jup, hab ich auch so..mfs hat geschrieben:Bis hierhin bin ich einverstanden. Du kannst jetzt aber nicht einfach die Initialisierungswerte aus dem Algorithmus einsetzen. Das musst du schon allgemein machen.grovieman hat geschrieben: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:
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.
3. Übungsblatt - Abgabe 14. November
Re: 3. Übungsblatt - Abgabe 14. November
Re: 3. Übungsblatt - Abgabe 14. November
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.grovieman hat geschrieben: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
Re: 3. Übungsblatt - Abgabe 14. November
würde ich auch gerne mal wissen. Ich fühl mich nämlich so leicht dazu verleitet bei 1c) einfach den Schleifenrumpf hinzuschreiben o_Osalami hat geschrieben:Hi, kann mir mal jemand erklären, was der Unterschied zwischen Aufgabe 1a und 1c ist?
Re: 3. Übungsblatt - Abgabe 14. November
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.
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.
Re: 3. Übungsblatt - Abgabe 14. November
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?
Re: 3. Übungsblatt - Abgabe 14. November
Das is ja goil, macht er das zu jedem Übungsblatt? Welches Tut?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.
Cheers André
Re: 3. Übungsblatt - Abgabe 14. November
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 nichtfake hat geschrieben: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?
Re: 3. Übungsblatt - Abgabe 14. November
alles klar danke
Re: 3. Übungsblatt - Abgabe 14. November
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.markusj hat geschrieben:Fragte sich unser Tutor auch ... Fakt ist:DaVinci hat geschrieben: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)
Du WIRST W nutzen.
Du kennst NUR die "Befehle", die Worsch für sein W definiert.
W besteht im Moment NUR aus:Es gibt KEIN break.
- Zuweisungen (<--)
- Vergleichen (siehe Mathematik)
- Fallunterscheidungen (wie in Mathe, mit geschweifter Klammer) und
- for to od Schleifen
mfG
Markus
PS: Ich hab die Pseudo-Sprache einfach mal W getauft
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.
¿ɯıɥ ssɐɹɹɐqɯǝ ʎɥʍ 'ʇou s,ʇı ɟı — noʎ llǝʇ ll,ǝɥ 'ɔɐɯ ɐ s,ʇı ɟı — sǝsn ǝɥ so ʇɐɥʍ uɐɯ ɐ ʞsɐ ɹǝʌǝu
Re: 3. Übungsblatt - Abgabe 14. November
In der Bib gibts "Einführung in Algorithmen" Da ist genau definiert wie pseudo Code aussehen soll