Invariante von remove bei linked und doubly-linked lists

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

Invariante von remove bei linked und doubly-linked lists

Beitrag von robertH »

Hallo zusammen,

wie ich das verstehe kann bei einer linearen Sequenz eine Ausprägung mehrfach vorkommen. So steht im wiki, dass die remove Methode (http://wiki.algo.informatik.tu-darmstad ... r_sequence) einer linearen Sequenz folgendes macht: "returns a Boolean value: true if the multiplicity of K in the sequence is positive; false, otherwise."

Dieses potenzielle Mehrfachvorkommen führt dann aber meines Erachtens dazu, dass die Invariante der remove Methode in der Implementierung der linked und doubly-linked list inkorrekt ist (http://wiki.algo.informatik.tu-darmstad ... st:_remove sowie http://wiki.algo.informatik.tu-darmstad ... st:_remove). Ich will das am Beispiel der linked List erläutern. Die Invariante besagt, dass der Zeiger p nach i Iterationen an Stelle i+1 steht und an den Positionen 1 bis i+1 der zulöschende Wert K nicht vorkommt. Wenn wir aber nun in der Iteration i das Element i+1 löschen und den Nachfolger vorziehen, können wir uns nicht sicher sein, dass dieser Nachfolger nicht ebenfalls die selbe Ausprägung abspeichert und eben dieser Nachfolger ist jetzt am Ende des Algorithmus an Position i+1.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Invariante von remove bei linked und doubly-linked lists

Beitrag von JannikV »

Hi, ich denke du hast recht.
Man könnte vielleicht drum herum kommen, wenn man sagt dass der Algorithmus ja bereits terminiert ist. Dennoch müsste meiner Meinung nach die Invariante dann noch gelten. Von daher stimmt wohl was du sagst.

Am besten Prof. Weihe darauf aufmerksam machen oder warten bis er das liest, damit er das korrigieren kann. (da es ja jetzt verbindliche Versionen der Seiten gibt will ich nicht einfach selbst was ändern ohne dass es jemand mitbekommt)

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

Re: Invariante von remove bei linked und doubly-linked lists

Beitrag von robertH »

Ob die Invariante nach der Terminierung gelten muss oder nicht ist ein interessanter Punkt. Ebenso die Frage welcher Wert i annimmt, wenn der Algorithmus terminiert.

Angenommen die Sequenz besteht aus den drei Zahlen (1,2,2) und wir wollen die 2. Position löschen. Dann zeigt p nach der Initialisierung auf die 1 (Kopf der Liste) und in der ersten Iteration wird dann die erste 2 gelöscht und die neue Liste ist (1,2). Der Zeiger p zeigt aber auch noch weiterhin auf den Kopf der Liste. In der Invarianten heißt es aber, dass p auf die Stelle i+1 zeigt und an den Stellen bis einschließlich i+1 der Wert K=2 nicht vorkommt. Wird hier also die Invariante verletzt oder ist i noch 0, da die erste Iteration nicht "fertig geworden" ist? Im zweiten Falle wäre alles korrekt.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Invariante von remove bei linked und doubly-linked lists

Beitrag von tmuecksch »

robertH hat geschrieben:Ob die Invariante nach der Terminierung gelten muss oder nicht ist ein interessanter Punkt.
Naja. Angenommen der Algorithmus macht 10 Iterationen. Das bedeutet dass nach Abschluss der 10.ten Iteration eine Abbruchbedingung gelten muss. Um die 10.te Iteration abzuschließen muss sie (die Iteration) die Invariante erfüllen. Also ist es logisch nur konsistent, dass dies auch nach Terminierung des Algorithmus der Fall ist.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Invariante von remove bei linked und doubly-linked lists

Beitrag von tmuecksch »

- sorry, double post, das Netz hier spinnt und ich habe wohl zwei Mal geklickt...-
Zuletzt geändert von tmuecksch am 10. Sep 2013 10:31, insgesamt 1-mal geändert.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Invariante von remove bei linked und doubly-linked lists

Beitrag von tmuecksch »

[EDIT:] Folgende Aussage ist falsch, da vernachlässigt wurde dass NACH i≥0 Iterationen die Invariante erfüllt sein muss. Der Vollständigkeit halber, lasse ich diesen Eintrag aber trotzdem stehen...

--- --- ---

Allerdings hast Du trotzdem Recht, dass die Invariante verletzt wird. Das aber ganz allgemein; allein schon im ersten Schritt.

Wir betrachten die LinkedList \(L=(1,2)\) und \(K=2\)
In der Induktionsbasis wird \(p:=first\) gesetzt, da es nicht \(K\) entspricht.
Im Induktionsschritt wird in der ersten Iteration \(p.next\) mit \(K\) verglichen. Hier zeigt aber \(p\) noch immer auf das erste Element, also auf das Element an Stelle 1. Also zeigt \(p\) auf ein Element an der Stelle \(i\) und nicht an Stelle \(i+1\). Gemeint war wohl, dass das zu Prüfende Element sich neben \(p\) an Stelle \(i+1\) befindet.
Zuletzt geändert von tmuecksch am 10. Sep 2013 12:33, insgesamt 3-mal geändert.

derJan2
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 23. Mai 2012 21:37

Re: Invariante von remove bei linked und doubly-linked lists

Beitrag von derJan2 »

tmuecksch hat geschrieben:Allerdings hast Du trotzdem Recht, dass die Invariante verletzt wird. Das aber ganz allgemein
Das stimmt so nicht. Problematisch wird die Invariante erst, wenn der Algorithmus terminiert.

Falls der Algorithmus noch nicht terminiert, dann gilt nach dem Induktionsanfang i=0 und p zeigt auf das i+1=1. Element, so wie es in der Invariante steht. Nach einer beliebigen Iteration i zeigt p auf das i+1. Element, was durch den 3. Schritt des Induction Step sichergestellt wird.

Nun zum Fall der Terminierung: Wenn ich die Notation des Wikis richtig verstanden habe, dann müssen nicht mehr alle Invarianten gelten, wenn in der Induction Basis oder dem Induction Step "terminate the algorithm" steht, da der Algorithmus an dieser Stelle abgebrochen und die Induktion nicht zu Ende geführt wird. Das gibt es aber nur bei wenigen Algorithmen, meistens werden die Iterationen immer bis zum Ende ausgeführt und anschließend überprüft, ob die Abbruchbedingung erfüllt ist. Daher gibt es bei den meisten Algorithmen das Problem nicht, ob die Invarianten auch nach der Terminierung noch gelten.

Meiner Meinung nach wäre es schöner / konsistenter, wenn die Invarianten bei jedem Algorithmus auch nach der Terminierung gelten würden. Beispielsweise wäre es bei diesem Algorithmus hier ganz einfach zu lösen, indem man "terminate the algorithm" durch "set p:=p.next and terminate the algorithm" ersetzt. Hiezu könnte sich auch nochmal Prof. Weihe äußern.

Gruß, derJan2

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Invariante von remove bei linked und doubly-linked lists

Beitrag von tmuecksch »

derJan2 hat geschrieben:Das stimmt so nicht. Problematisch wird die Invariante erst, wenn der Algorithmus terminiert.
Du hast Recht. Es heißt ja auch NACH \(i\geq 0\) Iterationen ist die Invariante XY erfüllt.

Antworten

Zurück zu „Archiv“