Korrektheitsbeweise Induktionsanfang

hallo6
Erstie
Erstie
Beiträge: 14
Registriert: 4. Mai 2017 10:36

Korrektheitsbeweise Induktionsanfang

Beitrag von hallo6 » 30. Mai 2017 18:22

Guten Tag,

ich habe ein Verständnisschwierigkeiten zu den Korrektheitsbeweisen Iterativ und Rekursiv.

Ich bin mir nicht sicher, wann man mehrere Induktionsanfänge benötigt und wann nicht.
Im Übungsblatt 2B bei FindSearchTree wurde der Fall, dass der erste Knoten gemäß compare gleich ist (Zeile 13-14) nicht als Induktionsanfang betrachtet, obwohl dort keine weiteren Rekursionen ausgeführt werden.
In den offenen Übungsaufgaben widerrum steht bei checkerInnerHave2ChildrenAndKey, dass man auf den Induktionsanfang achten solle. Muss man dort nun als Anfang alle vier Rekursionsanker aufführen oder reicht wieder die Baumhöhe gleich 0 aus?

Vielen Dank im Vorraus

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

Re: Korrektheitsbeweise Induktionsanfang

Beitrag von invariant » 31. Mai 2017 23:00

Hallo,

Fragen zu den Übungsblättern besser in das Forum zu theoretischen Übungsaufgaben.

Dann zu Ihrer Frage:

Der erste Knoten? Meinen Sie damit die Wurzel?
- Das ist an der Stelle nicht nötig, denn das wird im Induktionsschritt behandelt.

Im Beweis den Sie ansprechen, ist ein Blatt nicht der letzte rekursive Aufruf sondern die Kinder dieses Blattes. Diese sind natürlich null und darauf basiert an dieser Stelle der Induktionsanfang.
Hier hat sich allerdings ein kleiner Fehler eingeschlichen:
Ein leerer Baum hat nach unserer Definition Höhe -1, da ist die 0 natürlich fehl am Platz und es müsste -1 hier stehen (wikipedia geschuldet an dieser Stelle ;) ).

Einen Baum mit einer Höhe 0, also einen einzelnen Knoten, können Sie an dieser Stelle auch im Induktionsanfang abhandeln.
Müssen Sie aber nicht, da - zumindest in diesem Algorithmus - Blätter nicht gesondert behandelt werden.

In einem Algorithmus, in dem Blätter gesondert gehandelt werden und in dem der letzte rekursive Aufruf auf dem Blatt ist, wäre es wohl von Vorteil diese im Induktionsanfang zu betrachten.

Ich hoffe das hilft weiter, wenn nicht nochmal nachfragen.

Gruß

hallo6
Erstie
Erstie
Beiträge: 14
Registriert: 4. Mai 2017 10:36

Re: Korrektheitsbeweise Induktionsanfang

Beitrag von hallo6 » 2. Jun 2017 21:54

So wie ich das aus ihrer Argumentation jetzt verstehe ist es also außreichend beim checkerInnerHave2ChildrenAndKey nur den Induktionsanfang Höhe ist 0 zu betrachten?
Die anderen Fälle erfordern ja Höhe 1 und sind somit durch den Induktionsschritt gedeckt?

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

Re: Korrektheitsbeweise Induktionsanfang

Beitrag von invariant » 3. Jun 2017 12:50

Hallo,

ja es sollte ausreichend sein, dass Sie Höhe 0 betrachten. Alle inneren Knoten, also Höhe >= 1 können im Induktionsschritt behandelt werden.

Allerdings sollten Sie darauf achten dass auch Bäume der Höhe -1 korrekt behandelt werden:

Code: Alles auswählen

if(currentTree == null)
	return true;
An dieser Stelle würde es sich anbieten sowohl Höhe 0 als auch Höhe -1 im Induktionsanfang zu benutzen.

Gruß

Antworten

Zurück zu „Archiv“