Fehler im Korrekheitsbeweis von Dijkstra?

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

Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von tmuecksch »

Beim durcharbeiten des Dijkstra Korrektheitsbeweises ist mir etwas aufgefallen:

http://wiki.algo.informatik.tu-darmstad ... p/Dijkstra
  • Im 8. Satz des Korrektheitsbeweises steht: "[…] the subpath of p from s to w is not […]". Das sollte wohl eher ein u sein
  • Im 7. Satz des Korrektheitsbeweises stehet: "On the other hand, the specific choice of v implies[…]". Auch das sollte woh eher ein u sein, denn wir "wählen" u und nicht v, da v durch die Iteration i bereits feststeht und auch nicht mit dem weiteren Satz in korrektem Zusammenhang steht.
  • Im vorletzten Satz steht "[...] and all nodes except for v and w belong to Vi-1". Hier war wohl Pi-1(v) gemeint, da eine Unterscheidung der Menge V zwischen den unterschiedlichen Iterationen ohne Nutzen ist und P besser ins Konzept passt.
Sollte ich das korrekt erkannt haben, würde ich mich über eine Korrektur im Wiki freuen.
Zuletzt geändert von tmuecksch am 4. Sep 2013 16:39, insgesamt 1-mal geändert.

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

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von JannikV »

Hey,

ich will momentan nicht einfach ins Wiki schreiben, da die Seiten ja eigentlich bis zur Klausur eingefroren sind. Die Liste der verbindlichen Wiki Seiten bezieht sich ja auf eine konkrete Version.

Natürlich sollen trotzdem Fehler korrigiert werden. Melde dich dazu am besten mal beim Professor. Der kann dann entscheiden ob die Änderung trotzdem durchgeführt werden soll und ggf. eine Ankündigung bzgl. der Änderung der verbindlichen Seiten machen.

VG

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

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von tmuecksch »

Hm. Ich habe unserem Prof. am 03.09. eine Mail geschrieben, aber vermutlich ist er momentan zu beschäftigt. Eigentlich interessiert es mich auch nur für meine eigenen Aufzeichnungen ob ich nun Recht habe oder nicht. Daher wäre ich dankbar wenn Du das bestätigen könntest. Außerdem habe ich auch noch nicht verstanden was man unter dem Unterschied ("The difference ...") zweier Pfadmengen zu verstehen hat, denn es wird der Backslash verwendet was ja eigentlich auf Menge A ohne Menge B schließen lässt, aber trotzdem in diesem Kontext falsch zu sein scheint.

Bild

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

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von JannikV »

Hallo,

auf die Schnelle waren ich und ein anderer Tutor nicht ganz sicher. Und momentan habe ich aufgrund zweier anstehender Klausuren nicht die Zeit mir das ganz im Detail anzusehen.

Du kannst aber noch auf die Antwort vom Professor warten, oder mal eine Sprechstunde aufsuchen..
Sorry.

VG

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von Prof. Karsten Weihe »

tmuecksch hat geschrieben: [*] Im 8. Satz des Korrektheitsbeweises steht: "[…] the subpath of p from s to w is not […]". Das sollte wohl eher ein u sein
Ja, danke, ist korrigiert.

tmuecksch hat geschrieben: [*] Im 7. Satz des Korrektheitsbeweises stehet: "On the other hand, the specific choice of v implies[…]". Auch das sollte woh eher ein u sein, denn wir "wählen" u und nicht v, da v durch die Iteration i bereits feststeht und auch nicht mit dem weiteren Satz in korrektem Zusammenhang steht.
Missverständnis: Ich meinte, dass der Algorithmus \(v\) wählt. Ist jetzt so umformuliert, dass das Missverständnis hoffentlich ausgeräumt ist.

tmuecksch hat geschrieben: [*] Im vorletzten Satz steht "[...] and all nodes except for v and w belong to Vi-1".
Das \(V_{i-1}\) war aus einer uralten Version der Seite aus Versehen stehengeblieben, in der ich noch die nicht nach der \(i\)-ten Iteration in \(Q\) befindlichen Knoten zu einer Menge \(V_i\) zusammengefasst hatte. :oops:

Jetzt klarer?

KW

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

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von tmuecksch »

Vielen Dank für Ihre Antwort! Das bringt mich schon einmal ein Stückchen weiter :)
Prof. Karsten Weihe hat geschrieben: Jetzt klarer?
Ja, aber noch nicht ganz :roll:

denn ich habe noch nicht verstanden was man unter dem Unterschied ("The difference ...") zweier Pfadmengen zu verstehen hat, denn es wird der Backslash verwendet was ja eigentlich auf *Menge A ohne Menge B* schließen lässt, aber trotzdem in diesem Kontext falsch zu sein scheint.

Bild

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von Prof. Karsten Weihe »

