3. Übungsblatt - Abgabe 14. November

[elitoliker]

habt ihr denn explizit die länge des wortes bei 3.1 a abgefragt? sonst wisst ihr ja nicht wie lang das wort ist und könnt auch kein n definieren

[Dennis]

Es ist doch Gn angegeben, dabei ist n die Länge des Wortes.

[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)

[mfs]

mit

Hi pedobear,

diesen Zusammenhang kann man ja mehr oder weniger einfach aus dem Quellcode ablesen. Ich dachte, die Aufgabenstellung verlange es, für Formeln zu finden, die jeweils nur von den Eingaben a,b und der Laufvariablen k abhängen (wie in meinem Post weiter oben). Meint ihr, dass der Zusammenhang als Schleifeninvariable reicht?

MfG,
mfs.

[Chrisor]

mit

Hi pedobear,

diesen Zusammenhang kann man ja mehr oder weniger einfach aus dem Quellcode ablesen. Ich dachte, die Aufgabenstellung verlange es, für Formeln zu finden, die jeweils nur von den Eingaben a,b und der Laufvariablen k abhängen (wie in meinem Post weiter oben). Meint ihr, dass der Zusammenhang als Schleifeninvariable reicht?

MfG,
mfs.

ja. schau im skript nach, dort sind die zusammenhänge auch nur so angegeben..

[mfs]

Hi,

ich habe die 3.2 bis jetzt folgendermaßen:

a)

b) im k-ten Schleifendurchlauf gilt:


c) Induktionsanfang:

Induktionsvoraussetzung: Sei

Induktionsschluss: zu zeigen:
(Das Zeichen ist das -Zeichen für "div".)

Wie ihr seht, hab ich den Ausdruck übrig. Damit mein Beweis fertig ist, müsste dieser Term gerade 1 ergeben.

Habt ihr da eine Idee? Oder habt ihr das irgendwie anders bewiesen?

MfG,
mfs.

[markusj]

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

[grovieman]

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:



Jetzt die entsprechenden Werte aus dem Algorithmus einsetzen:


Das ganze noch mal umgeformt:


und da (a mod 2) + 2*(a div 2) = a folgt daraus, dass b^a = b^a ist.

Ist das die Lösung oder bin ich komplett auf dem Holzweg?

Gruß

[mfs]

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.

[grovieman]

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