Informatik I Tutorium - STUDWWW s_kehne/tutorium/tutorium06.pdf · PDF file 2 Agenda des heutigen Tutoriums Übersicht heute • Rückblick • Theorie • Schleifeninvariante

Vorlesung:

Prof. Dr. F. Bellosa

Übungsleitung:

Dipl.-Inform. A. Merkel

Tutorium:

Tutor:

Informatik I TutoriumWS 07/08

Tutorium 6: Dienstag, 04. Dezember 2007

12

Jens Kehne

http://info1.informatik.uni-karlsruhe.de

2

Agenda des heutigen Tutoriums

Übersicht heute

• Rückblick

• Theorie

• Schleifeninvariante

• Halbgruppen und Monoide

• Praxis

• String-Manipulation


3

Rückblick

• „Begründen sie ihre Antwort“ meint die ganze Antwort

• ...außerdem muss natürlich eine Antwort dastehen...

• Schon wieder geschenkte Punkte


4

TheorieSchleifeninvariante


5

Definition

• Eine Schleifeninvariante ist eine Zusicherung, die in

jedem Schleifendurchlauf gilt.

• Beispiel:

int i = 1; for (i = 2;i<=100;i++) n = n + i;

• Eine Invariante dafür wäre 1

( 1)

2

i

k

i in k


6

Gegeben sei folgendes Programmstück:

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*/

}

Beweisen oder widerlegen Sie die Korrektheit der folgenden Aussagen:

a) z == b * i ist eine Schleifeninvariante für die while-Schleife.

b) kgV(a,b) == kgV(a,z) ist eine Schleifeninvariante für die while-Schleife.

c) Die while-Schleife terminiert.Hinweis:

Nutzen Sie geeignete Zusicherungen an den Stellen position 1, position 2 und position 3,

um die Beweise zu führen.

Aufgabe 1: Schleifeninvariante


7

Aufgabe 1.3a: Schleifeninvariante (15T)

Lösung a): Beweis über vollständige Induktion.

Induktionsanfang:

Beim ersten Schleifendurchlauf gilt z == b * i

denn (z == b) && (i == 1)

Induktionsschluss:

Annahme:

Beim n-ten Durchlauf gilt bei Schleifenbeginn (position 1) z == b * i

Zu zeigen:

Beim (n+1)-ten Durchlauf gilt bei Schleifenbeginn (position 1) z == b * i

Damit muss gelten: Beim n-ten Durchlauf gilt bei Schleifenende (position 3) z == b * i



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*/

}


8


Lösung a) (Fortsetzung): Beweis über vollständige Induktion.

Es gelten folgende Zusicherungen:

position 1:

zalt == b * ialt

position 2:

zneu == zalt + b

position 3:

ineu == ialt + 1

Somit gilt am Ende der Schleife (position 3):

zneu == zalt + b == b * ialt + b == b * (ialt + 1) == b * ineu

Durch vollständige Induktion ist damit bewiesen, dass z = b * i am Anfang und am Ende jedes

Schleifendurchlaufs gilt.

Da der Ausdruck z = b * i am Anfang und am Ende jedes Schleifendurchlaufs gilt, ist nachgewiesen,

dass es sich bei diesem Ausdruck um eine Schleifeninvariante handelt.



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*/

}


9

Aufgabe 1.3b: Schleifeninvariante (15T)

Lösung b): Beweis durch Gegenbeispiel:

Sei beispielsweise

a == 3

b == 5

Zu Beginn des ersten Schleifendurchlaufs (position 1) gilt z == b == 5

Somit gilt kgV(a,b) == kgV(3,5) == 15 == kgV(3,5) == kgV(a,z)

Am Ende des ersten Schleifendurchlaufs (position 3) gilt zneu == b * ineu (siehe Teilaufgabe a))

=> ineu == ialt + 1 == 1 + 1 == 2

=> zneu == b * 2 == 5 * 2 == 10

aber kgV(a, b) != kgV(a, zneu)

kgV(a, b) == 15 aber kgV(a, zneu) == 30



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*/

}


10

Aufgabe 1.3b: Schleifeninvariante (15T)

Lösung c):

I) zu Beginn gilt z ==b