tmuecksch hat geschrieben: denn ich habe noch nicht verstanden was man unter dem Unterschied ("The difference ...") zweier Pfadmengen zu verstehen hat, denn es wird der Backslash verwendet was ja eigentlich auf *Menge A ohne Menge B* schließen lässt
\(A\setminus B\) nennt man doch die Differenzmenge :!: :?:

tmuecksch hat geschrieben: aber trotzdem in diesem Kontext falsch zu sein scheint.
Warum? :shock:

KW

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

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von tmuecksch »

Prof. Karsten Weihe hat geschrieben:
tmuecksch hat geschrieben: Warum? :shock:
Also ich habe das so aufgefasst, dass der Knoten \(w\) in der \(i\)-ten Iteration abgearbeitet wird. In dieser Iteration steht aber die Länge des kürzesten \((s,w)\)-Pfades schon längst fest. Es ist nur jetzt erst gewiss, dass sie auch die "endgültig kürzeste Länge" (groß Delta) ist und in der i-ten Iteration die von w aus erreichbaren Knoten aktualisiert werden. Das Bedeutet dass spätestens in der \(i-1\)ten Iteration der kürzeste \((s,w)\)-Pfad bereits festeht, sich also die Pfadmengen nicht unterscheiden dürften.
Zuletzt geändert von tmuecksch am 7. Sep 2013 19:11, insgesamt 3-mal geändert.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von Prof. Karsten Weihe »

tmuecksch hat geschrieben: Also ich habe das so aufgefasst, dass der Knoten \(w\) in der \(i\)-ten Iteration abgearbeitet wird.
Nein, \(v\) wird abgearbeitet, \(w\) ist der erste Knoten in \(Q\) auf \(p\).

KW

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

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von tmuecksch »

\(v\) ist doch der letzte Knoten vor w? Also wird er in der \(i-1\)ten Iteration abgearbeitet (oder liegt hier etwas das Missverständnis?)

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von Prof. Karsten Weihe »

tmuecksch hat geschrieben:\(v\) ist doch der letzte Knoten vor w? Also wird er in der \(i-1\)ten Iteration abgearbeitet
Jetzt wäre es hilfreich gewesen, wenn Sie \(v\) oder \(w\) statt "er" geschrieben hätten. :roll: :wink:

Abgearbeitet wird \(v\) in der \(i\)-ten Iteration.

Im letzten Absatz ist \(w\) irgendein Knoten, wobei der letzte Absatz nur für Knoten \(w\) mit \(P_{i-1}(w)\subsetneq P_i(w)\) überhaupt relevant ist. Für alle Knoten \(w\), für die dies gilt, gilt offenbar auch: Sie sind in \(Q\), und es gibt eine Kante \((v,w)\).

Ist die Rolle von \(w\) klarer geworden?

KW

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

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von tmuecksch »

Prof. Karsten Weihe hat geschrieben: Ist die Rolle von \(w\) klarer geworden?

Vielen Dank erstmal, dass Sie mir so viel Geduld entgegen bringen.

Ich denke ich verstehe jetzt worauf dieser Teil des Beweises hinausläuft. Jetzt hänge ich nur noch an der Formulierung "The induction hypothesis says \(\delta (w)\) is the minimum length of all \((s,w)\)-paths in \(P_{i-1}(w)\)".

Wo kommt die denn auf einmal her :shock: Es gibt im Wiki-Dijkstra-Eintrag keine Induktionshypothese... Da bleibe ich immer hängen und verliere den Faden, weil mich das immer wieder verwirrt wo diese Aussage wohl herkommen mag ;)


Vielen Dank
Tobias

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von Prof. Karsten Weihe »

tmuecksch hat geschrieben:Es gibt im Wiki-Dijkstra-Eintrag keine Induktionshypothese...
Doch, die Induktionshypothese ist bei uns generell identisch mit der (tataaa:) Invariante. 8)

In http://christianforst.de/?wpfb_dl=64 finde ich eine interessante Formulierung: "Die Induktionshypothese an sich beinhaltet den zu zeigenden Ausdruck. In der Regel steht er bereits in der Angabe und ihr müsst ihn nur noch abschreiben". Leider finde ich mit google keine exakte Definition des Begriffs Induktionsvoraussetzung. :(

Ich hätte statt dessen auch semantisch äquivalent schreiben können: "Die Behauptung folgt daraus, dass die Invariante für den Fall \(i-1\) nach Voraussetzung schon gilt." Aber "nach Induktionsvoraussetzung" ist nicht nur kürzer, sondern rekurriert auch noch einmal auf das Beweisschema.

KW

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

Re: Fehler im Korrekheitsbeweis von Dijkstra?

Beitrag von tmuecksch »

Ich verstehe...

Vielen Dank für die Mühe! Jetzt kann ich einen Haken an den Dijkstra machen!

Antworten

Zurück zu „Archiv“