Erste Schritte Schleifeninvariante

[Tindro]

Ich habe folgende Aufgabe als Hausaufgabe aufbekommen und hatte ziemliche Probleme die Aufgabe zu lösen. ich hoffe hier kann mir jemand eine Art Musterlösung anbieten, mit der ich es mir dann selbst beibringen kann.
Vorallendingen habe ich Probleme mit der Schleifeninvariante und deren beweis über die vollständige Induktion.

Beweisen Sie die Korrektheit des folgenden Algorithmus! Gehen Sie dabei auf Wohldefiniertheit, Terminierung und korrektes Ergebnis ein.

Input: reelle Zahlen a(1), ....... , a(n) alle echt größer 0
Output: geometrisches Mittel der zahlenfolge a(1), ..... , a(n)

(1) s = 0;
(2) i = 1;
(3) while i <= n do

(4) s = s + ln(a(i)):
(5) i = i +1;
(6) s = s/n;​

(7) return exp(s);

Vielen Dank schon mal im Vorraus

 

[AntiMuffin]

Hallo,
eine Musterlösung werde ich dir nicht machen, sonst Lernst du dabei ja nichts, aber ich helfe dir gerne:
Wie sehen denn deine Ansätze bis jetzt aus?

 

[Tindro]

Ich habe meine Antwort als .pdf , kann ich die hier irgendwie hochladen?

 

[Gucky]

Du könntest sie markieren und dann den Text posten, du benutzt einen Oneclickhoster oder etwas Vergleichbares zu Google Drive. Anhänge funktionieren nicht.

 

[Tindro]

Terminierung

- Index = "i <= n"
- i wird am ede der Schleife erhöht (keine Endlosschleife möglich)​

Wohldefiniertheit

- länge von "n" wird nicht überschritten​

- Division durch Null möglich, wenn n-Eingaben = 0​

Schleifeninvariant:

Schleifeninvarante am Anfang des Schleifendurchlauf gilt:​

i <= n​

IA:Initialisierung (Zeile 2)​

i = 1, dann gilt:
1 <= n​

IS: nach IV gilt:​

sei i <= n
nach Zeile 5 gilt:
i + 1 <= n​

somit folgt:​

i < i+1 < i+ (n-1) <= n

​

Für diese Lösung habe ich insgesamt 1 von 4 Punkten bekommen.

 

[Gucky]

Du bist nicht auf das Ergebnis eingegangen. Vielleicht liegt es daran.

 

[Joose]

Anhänge funktionieren nicht.

[ot]Dem will ich widersprechen [/ot]Anhang anzeigen consoleText.txt

 

[Gucky]

@Joose
Wie hast du das denn gemacht? Ich sehe immer Anhang3736 und wenn man draufklickt bekommt man die Meldung der Link sei defekt.

 

[Tindro]

Ergebnis? Auf welches Ergebnis?

 

[Gucky]

und korrektes Ergebnis ein.

Auf dieses Ergebnis.

 

[stg]

Du bist nicht auf das Ergebnis eingegangen. Vielleicht liegt es daran.

Oder es liegt daran, dass in der geposteten Lösung einfach nur Blödsinn steht. Für die Aussagen zu "Terminierung" kann man mit viel Wohlwollen noch den einen Punkt geben, der Rest hingegen lässt stark vermuten, dass der TE nicht einmal die Begriffe verstanden hat, um die es hier geht...

Zur Aufgabe selbst: Ich würde einfach mal versuchen zu zeigen, dass der Algorithmus NICHT korrekt ist! Jedenfalls so, wie er da steht. Es müsste stattdessen eigentlich wie folgt aussehen:

(1) s = 0;
(2) i = 1;
(3) while i <= n do
    (4) s = s + ln(a(i)):
    (5) i = i +1;
(6) s = s/n;
(7) return exp(s);

Vielleicht reicht das ja schon, um deine Verwirrung zu beseitigen?!

 

[Tindro]

Nagut, nehmen wir an der Code lautet so:

(1) s = 0;
(2) i = 1;
(3) while i <= n do
    (4) s = s + ln(a(i)):
    (5) i = i +1;
(6) s = s/n;
(7) return exp(s);

Wie hätte ich dann die Aufgabe lösen können?