search

PrideNoodles / algowiki-pub

1 stars 0 forks source link

Algowiki: Fehler bei "Pivot partitioning by scanning" #7

Open PrideNoodles opened 9 years ago

PrideNoodles commented 9 years ago

Die Variable n wird inkonsistent benutzt: Im Punkt 1.3 der Invariante ist (leicht nachrechenbar) n gleich der Anzahl der Elemente plus 1 Im weiteren Artikel wird n aber scheinbar für die Anzahl der Elemente benutzt.

Ursache könnte ein Fehler in Punkt 1.1 sein: Wenn es dort "m_1 elements less than p" hieße, wäre n überall gleich der Anzahl der Elemente.

PrideNoodles commented 9 years ago

https://github.com/hydranox/foo-pub/issues/141

FHees commented 9 years ago

Gerade nochmal drüber geschaut: Punkt 1.1 ist definitiv korekt. (Sonst funktioniert der Algorithmus nicht weil m_1 und m_2 zu klein sind) Der Fehler ist also entweder in Punkt 1.3 und es muss dort heißen: "n + 1 - m_2 greater than p." (Dann ist n = Anzahl der Elemente) oder an allen anderen Stellen muss "n + 1" durch "n" ersetzt werden.

karweihe commented 9 years ago

Am 7. Mai 2015 um 21:16 schrieb Thomas Lüdecke notifications@github.com:

Die Variable n wird inkonsistent benutzt: Im Punkt 1.3 der Invariante ist (leicht nachrechenbar) n gleich der Anzahl der Elemente plus 1 Im weiteren Artikel wird n aber scheinbar für die Anzahl der Elemente benutzt.

Danke, habe ich in 1.3 korrigiert.

Ursache könnte ein Fehler in Punkt 1.1 sein: Wenn es dort "m_1 elements less than p" hieße

dann wäre der Foliensatz PivotPartitioningSchema nicht mehr konsistent mit dem Wiki, daher habe ich lieber 1.3 korrigiert.

Prof. Karsten Weihe Hochschulstr. 10, 64289 Darmstadt, Germany Phone: +49-6151-16-20870 Fax: +49-6151-16-20873 www.algo.informatik.tu-darmstadt.de

karweihe commented 9 years ago

Habe 1.3 korrigiert, danke!

Am 8. Mai 2015 um 15:43 schrieb FHees notifications@github.com:

Gerade nochmal drüber geschaut: Punkt 1.1 ist definitiv korekt. (Sonst funktioniert der Algorithmus nicht weil m_1 und m2 zu klein sind) Der Fehler ist also entweder in Punkt 1.3 und es muss dort heißen: "n + 1_ - m_2 greater than p." (Dann ist n = Anzahl der Elemente) oder an allen anderen Stellen muss "n + 1" durch "n" ersetzt werden.

— Reply to this email directly or view it on GitHub https://github.com/hydranox/algowiki-pub/issues/7#issuecomment-100237574 .

Prof. Karsten Weihe Hochschulstr. 10, 64289 Darmstadt, Germany Phone: +49-6151-16-20870 Fax: +49-6151-16-20873 www.algo.informatik.tu-darmstadt.de