Informatik I - Tutorium� Wintersemester 2007/08 �
Christian Jülg
http://infotut.blogspot.com
03. Dezember 2007
Universität Karlsruhe (TH)Forschungsuniversität · gegründet 1825
Quellennachweis & Dank an:Susanne Dinkler, Bernhard Müller, Joachim Wilke
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Übersicht
1 Organisatorisches
2 Übungsblatt 4
3 Java
4 Schleifeninvariante
5 Nützliches / Gefährliches
6 Halbgruppen und Monoide
7 AbschlussFeedback
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
1 Organisatorisches
2 Übungsblatt 4
3 Java
4 Schleifeninvariante
5 Nützliches / Gefährliches
6 Halbgruppen und Monoide
7 AbschlussFeedback
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Wenn doch noch Fragen auftauchen...
Kontakt
Kontakt: [email protected]
Homepage: http://infotut.blogspot.com
bitte beachten:
Im Betre� der Emails [08] einfügen!
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Wenn doch noch Fragen auftauchen...
Kontakt
Kontakt: [email protected]
Homepage: http://infotut.blogspot.com
bitte beachten:
Im Betre� der Emails [08] einfügen!
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
1 Organisatorisches
2 Übungsblatt 4
3 Java
4 Schleifeninvariante
5 Nützliches / Gefährliches
6 Halbgruppen und Monoide
7 AbschlussFeedback
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Übungsblatt 5
Kurzer Rückblick...
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Übungsblatt 5
Kurzer Rückblick...
Fragen?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Organisatorisches
Rechnerübung
Nächste normale RÜ mit Anmeldung am Di, 04.12. im RZ, Pool B- aber nur wenn es Anmeldungen gibt. Anmeldung per Email oderdirekt im Tut.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
1 Organisatorisches
2 Übungsblatt 4
3 Java
4 Schleifeninvariante
5 Nützliches / Gefährliches
6 Halbgruppen und Monoide
7 AbschlussFeedback
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Zufall
Math.random()
erzeugt double Werte im Bereich 0 ≤ d < 1
für Ganzzahlen zwischen 0 und 2: int i = Math.random()* 3
liefert nur Pseudo-Zufallszahlen⇒ sind bei gleichem �Seed� deterministisch
für mehr Kontrolle: java.util.Random
für mehr Sicherheit: java.security.SecureRandom
Für weitere Infos: Google �site:java.sun.com Math.random�
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Genauigkeit
Datentyp
byte
short
int
long
bool
float
double
Werte
-128 bis 127
-32.768 bis 32.767
-2147483648 bis 2147483647
-9.223.372.036.854.775.808 bis
9.223.372.036.854.775.807
true oder false
Im Bereich ±10±38Im Bereich ±10±308
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Genauigkeit
Listing 1: precision of �oat1 class Precision{2 public static void main(String cmd []){3 int max = Integer.MAX_VALUE;4 int almostMax = 2147483000;5 System.out.println(max);6 System.out.println (( float)max);7 int diff = max -almostMax;8 System.out.println(diff); //647
9 float fdif = (float)max -almostMax;10 System.out.println(fdif); //640.0
11 }12 }
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Trugschluss bei call-by-reference
Listing 2: fallacy1 class CallBy{2 static void m(String in){3 in += " nochwas";}4 static void n(Object o){5 o = new Object ();}6 public static void main(String cmd []){7 String input="A text.";8 System.out.println(input);9 m(input);10 System.out.println(input);//same text
11 Object obj = new Object ();12 System.out.println(obj);13 n(obj);14 System.out.println(obj);//same object
15 }16 }
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Arrays
Was wisst ihr zu dem Thema?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Arrays
Was wisst ihr zu dem Thema?
wie sehen Deklaration und Initialisierung aus?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Arrays
Was wisst ihr zu dem Thema?
wie sehen Deklaration und Initialisierung aus?
geht das auch anders?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Arrays
Was wisst ihr zu dem Thema?
wie sehen Deklaration und Initialisierung aus?
geht das auch anders?
wie sieht es mit default-Werten aus?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Arrays
Was wisst ihr zu dem Thema?
wie sehen Deklaration und Initialisierung aus?
geht das auch anders?
wie sieht es mit default-Werten aus?
wie werden mehrdimensionale Arrays benutzt?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Und nochmal...
Ein Syntaxdiagramm muss...1 ... allgemein verständliche Terminale nicht enthalten.2 ... so gezeichnet werden, dass die Leserichtung eindeutig ist.3 ... nur die selbe Sprache erzeugen, um passend zu einer EBNF
zu sein.
for-Schleifen in Java ...1 ... sind wenn möglich stets while vorzuziehen.2 ... braucht man nicht unbedingt, es reicht while.3 ... können mit break abgebrochen werden.
Variablen in Java ...1 ... können während der Laufzeit durch zB. (long) c += 1;
ihren Datentyp wechseln.2 ... verlangen bei Division stets nach einem Flieÿkommatyp.3 ... rechnen Punkt vor Strich.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Und nochmal...
Ein Syntaxdiagramm muss...1 ... allgemein verständliche Terminale nicht enthalten.2 ... so gezeichnet werden, dass die Leserichtung eindeutig ist.3 ... nur die selbe Sprache erzeugen, um passend zu einer EBNF
zu sein.
for-Schleifen in Java ...1 ... sind wenn möglich stets while vorzuziehen.2 ... braucht man nicht unbedingt, es reicht while.3 ... können mit break abgebrochen werden.
Variablen in Java ...1 ... können während der Laufzeit durch zB. (long) c += 1;
ihren Datentyp wechseln.2 ... verlangen bei Division stets nach einem Flieÿkommatyp.3 ... rechnen Punkt vor Strich.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Und nochmal...
Ein Syntaxdiagramm muss...1 ... allgemein verständliche Terminale nicht enthalten.2 ... so gezeichnet werden, dass die Leserichtung eindeutig ist.3 ... nur die selbe Sprache erzeugen, um passend zu einer EBNF
zu sein.
for-Schleifen in Java ...1 ... sind wenn möglich stets while vorzuziehen.2 ... braucht man nicht unbedingt, es reicht while.3 ... können mit break abgebrochen werden.
Variablen in Java ...1 ... können während der Laufzeit durch zB. (long) c += 1;
ihren Datentyp wechseln.2 ... verlangen bei Division stets nach einem Flieÿkommatyp.3 ... rechnen Punkt vor Strich.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Und nochmal...
Ein Syntaxdiagramm muss...1 ... allgemein verständliche Terminale nicht enthalten.2 ... so gezeichnet werden, dass die Leserichtung eindeutig ist.3 ... nur die selbe Sprache erzeugen, um passend zu einer EBNF
zu sein.
for-Schleifen in Java ...1 ... sind wenn möglich stets while vorzuziehen.2 ... braucht man nicht unbedingt, es reicht while.3 ... können mit break abgebrochen werden.
Variablen in Java ...1 ... können während der Laufzeit durch zB. (long) c += 1;
ihren Datentyp wechseln.2 ... verlangen bei Division stets nach einem Flieÿkommatyp.3 ... rechnen Punkt vor Strich.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
1 Organisatorisches
2 Übungsblatt 4
3 Java
4 Schleifeninvariante
5 Nützliches / Gefährliches
6 Halbgruppen und Monoide
7 AbschlussFeedback
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Schon wieder Mathe...
Schleifenin...was???
Schleifeninvarianten. . .
sind Aussagen, die am Anfang und am Ende einesSchleifendurchlaufs gelten.
helfen, die Korrektheit eines Programmes zu beweisen.
beweist man meist durch vollständige Induktion.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Vollständige Induktion tut nicht weh...
Ihr seid dran...
Wer kennt das Beweisverfahren der vollständige Induktion ?
Erklärt den �Unwissenden� das Verfahren...
Wer kennt das Verfahren nicht?
Hört gespannt zu...
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Vollständige Induktion tut nicht weh...
Ihr seid dran...
Ihr kennt das Beweisverfahren der vollständige Induktion ...Erklärt den �Unwissenden� das Verfahren...
Ihr kennt das Verfahren nicht...Hört gespannt zu...
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Beweisverfahren der vollständigen Induktion
Die Theorie
Der Beweis erfolgt in folgenden Schritten:1 Induktionsanfang: Die Aussage wird für n = n0 gezeigt2 Induktionsvorraussetzung: Die Aussage sei für ein n wahr.3 Induktionsschritt: Aus dem Schluÿ von n auf n + 1 folgt, dass
die Aussage für alle natürlichen Zahlen n > n0 gilt.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Beweisverfahren der vollständigen Induktion
Die Theorie
Der Beweis erfolgt in folgenden Schritten:1 Induktionsanfang: Die Aussage wird für n = n0 gezeigt2 Induktionsvorraussetzung: Die Aussage sei für ein n wahr.3 Induktionsschritt: Aus dem Schluÿ von n auf n + 1 folgt, dass
die Aussage für alle natürlichen Zahlen n > n0 gilt.
Ein Beispiel:
Beweise durch vollständig Induktion 1+ 3+ 5+ ... + (2n− 1) = n2:
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Beweisverfahren der vollständigen Induktion
Ein Beispiel:
Beweise durch vollständig Induktion 1 + 3 + 5 + ... + (2n− 1) = n2:
IA: n = 1: 1 = 12 = 1 ist erfüllt
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Beweisverfahren der vollständigen Induktion
Ein Beispiel:
Beweise durch vollständig Induktion 1 + 3 + 5 + ... + (2n− 1) = n2:
IA: n = 1: 1 = 12 = 1 ist erfüllt
IV: 1 + 3 + 5 + ... + (2n − 1) = n2 gilt für ein n ∈ N
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Beweisverfahren der vollständigen Induktion
Ein Beispiel:
Beweise durch vollständig Induktion 1 + 3 + 5 + ... + (2n− 1) = n2:
IA: n = 1: 1 = 12 = 1 ist erfüllt
IV: 1 + 3 + 5 + ... + (2n − 1) = n2 gilt für ein n ∈ NIS:
1 + 3 + 5 + ... + (2(n + 1)− 1)
= 1 + 3 + 5 + ... + (2n + 1)
= 1 + 3 + 5 + ... + (2n − 1) + (2n + 1)
IV= n2 + 2n + 1
= (n + 1)2
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Aufgabe
int a = In.readInt();int b = In.readInt();
if (a > b) {int h = a;a = b;b = h;
}
int z = b;int i = 1;
while ((z % a) != 0){ /*1*/z += b; /*2*/i++; /*3*/
}
Beweist oder widerlegt diefolgendenen Aussagen:
1 z = b · i ist eineSchleifeninvariante für diewhile-Schleife
2 LCM(a, b) = LCM(a, z) isteine Schleifeninvariante fürdie while-Schleife
3 Die while-Schleifeterminiert
Hinweise: Verwende geeigneteZusicherungen an den Positionen1,2 und 3.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Lösung Aufgabe 1
int a = In.readInt();int b = In.readInt();
if (a > b) {int h = a;a = b;b = h;
}
int z = b;int i = 1;
while ((z % a) != 0){ /*1*/z += b; /*2*/i++; /*3*/
}
Induktionsanfang: n = 1Zu Beginn des 1. Schleifendurchlaufs:z1 = b = b · 1 = b · i1
√
Induktionsannahme:
Beim n-ten Durchlauf gelte beiSchleifenbeginn (/*1*/): zn = b · inInduktionsschluss: (n→ n + 1)Es gelten folgende Zusicherungen:
/*1*/ zn = b · in./*2*/ zn+1 = zn + b.
/*3*/ in+1 = in + 1.
Also gilt:
zn+1 = zn + b = b · in + b
= b · (in + 1) = b · in+1
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Lösung Aufgabe 1 (Fortsetzung)
int a = In.readInt();int b = In.readInt();
if (a > b) {int h = a;a = b;b = h;
}
int z = b;int i = 1;
while ((z % a) != 0){ /*1*/z += b; /*2*/i++; /*3*/
}
Die Schleifeninvariante gilt alsoam Ende des n-ten Durchlauf unddamit auch am Anfang desn + 1-ten Durchlauf.Duch die Induktion ist nungezeigt, dass z = b · i am Anfangund am Ende jedesSchleifendurchlaufes gilt. Damitist bewiesen, dass es eineSchleifeninvariante ist.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Lösung Aufgabe 2
int a = In.readInt();int b = In.readInt();
if (a > b) {int h = a;a = b;b = h;
}
int z = b;int i = 1;
while ((z % a) != 0){ /*1*/z += b; /*2*/i++; /*3*/
}
Wir widerlegen durch
Gegenbeispiel:
Seien a = 3 und b = 5.
/*1*/ z1 = b = 5
⇒ LCM(a, b) = LCM(a, z1)
/*3*/ z2 = b · i2 = 5 · 2 = 10
LCM(a, b) = 15LCM(a, z2) = 30
⇒ keine Schleifeninvariante
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Lösung Aufgabe 3
int a = In.readInt();int b = In.readInt();
if (a > b) {int h = a;a = b;b = h;
}
int z = b;int i = 1;
while ((z % a) != 0){ /*1*/z += b; /*2*/i++; /*3*/
}
1 Zu Beginn gilt z = b
2 z wächst mit jedemDurchlauf monoton um b
3 z mod a = 0 genau dann,wenn z Vielfaches von a ist
4 Nach a Schritten istz = b · a Vielfaches von a
5 Die Schleife terminiert nach(spätestens) a Schritten
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Entspannungspäuschen??
5 Minuten Pause zum frei werden.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
1 Organisatorisches
2 Übungsblatt 4
3 Java
4 Schleifeninvariante
5 Nützliches / Gefährliches
6 Halbgruppen und Monoide
7 AbschlussFeedback
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
weitere Operatoren
ternärer Operator ? :
Dieser Operator ist besonders für kleine bedingte Zuweisungennützlich
int max = ( a > b )? a : b;
Aber auch für bedingte Ausgaben ist er nützlich:
System.out.println( ( a > b )? a : b );
Aber: der Operator liefert nur Werte zurück, keine Variablen
⇒ er lässt sich nicht auf der linken Seite von Zuweisungenverwenden.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
weitere Operatoren
|| und | bzw. && und &
1 public class LazyEager {2 public static void main(String [] args) {3 if ( true || sideEffect ())4 System.out.println("Lazy.");5 if ( true | sideEffect ())6 System.out.println("Eager.");7 } // && and & likewise
8 private static boolean sideEffect () {9 System.out.println("Not yet implemented");10 return false;11 }12 }
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
versch. Zeichensätze
1 import java.io.OutputStreamWriter;2 import java.io.PrintWriter;3 import java.io.UnsupportedEncodingException;4 public class Encoding {5 public static void main(String [] args) {6 try {7 System.out.println("Ich kann Ä Ü Ö und ÿ");8 PrintWriter out = new PrintWriter(9 new OutputStreamWriter(System.out , "Cp850"
));10 out.println("Ich kann Ä Ü Ö und ÿ");11 out.flush (); // flush buffer
12 } catch (UnsupportedEncodingException e) {13 } // here be error handling
14 }15 }
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
versch. Zeichensätze
mögliche Zeichensätze
IDEs wie Eclipse oder NetBeans haben eine eigene Konsole
diese hat idR keine Probleme mit der StandardkodierungUnicode
http://java.sun.com/javase/6/docs/technotes/guides/
intl/encoding.doc.html
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
1 Organisatorisches
2 Übungsblatt 4
3 Java
4 Schleifeninvariante
5 Nützliches / Gefährliches
6 Halbgruppen und Monoide
7 AbschlussFeedback
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Noch mehr Mathe ... - Halbgruppen
Was war das nochmal...1 Ein Menge M mit einer Abbildung ∗ : M ×M → M
In�x-Schreibweise bevorzugt (a ∗ b statt ∗(a, b))2 Diese Verknüpfung muss abgeschlossen sein
Die Schreibweise ∗ : M ×M → M sagt das bereits.Abgeschlossenheit bedeutet: Ich bekomme in jedem Fall einElement aus M heraus.
3 Das Assoziativgesetz muss gelten:(a ∗ b) ∗ c = a ∗ (b ∗ c) =: a ∗ b ∗ c
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Beispiele für eine Halbgruppe
Standardbeispiele
(N, +)
(N, ∗)
Zeichenketten
Die Menge Σ+ über einem Alphabet Σ ist mit der Konkatenationeine Halbgruppe und enthält alle Zeichenketten.In der Informatik ist Σ meist endlich. Dann ist Σ+ abzählbar.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Monoide
Ein Monoid ist...1 eine Halbgruppe mit2 ein Einselement ε, für das folgende Eigenschaften gelten:
ε ∗ a = a
a ∗ ε = a
Beachte
Gibt es ein Einselement, so gibt es genau eines. Man sagt, dasEinselement ist eindeutig.Kurz-Beweis:Angenommen e und e ′ sind Einselemente:Dann ist e ∗ e ′ = e und e ∗ e ′ = e ′. Also ist e = e ′
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Beispiel für Monoid
Zeichenketten mit Konkatention
Σ∗ := Σ+ ∪ {ε}ε ist das leere Wort, d.h. Länge |ε| = 0
falls wn die n-fache Wiederholung des Wortes w bezeichnet,so gilt w0 = ε
Haben wir ein allgemeines U, so ist das Einselement von [U]die leere Liste []
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Nachweis: Monoid
Ist eine gegebene Struktur ein Monoid? Zu überprüfen ist:Die Verknüpfung ∗ auf der Menge M ist abgeschlossen, erfüllt dasAssoziativgesetz und besitzt ein Einselement ε.
Checkliste
Abgeschlossenheit: ∀x , y ∈ M : x ∗ y ∈ M
Assoziativität: ∀x , y , z ∈ M : (x ∗ y) ∗ z = x ∗ (y ∗ z)Einselement: ∀x ∈ M : ε ∗ x = x ∗ ε = x
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Nachweis: Halbgruppe
Ist die gegebene Struktur ist eine Halbgruppe, aber kein Monoid?Zu zeigen ist: Die Verknüpfung ∗ auf der Menge M istabgeschlossen, erfüllt das Assoziativgesetz, sie besitzt aber keinEinselement.
Checkliste
Abgeschlossenheit: ∀x , y ∈ M : x ∗ y ∈ M
Assoziativität: ∀x , y , z ∈ M : (x ∗ y) ∗ z = x ∗ (y ∗ z)Einselement: @ε ∈ M : ∀x ∈ M : x ∗ ε = x und ε ∗ x = x
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Nachweis: Halbgruppe - Monoid
Überprüft, ob es sich bei folgenden Strukturen um Halbgruppenoder Monoide oder keines von beidem handelt. Beweist eureAussage. Ihr dürft bei den Beweisen auf schon bekannteEigenschaften aus der Vorlesung zurückgreifen. Zum Widerlegengenügen begründete Gegenbeispiele.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Aufgabe 1
Multiplikation
Die Multiplikation · auf der Menge M = {r ∈ R|r > 1}, wobei Rdie Menge der reelen Zahlen ist.
Die Struktur ist eine Halbgruppe, aber kein Monoid. DieMultiplikation auf R ist abgeschlossen, erfüllt das Assoziativgesetz,sie besitzt aber kein Einselement.
Beweis
Abgeschlossenheit: ∀x , y ∈ R : x · y ∈ RAssoziativität: ∀x , y , z ∈ R : (x · y) · z = x · (y · z)Einselement: ∀x , y ∈ M : y > 1⇒ x · y > x ⇒ x · y 6= x
⇒ y ist kein Einselement.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Aufgabe 1
Multiplikation
Die Multiplikation · auf der Menge M = {r ∈ R|r > 1}, wobei Rdie Menge der reelen Zahlen ist.
Die Struktur ist eine Halbgruppe, aber kein Monoid. DieMultiplikation auf R ist abgeschlossen, erfüllt das Assoziativgesetz,sie besitzt aber kein Einselement.
Beweis
Abgeschlossenheit: ∀x , y ∈ R : x · y ∈ RAssoziativität: ∀x , y , z ∈ R : (x · y) · z = x · (y · z)Einselement: ∀x , y ∈ M : y > 1⇒ x · y > x ⇒ x · y 6= x
⇒ y ist kein Einselement.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Aufgabe 2
Modulo-Operator
Der Modulo-Operator auf der Menge N.
Die Struktur ist nicht mal eine Halbgruppe.
Gegenbeispiel
Für eine Halbgruppe muss das Assoziativgesetz erfüllt sein, aber
(15%9)%5 = 6%5 = 1 6= 3 = 15%4 = 15%(9%5)
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Aufgabe 2
Modulo-Operator
Der Modulo-Operator auf der Menge N.
Die Struktur ist nicht mal eine Halbgruppe.
Gegenbeispiel
Für eine Halbgruppe muss das Assoziativgesetz erfüllt sein, aber
(15%9)%5 = 6%5 = 1 6= 3 = 15%4 = 15%(9%5)
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Aufgabe 3
Linksidentität
Die Linksidentität mit der Verknüpfung # mit a#b := a auf einerbeliebigen Menge M 6= ∅
Die Struktur ist eine Halbgruppe, aber kein Monoid. DieLinksidentität mit der Verknüpfung # auf M ist abgeschlossen,erfüllt das Assoziativgesetz, sie besitzt aber kein Einselement.
Beweis
Abgeschlossenheit: ∀x , y ∈ M : x#y = x ∈ M
Assoziativität: ∀x , y , z ∈ M : (x#y)#z = x#z
= x = x#y = x#(y#z)Einselement: ∀x , y ∈ M, x 6= y : x#y = x 6= y = y#x
⇒ y ist nicht Linkseins.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Aufgabe 3
Linksidentität
Die Linksidentität mit der Verknüpfung # mit a#b := a auf einerbeliebigen Menge M 6= ∅
Die Struktur ist eine Halbgruppe, aber kein Monoid. DieLinksidentität mit der Verknüpfung # auf M ist abgeschlossen,erfüllt das Assoziativgesetz, sie besitzt aber kein Einselement.
Beweis
Abgeschlossenheit: ∀x , y ∈ M : x#y = x ∈ M
Assoziativität: ∀x , y , z ∈ M : (x#y)#z = x#z
= x = x#y = x#(y#z)Einselement: ∀x , y ∈ M, x 6= y : x#y = x 6= y = y#x
⇒ y ist nicht Linkseins.
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
1 Organisatorisches
2 Übungsblatt 4
3 Java
4 Schleifeninvariante
5 Nützliches / Gefährliches
6 Halbgruppen und Monoide
7 AbschlussFeedback
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist der Sinn von Methoden und wie erkenne ich sie?
Wie transformiere ich Schleifen ohne einen Durchlauf zuunterschlagen oder zu viel zu machen?
Was ist eine Schleifeninvariante?
Wie beweise ich sie? Wie widerlege ich sie?
Wann terminiert formell eine Schleife?
Wie lautet die Checkliste zum Beweisen einer Halbgruppe odereines Monoids?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist der Sinn von Methoden und wie erkenne ich sie?
Wie transformiere ich Schleifen ohne einen Durchlauf zuunterschlagen oder zu viel zu machen?
Was ist eine Schleifeninvariante?
Wie beweise ich sie? Wie widerlege ich sie?
Wann terminiert formell eine Schleife?
Wie lautet die Checkliste zum Beweisen einer Halbgruppe odereines Monoids?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist der Sinn von Methoden und wie erkenne ich sie?
Wie transformiere ich Schleifen ohne einen Durchlauf zuunterschlagen oder zu viel zu machen?
Was ist eine Schleifeninvariante?
Wie beweise ich sie? Wie widerlege ich sie?
Wann terminiert formell eine Schleife?
Wie lautet die Checkliste zum Beweisen einer Halbgruppe odereines Monoids?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist der Sinn von Methoden und wie erkenne ich sie?
Wie transformiere ich Schleifen ohne einen Durchlauf zuunterschlagen oder zu viel zu machen?
Was ist eine Schleifeninvariante?
Wie beweise ich sie? Wie widerlege ich sie?
Wann terminiert formell eine Schleife?
Wie lautet die Checkliste zum Beweisen einer Halbgruppe odereines Monoids?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist der Sinn von Methoden und wie erkenne ich sie?
Wie transformiere ich Schleifen ohne einen Durchlauf zuunterschlagen oder zu viel zu machen?
Was ist eine Schleifeninvariante?
Wie beweise ich sie? Wie widerlege ich sie?
Wann terminiert formell eine Schleife?
Wie lautet die Checkliste zum Beweisen einer Halbgruppe odereines Monoids?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist der Sinn von Methoden und wie erkenne ich sie?
Wie transformiere ich Schleifen ohne einen Durchlauf zuunterschlagen oder zu viel zu machen?
Was ist eine Schleifeninvariante?
Wie beweise ich sie? Wie widerlege ich sie?
Wann terminiert formell eine Schleife?
Wie lautet die Checkliste zum Beweisen einer Halbgruppe odereines Monoids?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist der Sinn von Methoden und wie erkenne ich sie?
Wie transformiere ich Schleifen ohne einen Durchlauf zuunterschlagen oder zu viel zu machen?
Was ist eine Schleifeninvariante?
Wie beweise ich sie? Wie widerlege ich sie?
Wann terminiert formell eine Schleife?
Wie lautet die Checkliste zum Beweisen einer Halbgruppe odereines Monoids?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Zum Schluss...
Was ihr nun wissen solltet!
Was ist der Sinn von Methoden und wie erkenne ich sie?
Wie transformiere ich Schleifen ohne einen Durchlauf zu unterschlagenoder zu viel zu machen?
Was ist eine Schleifeninvariante?
Wie beweise ich sie? Wie widerlege ich sie?
Wann terminiert formell eine Schleife?
Wie lautet die Checkliste zum Beweisen einer Halbgruppe oder einesMonoids?
Ihr wisst was nicht?
Stellt jetzt Fragen!
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Feedback
Dann habe ich noch eine Frage:
Wie fandet ihr dieses Tutorium?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Feedback
Dann habe ich noch eine Frage:
Wie fandet ihr dieses Tutorium?
War ich zu schnell?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Feedback
Dann habe ich noch eine Frage:
Wie fandet ihr dieses Tutorium?
War ich zu schnell?
Habe ich bestimmte Sachen zu kurz behandelt?
Informatik I - Tutorium Christian Jülg
Orga Blatt 4 Java Schleifeninvariante Nützliches / Gefährliches Halbgruppen und Monoide Abschluss Ende
Informatik I - Tutorium Christian Jülg