II) z wächst mit jedem Schleifendurchlauf streng monoton um b.

III) a * b ist ein gemeinsames Vielfaches von a und b.

IV) Aus I), II) und III) => a * b ist obere Schranke für z.

V) aus I), II) und IV) => die Schleife terminiert.



if (a > b) {

int h = a;

a = b;

b = h;

}

int z = b;

int i = 1;

while ((z % a) != 0){

z += b;

i++;

}


Gegeben sei folgendes Programmstück:

public static double exp(byte b, byte e) {

// assertion: 0 <= e <= 127

double r = 1;

int i = 0;

while (i < e) {

// assertion when entering loop: (i < e)

// position 1

r = r * b;

// position 2

i++;

// position 3

}

return r; // return b^e

}

Beweisen oder widerlegen Sie die Korrektheit der folgenden Aussagen:

a) r == bi ist eine Schleifeninvariante für die while-Schleife.Hinweis:

Nutzen Sie geeignete Zusicherungen an den Stellen position 1, position 2 und position 3,

um die Beweise zu führen. 11

Aufgabe 2: Schleifeninvariante


12


Lösung a): Beweis über vollständige Induktion.

Induktionsanfang:

An position 1 gilt im ersten Schleifendurchlauf: r == 1 == b0 == bi.

Induktionsschluss:

Annahme:

An Position 1 gelte für beliebiges i: r == bi .

Zu zeigen:

Beim (n+1)-ten Durchlauf gilt bei Schleifenbeginn (position 1):r == bi

Damit muss gelten: Beim n-ten Durchlauf gilt bei Schleifenende (position 3) r == bi

public static double

exp(byte b, byte e)

{

// assertion: 0 <= e <= 127

double r = 1;

int i = 0;

while (i < e) {

// assertion when entering

loop: (i < e)

// position 1

r = r * b;

// position 2

i++;

// position 3

}


}


public static double

exp(byte b, byte e)

{

// assertion: 0 <= e <= 127

double r = 1;

int i = 0;

while (i < e) {

// assertion when entering

loop: (i < e)

// position 1

r = r * b;

// position 2

i++;

// position 3

}


}

13


Lösung a) (Fortsetzung): Beweis über vollständige Induktion.

Es gelten folgende Zusicherungen:

Position 1: ralt == bialt (laut Induktionsvoraussetzung)

Position 2: rneu == ralt * b

Position 3: ineu == ialt + 1

Somit gilt am Ende der Schleife (position 3):

rneu == ralt * b == bialt * b == bi

alt+1 == bi

neu

Durch vollständige Induktion ist damit bewiesen, dass r == bi am Anfang und am Ende jedes

Schleifendurchlaufs gilt.

Da der Ausdruck z == bi am Anfang und am Ende jedes Schleifendurchlaufs gilt, ist nachgewiesen,

dass es sich bei diesem Ausdruck um eine Schleifeninvariante handelt.


14

TheorieHalbgruppen und Monoide


15

Halbgruppe

• Die in der Zeichenverarbeitung auftretende Beziehung des Nebeneinanderschreibens von Zeichen lässt sich als eine Halbgruppe auffassen

• Mathematische Formulierung als Algebra• Menge

• Zeichenreihen über der Grundmenge

• Operationen

• . Konkatenation

• Gesetze

• HG1: (a . b) . c = a . (b . c) Assoziativgesetz

• Die Eigenschaft der algebraischen Abgeschlossenheit ist erfüllt

