3. Übungsblatt - Abgabe 14. November

[Chrisor]

Zur 3.2 c)

Ich hab das folgendermaßen gelöst:

Zunächst beim Induktionsanfang i=0 => b^a = b^a
Dann hab ich den Induktionsschluss folgendermaßen (hier ebenfalls mit i statt mit k, denke mal das geht auch):



soweit so gut. Dann kann man ja die Sachen aus der "for-Schleife" dafür einsetzen. Dann sieht das so aus:

Bis hierhin bin ich einverstanden. Du kannst jetzt aber nicht einfach die Initialisierungswerte aus dem Algorithmus einsetzen. Das musst du schon allgemein machen.

Mein Vorschlag für eine allgemeine Lösung wäre:



Zur Erklärung der Gleichheitszeichen: 1.) Hier habe ich die Angaben aus der For-Schleife eingesetzt.
2.) Hier habe ich auch die Angaben aus der For-Schleife benutzt (bezüglich x bzw. X) und Potenzrechenregeln:
3.) Hier habe ich wieder Potenzrechnung gemacht:
4.) Hier habe ich folgende Eigenschaft von div und mod angewandt:
5.) Induktionsvoraussetzung.

Meint ihr, das passt so?

MfG,
mfs.

jup, hab ich auch so..

[M.A.]

Wieso darf ich die Werte denn nicht einsetzen?
Ich will doch den Algorithmus beweisen und die Werte X0, Y0 und P0 sind ja fest belegte/zugewiesene Werte durch den Algorithmus. Ich setze ja keine willkürlichen Zahlen ein, denn a und b kann ja alles mögliche sein.
Deshalb fand ich das ziemlich allgemein

Seh ich auch so. Die Invariante muss ja vor der Schleife, während der Schleife und danach gelten. Wenn man X_0, Y_0 und P_0 nimmt trifft das auf "vor der Schleife" zu und ist genausogut wie X_1.

[elTybbq]

Hi, kann mir mal jemand erklären, was der Unterschied zwischen Aufgabe 1a und 1c ist?

würde ich auch gerne mal wissen. Ich fühl mich nämlich so leicht dazu verleitet bei 1c) einfach den Schleifenrumpf hinzuschreiben o_O

[Chrisor]

unser tutor hat uns folgendes geschrieben:

Hinweise zum 3.Übungsblatt
3.1 a): Ein Programm in Pseudo-Code wie in der Vorlesung. 3.1 b): Einfach eine prädikatenlogische Formel 3.1 c): Eine triviale Schleifeninvariante, wäre $6>3$; eine nichttriviale Schelifeninvariante, die nicht den wesentlichen Teil des Algorithmus widerspiegelt, wäre $i < n$ (wenn $i$ die Schleifenvariable ist).
Hinweis: Schleifeninvariante kann auch Schleifenvariable enthalten.
3.2 a): Formel mit $a$ und $b$ 3.2 b): Wie 3.1 c) 3.2 c): Beweis durch Induktion über Anzahl der Schleifendurchläufe (also Induktionsanfang, Induktionsannahme, Induktionsschritt). 3.2 d): Gleiches Ergebnis oder anderes Ergebnis? Begründung sollte "plausibel" sein, muss aber kein strenger Beweis sein.

[fake]

ne kurze frage, ich hab die 3.1 a) jetzt auch gemacht doch habe ich bei mir geschrieben for i <-- 0 to n-1 do ........... den rest habe ich gleich, aber warum kommt hier n-2 hin und nicht n -1?

[Dre]

Hinweise zum 3.Übungsblatt
3.1 a): Ein Programm in Pseudo-Code wie in der Vorlesung. 3.1 b): Einfach eine prädikatenlogische Formel 3.1 c): Eine triviale Schleifeninvariante, wäre $6>3$; eine nichttriviale Schelifeninvariante, die nicht den wesentlichen Teil des Algorithmus widerspiegelt, wäre $i < n$ (wenn $i$ die Schleifenvariable ist).
Hinweis: Schleifeninvariante kann auch Schleifenvariable enthalten.
3.2 a): Formel mit $a$ und $b$ 3.2 b): Wie 3.1 c) 3.2 c): Beweis durch Induktion über Anzahl der Schleifendurchläufe (also Induktionsanfang, Induktionsannahme, Induktionsschritt). 3.2 d): Gleiches Ergebnis oder anderes Ergebnis? Begründung sollte "plausibel" sein, muss aber kein strenger Beweis sein.

Das is ja goil, macht er das zu jedem Übungsblatt? Welches Tut?

[elTybbq]

ne kurze frage, ich hab die 3.1 a) jetzt auch gemacht doch habe ich bei mir geschrieben for i <-- 0 to n-1 do ........... den rest habe ich gleich, aber warum kommt hier n-2 hin und nicht n -1?

Weil beim i-ten Durchgang der (i+1)-te Buchstabe mitgeprüft wird. Würde die Schleife bis n-1 laufen würde beim (n-1)-ten Durchgang w(n-1) und w(n) geprüft werden und w(n) gibt es halt nicht

[fake]

alles klar danke

[DaVinci]

Bin ich der einzige, der bitte schön endlich eine verbindliche Syntax-Definition für Worschs Pseudo-Code haben möchte?
À la "ist break erlaubt?" Wie habe ich ein Conditional-Branch mit nur einem Fall zu schreiben?
Anyway, warum nicht gleich in C? (ohne Typisierung und Memory Allocation, etc. von mir aus)

Fragte sich unser Tutor auch ... Fakt ist:
Du WIRST W nutzen.
Du kennst NUR die "Befehle", die Worsch für sein W definiert.
W besteht im Moment NUR aus:

• Zuweisungen (<--)
• Vergleichen (siehe Mathematik)
• Fallunterscheidungen (wie in Mathe, mit geschweifter Klammer) und
• for to od Schleifen

Es gibt KEIN break.

mfG
Markus

PS: Ich hab die Pseudo-Sprache einfach mal W getauft

Nicht mehr ganz so richtig. Weil: Ich bin nach der letzten Vorlesung mal zum Worsch gegangen und ihn um eine genaue Syntax-Definition gebeten. Worauf er meinte wir würden von ihm aus auch richtigen Programm-Code nutzen dürfen. Er selbst sei dafür einfach zu faul, daher der Pseudo-Code.
Unser Code muss nicht einmal 100% kompilieren können: Jeweils unwichtigen Schnickschnack wie Typisierung und Speicher-Management können wir vernachlässigen/weglassen.

Achja, nochwas: Er bat jedoch darum von Ternary-Operators und ähnlich geschachtelten/komplexen Konstrukten abzusehen. Unsere Tutoren wollen es ja schließlich schnell verstehen können.

Dinge wie "if-else", "for", "do-while", "while", "break", "return" und vergleichbar generische (C-)Syntax ist jedoch erlaubt.

[JTex]

In der Bib gibts "Einführung in Algorithmen" Da ist genau definiert wie pseudo Code aussehen soll