Beispiele für Algorithmen und Beweise, die korrekt erscheinen, aber nicht korrekt sind

In meiner Einführung in den Programmierkurs lernen wir die Methode Initialisierung-Wartung-Beendigung kennen, mit der bewiesen wird, dass ein Algorithmus das tut, was wir von ihm erwarten. Wir mussten jedoch nur beweisen, dass ein Algorithmus, von dem bereits bekannt ist, dass er korrekt ist, korrekt ist. Wir wurden nie gebeten zu zeigen, dass ein Algorithmus nicht korrekt ist.

Gibt es klassische Beispiele für Algorithmen, die korrekt aussehen, aber nicht korrekt sind? Ich suche nach Fällen, in denen der Ansatz der Initialisierung, Wartung und Beendigung etwas erfasst, was die Intuition auf den ersten Blick nicht tut.

ds.algorithms proofs Marin
quelle

Möglicherweise von Interesse: cs.stackexchange.com/q/29475/755

Upvoting, weil ich denke, dass dies eine sehr wichtige pädagogische Frage ist. Es ist etwas außerhalb des Rahmens für cstheory, aber ich kenne keine bessere Plattform dafür, und es gibt viele Algorithmuslehrer in der cstheory-Community. Die meisten Algorithmen-Design-Kurse setzen die Schüler nur korrekten, vorhandenen Algorithmen und Problemen aus, die mit bekannten Techniken leicht zu lösen sind. Dies verstärkt den für Studenten so attraktiven Eindruck, dass man seinem intuitiven Gefühl vertrauen kann, dass ein scheinbar plausibler Algorithmus richtig ist. Ein guter Algorithmus-Design-Kurs sollte das Gegenteil bewirken!

Neal Young

Ich würde gerne eine solche Sammlung haben.

Chandra Chekuri

Antworten:

2D lokales Maximum

Eingabe: 2-dimensionales Array $n \times n$ $A$

Ausgabe: ein lokales Maximum - ein Paar so dass $(i,j)$ $A[i,j]$ keine benachbarte Zelle im Array hat, die einen streng größeren Wert enthält.

(Die benachbarten Zellen sind diejenigen unter , die in dem Array vorhanden sind.) Also zum Beispiel, wenn ist $A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$ $A$

\begin{array}{cccc} 0 & 1 & 3 & 4 \\ 3 & 2 & 3 & 1 \\ 2 & 5 & 0 & 1 \\ 4 & 0 & 1 & 3 \end{array}

$\begin{array}{cccc} 0&1&3&\mathbf{4}\\ \mathbf{3}&2&\mathbf{3}&1\\ 2&\mathbf{5}&0&1\\ \mathbf{4}&0&1&\mathbf{3}\end{array}$

dann ist jede fettgedruckte Zelle ein lokales Maximum. Jedes nicht leere Array hat mindestens ein lokales Maximum.

Algorithmus. Es gibt ein $O(n^2)$ -Zeitalgorithmus: Überprüfen Sie einfach jede Zelle. Hier ist eine Idee für einen schnelleren, rekursiven Algorithmus.

$A$ $X$ $X$ $A$ $(i, j)$ $X$ $(i, j)$ $(i', j')$

$A \setminus X$ $A$ $X$ $(i', j')$ $A'$

$A'$ $A$

$(i', j')$ $A'$ $A'$ $(i', j')$ $\diamond$

$\frac{n}{2}\times\frac{n}{2}$ $A'$ $(i, j)$

$T(n)$ $n\times n$ $T(n) = T(n/2) + O(n)$ $T(n) = O(n)$

Damit haben wir folgenden Satz bewiesen:

$O(n)$ $n\times n$

Oder haben wir?

Neal Young
quelle

Bei der ersten Lesung war der einzige Fehler, den ich entdeckte, die Wiederholungslösung. Ist das der einzige Fehler?

Radu GRIGore

Die Wiederholung ist korrekt. Der Algorithmus ist nicht!

Neal Young

Ah, ja, ich habe mit der Wiederholung einen dummen Fehler gemacht. Ich sehe das Problem: Das Maximum, das Sie beweisen, ist nicht (notwendigerweise) das, was Sie finden. Und was Sie finden, ignoriert das X.

Radu GRIGore

(\begin{matrix} 2 & 1 & 4 & 3 & 3 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 0 & 0 \\ 0 & 1 & 0 & 2 & 3 & 0 & 0 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 3 & 3 & 3 & 2 & 3 & 3 & 3 \\ 0 & 0 & 3 & 2 & 3 & 0 & 0 \\ 0 & 0 & 3 & 2 & 3 & 0 & 0 \end{matrix})

$\begin{pmatrix}2&1&4&3&3&0&0\\1&0&1&2&3&0&0\\0&{\color{red}1}&0&2&3&0&0\\2&2&2&2&2&2&2\\3&3&3&2&3&3&3\\0&0&3&2&3&0&0\\0&0&3&2&3&0&0\end{pmatrix}$

A^{'}

$A'$

A

$A$