• Die beschriebene Algebra ( . HG1 , kurz auch als bezeichnet, bildet eine Halbgruppe

Au

s d

er

Vo

rle

su

ng


16

Monoid

• Ein Monoid ist eine Halbgruppe mit Einselement• Eigenschaft eines Einselements

(1) a = a

(2) a = a

• das Einselement ist eindeutig

Beweis: Seien , ´ Einselemente

= ´ = ´ (Im ersten Schritt wurde die Einselement-

Eigenschaft von ausgenutzt, im Zweiten die von ´)

• Beispiel eines Monoids: • ist das leere Wort, d.h. die Länge ist 0

• falls wn die n-fache Wiederholung des Wortes w bezeichnet, so gilt w0=


17

Monoid U* über Monoid *

• In der Informatik werden Monoide U* häufig über anderen Grundmengen als Zeichen gebildet• Grundmenge U kann aus Zeichenreihen bestehen, die aus

einem anderen Monoid stammen

• Elemente von U* heißen Listen

• oder alternativ: Sequenzen, Folgen

• Notation:

• Liste: [x1,x2,...,xn], wobei xi U

• [] ist die leere Liste

• [U] als alternative Schreibweise für U*

• Beispiel: U = {Apfel,Birne,Pflaume,Kirsche,Traube}• [Apfel,Birne], [Pflaume,Kirsche,Traube] sind Listen

• append([Apfel,Birne], [Pflaume,Kirsche,Traube]) ist eine alternative Funktionsschreibweise für

[Apfel,Birne] [Pflaume,Kirsche,Traube] (Infix-Operator)


18

Beispielvorgehen: Nachweis: Halbgruppe – Monoid

Die gegebene Struktur ist ein Monoid. Die Relation R auf der Menge M ist

abgeschlossen, erfüllt das Assoziativgesetz und besitzt das Einselement E.

Beweis:

Abgeschlossenheit: für alle x, y ∈ M gilt, x R y ∈ M

Assoziativität: für alle x, y, z ∈ M gilt, (x R y) R z = x R (y R z)

Einselement: für alle x ∈ M gilt, E R x = x und x R E = x

Die gegebene Struktur ist eine Halbgruppe, aber kein Monoid. Die Relation R auf

der Menge M ist abgeschlossen, erfüllt das Assoziativgesetz, sie besitzt aber kein

Einselement.

Beweis:

Abgeschlossenheit: für alle x, y ∈ M gilt, x R y ∈ M

Assoziativität: für alle x, y, z ∈ M gilt, (x R y) R z = x R (y R z)

Einselement: es gibt kein Einselement (Wieso? Begründung!)


19

Aufgabe 1: Nachweis: Halbgruppe – Monoid

Überprüfen Sie, ob es sich bei folgenden Strukturen um Halbgruppen oder Monoide

oder keines von beidem handelt. Beweisen Sie Ihre Aussage. Sie dürfen zum

Beweisen auf schon bekannte Eigenschaften aus der Vorlesung zurückgreifen. Zum

Widerlegen genügen begründete Gegenbeispiele.

a) Die Addition auf der Menge ℕ0, der natürlichen Zahlen mit der Zahl Null.

Lösung a):

Die Struktur ist ein Monoid. Die Addition auf ℕ0 ist abgeschlossen, erfüllt das

Assoziativgesetz und besitzt das Einselement Null.

Beweis:

Abgeschlossenheit: für alle x, y ∈ ℕ0 gilt, x + y ∈ ℕ0

Assoziativität: für alle x, y, z ∈ ℕ0 gilt, (x + y) + z = x + (y + z)

Einselement: für alle x ∈ ℕ0 gilt, 0 + x = x und x + 0 = x


20






b) Die Multiplikation ∗ auf der Menge M={r ∈ ℝ | r > 1}, wobei ℝ die Menge der

reellen Zahlen ist.

Lösung b):

Die Struktur ist eine Halbgruppe, aber kein Monoid. Die Multiplikation auf ℝ ist

abgeschlossen, erfüllt das Assoziativgesetz, sie besitzt aber kein Einselement.

Beweis:

Abgeschlossenheit: für alle x, y ∈ M gilt, x∗ y ∈ M

Assoziativität: für alle x, y, z ∈ M gilt, (x ∗ y) ∗ z = x ∗ (y ∗ z)

Einselement: es gibt kein Einselement (Die Vermutung das dies die 1 ist, ist

falsch, denn 1 liegt nicht M)


21






c) Die Vektoraddition mit der Verknüpfung + : (a, b) + (c, d) = (a + c, b + d) auf der Mengeℕ0, der natürlichen Zahlen mit der Zahl Null.

Lösung c):

Die Struktur ist ein Monoid.

Beweis:

In beiden Stellen des Vektors findet unabhängig voneinander eine normale

Addition wie bei der Struktur in Aufgabenteil a) statt. Von dieser ist bekannt, dass

