Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Beitrag von SophiaLi1 » 12. Jul 2017 11:49

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?

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Beitrag von invariant » 14. Jul 2017 12:10

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ß

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Beitrag von SophiaLi1 » 16. Jul 2017 22:40

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?

ttt3
Neuling
Neuling
Beiträge: 9
Registriert: 11. Mai 2015 22:14

Re: Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Beitrag von ttt3 » 17. Jul 2017 17:38

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?

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Beitrag von SophiaLi1 » 17. Jul 2017 20:51

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.

ttt3
Neuling
Neuling
Beiträge: 9
Registriert: 11. Mai 2015 22:14

Re: Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Beitrag von ttt3 » 19. Jul 2017 10:34

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

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: Theorietestat #5: Korrektes Endergebnis bei rekursiven Algorithmen

Beitrag von SophiaLi1 » 19. Jul 2017 12:02

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.

Antworten

Zurück zu „Archiv“