Off-by-one-Fehler im Wiki?

MichaelS
Erstie
Erstie
Beiträge: 13
Registriert: 16. Mai 2013 10:50

Off-by-one-Fehler im Wiki?

Beitrag von MichaelS »

Hallo,

eventuell hat sich im Merge-Artikel des Wikis ein kleiner Fehler eingeschlichen: In der vierten Zeile (ab "Auxiliary Data") steht, dass die beiden Indeces i1 und i2 Elemente von {0, ... , |S1| } bzw {0, ... , |S2|} sind. Müsste es aber nicht entweder {1, ... , |S1|} oder {0, ... , |S1|-1} lauten? (Ich weiß, das ist jetzt sehr pingelig on mir :mrgreen: )

Noch eine Frage zur Übung: Sollen wir in den Theorietestaten als Startindex von Sequenzen 0 oder 1 verwenden?

lg und schöne Feiertage, Michael

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

Re: Off-by-one-Fehler im Wiki?

Beitrag von JannikV »

Hey,

die "Pingeligkeit" ist durchaus angebracht. ^^ Bei dem formalen Level, dass das Wiki vorgibt, sollte alles ganz genau und korrekt sein.

In diesem Fall ist es aber schon korrekt ;-)

Indizes von Datenstrukturen fangen hier immer bei 1 an. Trotzdem ist 0 bis |S| richtig.
Die 0 gehört dazu, weil in der Induktionsbasis i = 0 gilt. Wenn du dir die Implementierungen ansiehst fällt auch auf, dass niemals auf S zugegriffen wird, sondern nur auf S[i+1].
Wenn i = |S| wird abgebrochen, d.h. es findet auch kein Zugriff auf S[|S| + 1] statt.
Damit gibt es hier kein Index-out-of-Bounds Problem.

VG

MichaelS
Erstie
Erstie
Beiträge: 13
Registriert: 16. Mai 2013 10:50

Re: Off-by-one-Fehler im Wiki?

Beitrag von MichaelS »

Alles klar, danke für die Antwort :)

sb.
Neuling
Neuling
Beiträge: 8
Registriert: 10. Mai 2013 10:37

Re: Off-by-one-Fehler im Wiki?

Beitrag von sb. »

Hallo,

ich habe eine Verständnisfrage zum Artikel "Pivot partitioning by scanning" des Wikis.

Müsste nicht des besseren Verständnisses wegen bei der Variante statt

$$S[j]<p \text{ for } j\in\{1,\ldots,i_1-1\};\text{ if }i_1<m_1,\text{ it is }S[i_1]\not<p$$

$$S[j]<p \text{ for } j\in\{1,\ldots,i_1-1\};\text{ if }i_1<m_1,\text{ it does not have to be }S[i_1]<p$$

heißen?

Ich habe gerade relativ lange über die das angebliche größer-gleich nachgedacht und kam schließlich zu dem Schluss, dass es das vermutlich gar nicht heißen soll, da es hierfür Gegenbeispiele gibt.

Das gleiche würde dann natürlich auch für die zwei darauf folgenden Items gelten.

Oder habe ich die Bedeutung des Zeichens \(\not<\) nur falsch aufgefasst und es gilt gar nicht \(\not<\Longleftrightarrow\geq\)?

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

Re: Off-by-one-Fehler im Wiki?

Beitrag von Prof. Karsten Weihe »

sb. hat geschrieben: Müsste nicht des besseren Verständnisses wegen bei der Variante
Ich bin momentan etwas verwirrt: Hier oben scheint es Ihnen um zwei äquivalente, aber mglw. unterschiedlich gut verständliche Aussagen zu gehen; weiter unten klingt es hingegen für mich so, als wären beide Aussagen doch nicht äquivalent, sondern eine wahr und eine unwahr :?:

KW

sb.
Neuling
Neuling
Beiträge: 8
Registriert: 10. Mai 2013 10:37

Re: Off-by-one-Fehler im Wiki?

Beitrag von sb. »

Sie haben Recht, meine Formulierung "des besseren Verständnisses wegen" war nicht sonderlich glücklich gewählt.

Mein Problem ist, dass für mich \(\not<\) äquivalent zu \(\geq\) ist, die im Wiki stehende Aussage mit dieser Äquivalenz jedoch (zumindest für mich) keinen Sinn ergibt, da es Gegenbeispiele gibt (z.B. eine von vorneherein komplett sortierte Liste).

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

Re: Off-by-one-Fehler im Wiki?

Beitrag von JannikV »

Kannst du mal ein konkretes Gegenbeispiel angeben, inklusive aller (nötigen) Hilfsvariablen?

sb.
Neuling
Neuling
Beiträge: 8
Registriert: 10. Mai 2013 10:37

Re: Off-by-one-Fehler im Wiki?

Beitrag von sb. »

Eingabeliste: 1, 2, 3, 4
Pivotelement: 3

\(m_1=3,\ m_2=4\)
\(i_1=1,\ i_2=3,\ i_3=4\)

Beginn:
\(i_1\) zeigt auf die Zahl 1, aber laut Wiki gilt \(S[i_1]\not<p\), da \(i_1<m_1\\) (konkret: \(1<3\Longrightarrow 1\not<3\))

1. Schritt:
\(i_1<p\), konkret: \(1<3\), also wird \(i_1\) um 1 erhöht.

Nun zeigt \(i_1\) auf die Zahl 2, aber auch hier gilt laut Wiki \(S[i_1]\not<p\), da \(i_1<m_1\) (konkret: \(2<3\Longrightarrow 2\not<3\\))

In beiden Fällen ist jedoch die Voraussetzung \(S[j]<p\) für alle \(j<i_1\) erfüllt.

Hoffe, dass erklärt mein Verständnisproblem.

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

Re: Off-by-one-Fehler im Wiki?

Beitrag von JannikV »

sb. hat geschrieben:Eingabeliste: 1, 2, 3, 4
Pivotelement: 3

\(m_1=3,\ m_2=4\)
\(i_1=1,\ i_2=3,\ i_3=4\)
HALT :P
\(i_1 = 1\) ist nicht richtig. Du hast Punkt 8 aus der Induktionsbasis vergessen.

VG

sb.
Neuling
Neuling
Beiträge: 8
Registriert: 10. Mai 2013 10:37

Re: Off-by-one-Fehler im Wiki?

Beitrag von sb. »

Danke dir. Dann hat sich das geklärt.

Antworten

Zurück zu „Archiv“