sie abgeschlossen und assoziativ ist und mit der Null ein Einselement, besitzt.


22






d) Die Linksidentität mit der Verknüpfung # : a # b = a auf der Menge ℕ0 der

natürlichen Zahlen mit der Zahl Null.

Lösung d):

Die Struktur ist eine Halbgruppe, aber kein Monoid. Die Linksidentität mit der

Verknüpfung # auf ℕ0 ist abgeschlossen, erfüllt das Assoziativgesetz, sie besitzt

aber kein Einselement.

Beweis:

Abgeschlossenheit: für alle a, b ∈ ℕ0 gilt, a # b = a ∈ ℕ0

Assoziativität: für alle a, b, c ∈ ℕ0 gilt, a # (b # c) = a # b = a = a # c = (a # b) # c

Einselement: es gibt kein Einselement (z.B. a # e = a ⇒ jedes e ∈ ℕ0 ist

Rechtseins, aber e # a = e ⇒ kein e ∈ ℕ0 ist Linkseins )


23






e) Die Konkatenation von Zeichenketten (Strings) in Java.

Lösung e):

Die Struktur ist ein Monoid. Die Konkatenation von Zeichenketten (Strings) in Java

ist abgeschlossen, erfüllt das Assoziativgesetz und besitzt als Einselement die

leere Zeichenkette.

Beweis:

Abgeschlossenheit: für alle a, b ∈ String gilt, a b = a ∈ String

Assoziativität: für alle a, b, c ∈ String gilt, a (b c) = a (bc) = abc = (ab) c = (a b) c

Einselement: Der String e=“ “ leere Zeichenkette ist das Einselement.

Es gilt a = a e und a = e a.


24

PraxisString-Manipulation


25

Java (String-Manipulation)

• Es gibt viele verschiedene Wege mit Strings zu arbeiten

• Viele Dinge lassen sich direkt mit den Methoden des String-Objekts bewerkstelligen (String.length(), String.charAt(int), String.equals(String), String.startsWith(String), …)

• Für komplexere Anwendungen empfiehlt sich die Umwandlung in andere Datenstrukturen. Hier sind die Folgenden besonders wichtig:• char-Array

• StringBuffer

• Beim char-Array handelt es sich um ein normales Array, das jedes Zeichen im String enthält (v.l.n.r.). Für einen String der Länge 10 wird also ein Array der Größe 10 mit den Indizes 0 bis 9 erstellt.• Umwandlung erfolgt mit der Methode String.toCharArray()


26

Java (StringBuffer)

• Häufig ist es jedoch angebracht, mit dem komplexen Datentyp StringBuffer zu arbeiten, da dieser viele nützliche (und schnelle) Funktionen bietet (u.a. zur Zeichenersetzung, Vertauschung, Suche, …)• Erzeugen eines neuen StringBuffers mittels Konstruktor:

• StringBuffer sb = new StringBuffer(String);

• Nützliche Methoden:

• StringBuffer.length(), StringBuffer.charAt(int), StringBuffer.toString(), StringBuffer.append(Sting), StringBuffer.delete(int, int), StringBuffer.substring(int, int), StringBuffer.replace(int, int, String)

• Beispielsweise lässt sich im String "Java ist doof!" das letzte Wort folgendermaßen ersetzen:

• StringBuffer sb = new StringBuffer("Java ist doof!");

• sb.replace(9, 13, "klasse");


27

Fragen? Questions?

Fragen? Questions?

Fragen? Questions?

Fragen? Questions?

Fragen? Questions?Fragen? Questions?

Fragen? Questions?

Fragen? Questions?

Fragen? Questions? Fragen? Questions?

Fragen? Questions? Fragen? Questions?

Fragen? Questions?

Questions?

Fragen?


28

Bis bald …


29

Credits

• Erstellung und Zusammenstellung des Materials:

• Christian Maier (Zusammenstellung)

• Stephan Kessler (Überarbeitung und Erweiterung)

• Till Fischer (Folien zur String-Manipulation)

Documents

Informatik I Tutorium - STUDWWW s_kehne/tutorium/tutorium06.pdf · PDF file 2 Agenda des heutigen Tutoriums Übersicht heute • Rückblick • Theorie • Schleifeninvariante