Frage zu Linked List / Doubly Linked List

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

Frage zu Linked List / Doubly Linked List

Beitrag von lkbaerenfaenger »

Hi,
ich habe eine Frage zu den Methoden \(insert at position\), zu finden hier:
http://wiki.algo.informatik.tu-darmstad ... t_position
http://wiki.algo.informatik.tu-darmstad ... t_position

:arrow: Man betrachte die Induktionsbasis (egal welche): Hier heißt es: "If \(l = 0\), the element is inserted prior to the head list item, and the algorithm terminates." Ergo: Die Methode wird mit 0 als Parameter aufgerufen, und der einzufügende Key landet an Index 1. OK. Daraus schließe ich, dass bei \(l = 1\) der Key an Index 2 eingefügt wird. OK.

:?: Wenn man nun aber den Induktionsschritt betrachtet, fällt auf, dass das nur funktioniert, wenn innerhalb der ersten Iteration gilt, dass i = 0. Probiert es an einem Beispiel aus. Es funktioniert sonst einfach nicht, da \(i+1<l\) nie gilt, wenn i bei 1 "startet" und \(l = 1\). Simple Frage: Sollte \(i\) innerhalb der ersten Iteration nicht 1 sein? Und warum wird i nirgendwo initialisiert?

Vielen Dank!

robertH
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 29. Apr 2013 13:11

Re: Frage zu Linked List / Doubly Linked List

Beitrag von robertH »

Das ist so ziemlich das gleiche Thema wie bei /viewtopic.php?f=165&t=28796 und einem Haufen von weiteren
Threads, die nie so wirklich beantwortet worden sind.

Es sieht wohl so aus, dass i nur nach einem vollständigen Durchlauf um 1 erhöht wird. Es zählt also die nicht-terminierenden, vollständig bearbeiteten Iterationen.

sbechtel
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 17. Apr 2013 19:13

Re: Frage zu Linked List / Doubly Linked List

Beitrag von sbechtel »

Hallo,

also zuerst mal zu den Grundbegriffen. Die Invariante stellt Kriterien auf, die nach einer Iteration gelten müssen, und zwar auf auch in Abhängigkeit der Iteration, wozu der Zähler i eingesetzt wird. Obwohl zwar i in Invariante und Variante verwendet wird, heißt das noch lange nicht, dass i so etwas wie eine Variable wäre, dass man irgendwann mal definieren müsste, oder das man nach Bedarf einfach mal auf 0 setzen kann, obwohl man schon in der ersten Iteration ist.

Nach der 0-ten Iteration heißt so viel wie vor der ersten Iteration. Dieser Zustand wird durch den Induktionsanfang hergestellt und nach dem Induktionsanfang müssen mit dem Wert i=0 alle Invarianten erfüllt sein.

Da p auf ein Element zeigen muss, und der Kopf der Liste nun mal das frühste Element ist, auf das man zeigen kann, so ergibt sich eben, dass p auf das (i+1)-te Element zeigt. Entsprechend ist also das einzig sinnvoll, dass in der ersten Iteration der Pointer auf das zweite Element zeigt, alles andere macht keinen Sinn.

Noch zur Frage wann i erhöht wird. Das geschiet, wenn die Variante durchgeführt wird. Die Variante ist das minimale, was eine Iteration machen muss, sodass sich aus Invariante, Variante & Abbruchbedingung am Ende Korrektheit beweisen lässt. Alles, was im Induktionsschritt on Top auf die Variante kommt, ist dazu da, dass nach der Iteration die Invariante noch eingehalten wird. Aber für den Beweis ist das ja nebensächlich, so lange man davon ausgeht, dass alles noch gilt.

Um also wieder auf das eigentliche Problem zurück zu kommen: Das Problem liegt meiner Ansicht nach im Induktionsanfang. Hier muss der weitere Spezialfall l=1 zusätzlich zu l=0 behandelt werden.

VG Sebastian

Antworten

Zurück zu „Archiv“