"Nach i>=0 Iterationen" Invariante

Assax
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 2. Dez 2011 10:38

"Nach i>=0 Iterationen" Invariante

Beitrag von Assax »

Hallo,

Ich habe eine Frage dazu, wann i denn hochgesetzt wird und ob die Induction basis schon als Iteration gilt nach der i = 1 ist.

Als Beispiel: Binary search tree find.
Sei der gesuchte Key im root Knoten.
Die Invariante besagt, dass nach i>=0 Iterationen p auf einen Knoten der Ebene i zeigt und in der induction basis wird p auf root initialisiert.
Angenommen nach der Induction basis ist i = 0, dann wäre root ja laut Invariante auf Ebene 0.
In der ersten Iteration wird jetzt laut Induction step terminiert da p.key = K ist, gleichzeitig wird i ja erhöht auf i = 1.
Da der Algorithmus jetzt terminiert und p nicht auf p.next gesetzt wird sind wir bei i=1 aber p immer noch root, wie kann das sein wenn root nach Annahme Ebene 0 war, jetzt aber i = 1 ist, p aber immer noch auf root zeigt und damit auf Ebene 0?

Ähnliche Probleme finden sich auch in anderen Alogrithmen, es geht schon bei Linked list: find los, dort wird im Induction step von i -> i+1 p auch nicht mehr auf p.next gesetzt falls derzeitiges p.key = K ist.

Wird bei Terminierung im induction step i nicht höher gesetzt?
Irgendwie hab ich mich da verheddert und komme nicht mehr rauß, Aufklärung wäre super :D

EDIT: Hab eben noch mal ein bisschen in den Archiven gestörbert und öfter Fragen zu Invarianten gefunden die jedoch in keinem der Threads so wirklich beantwortet wurden.
Oft wird wohl angenommen, dass die Invariante nach der Terminierung nicht stimmen muss, oder, dass i erst nach vollständigem Durchlauf erhöht wird (also nicht wenn im Induction step terminiert wird)
Zum Beispiel hier:
viewtopic.php?f=165&t=26324

Langsam wird der Post echt lang :roll:

Zurück zu „Archiv“