Seite 1 von 1

Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Verfasst: 12. Jul 2017 11:49
von SophiaLi1
Hallo,

auf dem 5. Übungsblatt steht für den rekursiven Algorithmus:
Korrektes Endergebnis: Folgt aus Invariante und Abbruchbedingung. Zum Zeitpunkt, da die höchste Rekursionsebene terminiert wurde der komplette Baum betrachtet.
Übrigens inklusive Kommafehler, aber den übergehe ich jetzt mal. Meiner Meinung nach ist das falsch. Bei rekursiven Algorithmen folgt das korrekte Endergebnis nur aus der Invariante, genauso wie wir es in der Übung #2b gelernt haben. Die Invariante besagt ja, dass der Algorithmus für Bäume der Höhe h das korrekte Ergebnis liefert. Die Invariante haben wir mittels Induktion bewiesen, also ist das korrekte Endergebnis folglich allein durch die Invariante geben. Als Vergleich hier nochmal der Satz aus den Übungen zu #2b:
Korrektes Endergebnis: Aus der Invariante folgt, dass der Algorithmus das geforderte Ergebnis zurück liefert. Da der Algorithmus im ersten Rekursionsschritt mit der Wurzel des Baumes aufgerufen wurde, besagt das Ergebnis ob das Element im Baum enthalten ist.
Also meine Frage: Braucht man die Abbruchbedingung bei rekursiven Algorithmen für das korrekte Endergebnis?

Re: Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Verfasst: 14. Jul 2017 12:10
von invariant
Hallo,

Abbruchbedingung und Invariante.
Invariante besagt, dass wir das korrekte Ergebnis erhalten.
Abbruchbedingung z.B., dass wir den kompletten Baum abgearbeitet haben - steckt aber auch zum Teil in der Induktion, ja.

Hoffe das beantwortet die Frage.

Gruß

Re: Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Verfasst: 16. Jul 2017 22:40
von SophiaLi1
Hi, ehrlich gesagt nicht, denn die Abbruchbedingung ist nur dazu relevant, dass der Algorithmus terminiert. Die Invariante allein sagt ja schon aus, dass der rekursive (!) Algorithmus das korrekte Endergebnis liefert, genauso wie in Theorie #2b gelernt. Warum sollte es plötzlich in Theorie #5 anders sein?

Re: Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Verfasst: 17. Jul 2017 17:38
von ttt3
Ich glaube schon, dass man die Abbruchbedingung für das korrekte Endergebnis (analog zu iterativen Algorithmen) braucht.

Durch Beweisen der Invariante wissen wir bspw., dass der rekursive Algorithmus das korrekte Ergebnis für Bäume der Höhen -1 ... h liefert. Wir wissen also, dass jeweils das Ergebnis für diese Bäume korrekt ist.

Ich denke aber, dass wir - hinsichtlich der Spezifikation - überprüfen müssen, zu welchem Zeitpunkt der rekursive Algorithmus terminiert und ob das derzeitige Zwischenergebnis für die derzeitige Baumhöhe h auch das richtige Endergebnis laut Spezifikation ist. Dies tun wir durch die Abbruchbedingung.

Wieso sollten wir sie also bei iterativen Algorithmen benötigen (hier zeigten wir, dass es für alle h >= 0 gilt und durch die Abbruchbedingung zum richtigen Zeitpunkt das richtige Endergebnis liefert), bei rekursiven jedoch nicht?

Re: Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Verfasst: 17. Jul 2017 20:51
von SophiaLi1
ttt3 hat geschrieben:
17. Jul 2017 17:38
Durch Beweisen der Invariante wissen wir bspw., dass der rekursive Algorithmus das korrekte Ergebnis für Bäume der Höhen -1 ... h liefert. Wir wissen also, dass jeweils das Ergebnis für diese Bäume korrekt ist.
Du hast dir die Antwort selbst gegeben. Ich empfehle auch einfach nochmal Theorie #2b zu lesen. Wir haben bereits durch den Induktionsbeweis bewiesen, dass der Algorithmus für einen Baum einer beliebigen Höhe das korrekte Ergebnis liefert. Also benötigen wir nur die Invariante, um auszusagen, dass eben das korrekte Ergebnis geliefert wird. Die Abbruchbedingung ist nur für die Terminierung wichtig.

Bei iterativen Algorithmen beweisen wir mit dem Induktionsbeweis zwar die Invariante, aber die lautet bei iterativen Algorithmen nicht, dass der Algorithmus das korrekte Endergebnis liefert. Bei iterativen Algorithmen sagt die Invariante nur etwas über den Zustand von Variablen nach einem Iterationsschritt aus, nicht aber, dass der Algorithmus korrekt ist, was aber bei rekursiven Algorithmen praktischerweise der Fall ist.

Re: Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Verfasst: 19. Jul 2017 10:34
von ttt3
Hm ja, das klingt einleuchtend, aber was wäre mit folgendem hypothetischem Algorithmus:

Wir wollen die Knoten des halben Baumes (also des Baumes der Höhe h/2) zählen.
Variante: h -> h - 1
Abbruchbedingung: h == h/2
Inv.: Für einen Baum der Höhe h funktioniert der Algorithmus korrekt (zählt also alle Elemente)
Ind.anf.: Leere Menge, also 0
Ind.schritt: Der Algorithmus zählt für einen Baum der Höhe h-1 alle Elemente - für einen Baum der Höhe h werden alle weiteren Elemente dazu addiert.

=> Terminierung: aus Variante und Abbruchbedingung
=> Korrektes Endergebnis = ?

Genau diesen Fall meine ich. Du weißt mithilfe der Invariante, dass für jede Höhe h alle Elemente gezählt wurden, aber nicht, nach welcher gewünschten Höhe der Algorithmus terminiert und somit das korrekte Ergebnis (nämlich die Anzahl der Elemente in der "ersten Hälfte" des Baumes).

Re: Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Verfasst: 19. Jul 2017 12:02
von SophiaLi1
Dein Problem ist hier die unterschiedliche Verwendung des Begriffs Höhe. Was ist ein halber Baum? Ein Teilbaum für sich ist wieder ein eigener Baum mit einer eigenen Höhe h - oder eben in Bezug auf den ganzen Baum mit einem geringeren h. Du kannst h nicht in Bezug auf halbe Bäume verwenden. Die Aufgabenstellung
Wir wollen die Knoten des halben Baumes (also des Baumes der Höhe h/2) zählen.
macht also gar keinen Sinn.
Auch die Abbruchbedingung
Abbruchbedingung: h == h/2
ist sinnlos. Zusammengefasst gesagt macht dein Beispiel keinen Sinn.