So täuschen Sie die Heuristik „probieren Sie einige Testfälle aus“: Algorithmen, die korrekt erscheinen, aber tatsächlich falsch sind

105

Um zu testen, ob ein Algorithmus für ein Problem korrekt ist, versuchen Sie in der Regel, den Algorithmus für eine Reihe einfacher Testfälle von Hand auszuführen. Versuchen Sie es an einigen Beispiel-Problemfällen, einschließlich einiger einfacher Eckfälle ". Dies ist eine großartige Heuristik: Es ist eine großartige Möglichkeit, viele fehlerhafte Versuche an einem Algorithmus schnell auszumerzen und zu verstehen, warum der Algorithmus nicht funktioniert.

Beim Erlernen von Algorithmen sind einige Schüler jedoch versucht, damit aufzuhören: Wenn ihr Algorithmus an einer Handvoll Beispiele korrekt funktioniert, einschließlich aller Eckfälle, die sie ausprobieren können, kommen sie zu dem Schluss, dass der Algorithmus korrekt sein muss. Es gibt immer einen Studenten, der fragt: "Warum muss ich meinen Algorithmus nachweisen, wenn ich ihn nur an ein paar Testfällen ausprobieren kann?"

Also, wie können Sie die Heuristik "Testfälle ausprobieren" zum Narren halten? Ich suche einige gute Beispiele, um zu zeigen, dass diese Heuristik nicht ausreicht. Mit anderen Worten, ich suche nach einem oder mehreren Beispielen für einen Algorithmus, der auf den ersten Blick korrekt aussieht und die richtige Antwort auf alle kleinen Eingaben ausgibt, die wahrscheinlich von irgendjemandem kommen, aber wo der Algorithmus tatsächlich ist funktioniert nicht Möglicherweise funktioniert der Algorithmus nur bei allen kleinen Eingaben ordnungsgemäß und schlägt nur bei großen Eingaben oder nur bei Eingaben mit einem ungewöhnlichen Muster fehl.

Konkret suche ich:

  1. Ein Algorithmus. Der Fehler muss auf der algorithmischen Ebene liegen. Ich suche keine Implementierungsfehler. (Zum Beispiel sollte das Beispiel zumindest sprachunabhängig sein, und der Fehler sollte sich eher auf algorithmische Belange als auf Software-Engineering- oder Implementierungsprobleme beziehen.)

  2. Ein Algorithmus, den sich jemand einfallen lassen könnte. Der Pseudocode sollte zumindest plausibel korrekt aussehen (z. B. ist Code, der verschleiert oder offensichtlich zweifelhaft ist, kein gutes Beispiel). Bonuspunkte, wenn es sich um einen Algorithmus handelt, den ein Schüler bei der Lösung einer Hausaufgabe oder eines Prüfungsproblems entwickelt hat.

  3. Ein Algorithmus, der mit hoher Wahrscheinlichkeit eine vernünftige manuelle Teststrategie besteht. Es ist unwahrscheinlich, dass jemand, der ein paar kleine Testfälle von Hand ausprobiert, den Fehler entdeckt. Zum Beispiel sollte es unwahrscheinlich sein, dass "QuickCheck von Hand in einem Dutzend kleiner Testfälle simuliert", dass der Algorithmus falsch ist.

  4. Vorzugsweise ein deterministischer Algorithmus. Ich habe viele Studenten gesehen, die dachten, dass "einige Testfälle von Hand versuchen" eine vernünftige Methode ist, um zu überprüfen, ob ein deterministischer Algorithmus korrekt ist, aber ich vermute, die meisten Studenten würden nicht davon ausgehen, dass das Probieren einiger Testfälle eine gute Methode ist, um die Wahrscheinlichkeit zu überprüfen Algorithmen. Bei probabilistischen Algorithmen kann häufig nicht festgestellt werden, ob eine bestimmte Ausgabe korrekt ist. Und Sie können nicht genügend Beispiele manuell ankurbeln, um einen nützlichen statistischen Test der Ausgabeverteilung durchzuführen. Daher würde ich mich lieber auf deterministische Algorithmen konzentrieren, da sie die falschen Vorstellungen der Schüler klarer herausarbeiten.

Ich möchte lehren, wie wichtig es ist, Ihren Algorithmus als korrekt zu beweisen, und ich hoffe, dass ich einige Beispiele wie dieses verwenden kann, um Beweise für die Richtigkeit zu motivieren. Ich würde Beispiele bevorzugen, die relativ einfach und für Studierende zugänglich sind. Beispiele, die schwere Maschinen oder eine Tonne mathematischen / algorithmischen Hintergrunds erfordern, sind weniger nützlich. Außerdem möchte ich keine "unnatürlichen" Algorithmen. Es mag zwar einfach sein, einen seltsamen künstlichen Algorithmus zu konstruieren, um die Heuristik zu täuschen, aber wenn er höchst unnatürlich aussieht oder eine offensichtliche Hintertür hat, die nur dazu dient, diese Heuristik zu täuschen, wird er die Schüler wahrscheinlich nicht überzeugen. Irgendwelche guten Beispiele?

DW
quelle
2
Ich liebe deine Frage, sie hat auch mit einer sehr interessanten Frage zu tun, die ich neulich in Mathematik gesehen habe und die sich darauf bezieht, Vermutungen mit großen Konstanten zu widerlegen. Sie finden es hier
ZeroUltimax
1
Noch ein bisschen graben und ich habe diese beiden geometrischen Algorithmen gefunden.
ZeroUltimax
@ZeroUltimax Sie haben Recht, es ist nicht garantiert, dass sich das Zentrum von 3 nicht-kolinearen Punkten im Inneren befindet. Die schnelle Abhilfe besteht darin, einen Punkt in der Linie zwischen der äußersten linken und der äußersten rechten Ecke zu setzen. Gibt es woanders ein Problem?
InformedA
Die Prämisse dieser Frage erscheint mir in einer Weise seltsam, dass ich Schwierigkeiten habe, mich zurechtzufinden, aber ich denke, es kommt darauf an, dass der beschriebene Prozess für das Algorithmus-Design von Grund auf kaputt ist. Selbst für Studenten, die hier nicht aufhören, ist es zum Scheitern verurteilt. 1> Algorithmus schreiben, 2> Testfälle denken / ausführen, 3a> stoppen oder 3b> als richtig erweisen. Der erste Schritt ziemlich viel hat die Eingangsklassen für den Problembereich werden zu identifizieren. Hieraus ergeben sich Eckfälle und der Algorithmus selbst. (Fortsetzung)
Mr.Mindor
1
Wie unterscheidet man einen Implementierungsfehler formal von einem fehlerhaften Algorithmus? Ihre Frage hat mich interessiert, aber gleichzeitig hat mich die Tatsache gestört, dass die von Ihnen beschriebene Situation eher die Regel als die Ausnahme zu sein scheint. Viele Leute testen, was sie implementieren, haben aber normalerweise immer noch Fehler. Das zweite Beispiel für die am besten bewertete Antwort ist genau ein solcher Fehler.
Babou

Antworten:

70

Ein häufiger Fehler ist meines Erachtens die Verwendung gieriger Algorithmen, was nicht immer der richtige Ansatz ist, aber in den meisten Testfällen funktionieren könnte.

Beispiel: , und eine Zahl , drücken als Summe von : s mit so wenig Münzen wie möglich aus. n n d id1,,dknndi

Ein naiver Ansatz ist es, zuerst die größtmögliche Münze zu verwenden und gierig eine solche Summe zu produzieren.

Zum Beispiel geben die Münzen mit den Werten , und für alle Zahlen zwischen und korrekte Antworten mit Gier, mit Ausnahme der Zahl .5 1 1 14 10 = 6 + 1 + 1 + 1 + 1 = 5 + 565111410=6+1+1+1+1=5+5

Per Alexandersson
quelle
10
Dies ist in der Tat ein gutes Beispiel, insbesondere eines, bei dem sich die Schüler routinemäßig irren. Sie müssen nicht nur bestimmte Münzsätze auswählen, sondern auch bestimmte Werte, damit der Algorithmus nicht funktioniert.
Raphael
2
Lassen Sie mich außerdem sagen, dass die Schüler in diesem Beispiel häufig falsche Beweise haben (mit einigen naiven Argumenten, die bei näherer Betrachtung fehlschlagen), sodass hier mehr als eine Lektion gelernt werden kann.
Raphael
2
Das alte britische Münzsystem (vor der Dezimalisierung von 1971) war dafür ein echtes Beispiel. Ein gieriger Algorithmus zum Auszählen von vier Schilling würde eine Halbkrone (2½ Schilling), eine Ein-Schilling-Münze und einen Sechs-Pence (½ Schilling) verwenden. Für die optimale Lösung werden jedoch zwei Gulden (jeweils 2 Schilling) verwendet.
Mark Dominus
1
In der Tat scheinen in vielen Fällen gierige Algorithmen vernünftig, funktionieren aber nicht - ein weiteres Beispiel ist das maximale bipartite Matching. Auf der anderen Seite gibt es auch Beispiele, bei denen es so aussieht, als ob ein gieriger Algorithmus nicht funktionieren sollte, aber es funktioniert: maximaler Spanning Tree.
JKFF
62

Ich erinnerte mich sofort an ein Beispiel von R. Backhouse (dies könnte in einem seiner Bücher gewesen sein). Anscheinend hatte er einen Programmierauftrag vergeben, bei dem die Schüler ein Pascal-Programm schreiben mussten, um die Gleichheit von zwei Zeichenfolgen zu testen. Eines der von einem Studenten eingereichten Programme war das folgende:

issame := (string1.length = string2.length);

if issame then
  for i := 1 to string1.length do
    issame := string1.char[i] = string2.char[i];

write(issame);

Wir können das Programm nun mit folgenden Eingaben testen:

"Universität" "Universität" True; okay

"course" "course" True; okay

"" " True; okay

"Universität" "Kurs" False; okay

"Vorlesung" "Kurs" False; okay

"Genauigkeit" "Genauigkeit" False, OK

All dies scheint sehr vielversprechend: Vielleicht funktioniert das Programm tatsächlich. Aber ein sorgfältigeres Testen mit "rein" und "wahr" zeigt fehlerhafte Ausgabe. Tatsächlich sagt das Programm "True", wenn die Zeichenfolgen dieselbe Länge und dasselbe letzte Zeichen haben!

Die Tests waren jedoch ziemlich gründlich: Wir hatten Zeichenfolgen mit unterschiedlicher Länge, Zeichenfolgen mit gleicher Länge, aber unterschiedlichem Inhalt und sogar gleichen Zeichenfolgen. Darüber hinaus hatte der Student sogar jede Branche getestet und ausgeführt. Man kann nicht wirklich behaupten, dass das Testen hier nachlässig war - da das Programm in der Tat sehr einfach ist, kann es schwierig sein, die Motivation und Energie zu finden, es gründlich genug zu testen.


Ein weiteres nettes Beispiel ist die binäre Suche. In TAOCP sagt Knuth, dass "obwohl die Grundidee der binären Suche vergleichsweise einfach ist, die Details überraschend schwierig sein können". Anscheinend ist ein Fehler in der Implementierung der binären Suche von Java ein Jahrzehnt lang unbemerkt geblieben. Es war ein Integer-Überlauffehler, der sich nur bei ausreichend großer Eingabe manifestierte. Knifflige Details zu Implementierungen der binären Suche werden auch von Bentley in dem Buch Programming Pearls behandelt .

Fazit: Es kann überraschend schwierig sein, sich zu vergewissern, dass ein binärer Suchalgorithmus korrekt ist, wenn man ihn nur testet.

Juho
quelle
9
Natürlich geht der Fehler aus der Quelle hervor (wenn Sie selbst schon einmal etwas Ähnliches geschrieben haben).
Raphael
3
Auch wenn der einfache Fehler im Beispielprogramm behoben ist, ergeben sich aus Strings einige interessante Probleme! Das Umkehren von Strings ist ein Klassiker - die "grundlegende" Art, dies zu tun, besteht darin, einfach die Bytes umzukehren. Dann kommt die Kodierung ins Spiel. Surrogate dann (normalerweise zweimal). Das Problem ist natürlich, dass es keine einfache Möglichkeit gibt, formal zu beweisen, dass Ihre Methode korrekt ist.
Ordentliche
6
Vielleicht interpretiere ich die Frage völlig falsch, aber dies scheint eher ein Fehler in der Implementierung als ein Fehler im Algorithmus selbst zu sein.
Mr.Mindor
8
@ Mr.Mindor: wie können Sie feststellen, ob der Programmierer einen korrekten Algorithmus aufgeschrieben und dann falsch implementiert hat oder einen falschen Algorithmus aufgeschrieben und dann korrekt implementiert hat (ich zögere, "richtig" zu sagen!)
Steve Jessop
1
@wabbit Das ist umstritten. Was für Sie offensichtlich ist, ist für einen Studenten im ersten Jahr möglicherweise nicht offensichtlich.
Juho
30

Das beste Beispiel, das mir jemals begegnet ist, ist das Testen der Ursprünglichkeit:

Eingabe: natürliche Zahl p, p! = 2
Ausgabe: ist pa prime oder nicht?
Algorithmus: Berechne 2 ** (p-1) mod p. Wenn result = 1 ist, dann ist p Primzahl, sonst ist p nicht.

Dies funktioniert für (fast) jede Zahl, außer für einige wenige Zählerbeispiele, und man benötigt tatsächlich eine Maschine, um in einem realistischen Zeitraum ein Gegenbeispiel zu finden. Das erste Gegenbeispiel ist 341, und die Dichte der Gegenbeispiele nimmt tatsächlich mit zunehmendem p ab, wenn auch fast logarithmisch.

Anstatt nur 2 als Grundlage für die Potenz zu verwenden, kann man den Algorithmus verbessern, indem man auch zusätzliche, zunehmende kleine Primzahlen als Grundlage verwendet, falls die vorherige Primzahl 1 zurückgibt. Dennoch gibt es ein Gegenbeispiel zu diesem Schema, nämlich die Carmichael-Zahlen ziemlich selten

Franki
quelle
Der Fermat-Primalitätstest ist ein probabilistischer Test, daher ist Ihre Nachbedingung nicht korrekt.
Femaref
5
ofc es ist ein probabilistischer Test, aber die Antwort zeigt (allgemeiner), wie probabilistische Algorithmen, die mit exakten verwechselt werden, eine Fehlerquelle sein können. Weitere
Informationen
2
Das ist ein schönes Beispiel mit einer Einschränkung: Für die praktische Anwendung der mir vertrauten Primalitätstests, nämlich die Erzeugung asymmetrischer kryptografischer Schlüssel, verwenden wir probabilistische Algorithmen! Die Zahlen sind zu groß für genaue Tests (wenn sie nicht wären, wären sie nicht für Krypto geeignet, da die Schlüssel in realistischer Zeit mit brachialer Gewalt gefunden werden könnten).
Gilles
1
Die Einschränkung, auf die Sie sich beziehen, ist praktisch und nicht theoretisch. Erstklassige Tests in Kryptosystemen, z. B. RSA, weisen aus genau diesen Gründen seltene / höchst unwahrscheinliche Fehler auf, was wiederum die Bedeutung des Beispiels unterstreicht. dh in der Praxis wird diese Einschränkung manchmal als unvermeidlich akzeptiert. Es gibt P-Zeit-Algorithmen für Primalitätstests, z. B. AKS, die jedoch für "kleinere" Zahlen, die in der Praxis verwendet werden, zu lange dauern.
vzn
Wenn Sie nicht nur mit 2 p testen , sondern mit einem p für 50 verschiedene Zufallswerte 2 ≤ a <p, wissen die meisten Leute, dass dies wahrscheinlich ist, aber bei Fehlern ist es so unwahrscheinlich, dass es wahrscheinlicher ist, dass eine Fehlfunktion in Ihrem Computer auftritt die falsche antwort. Mit 2 p, 3 p, 5 p und 7 p sind Ausfälle bereits sehr selten.
gnasher729
21

Hier ist eine, die mir von Google-Vertretern auf einer Tagung, an der ich teilgenommen habe, gezeigt wurde. Es wurde in C codiert, funktioniert aber auch in anderen Sprachen, die Verweise verwenden. Es tut mir leid, dass Sie auf [cs.se] codieren müssen, aber es ist das einzige Beispiel dafür.

swap(int& X, int& Y){
    X := X ^ Y
    Y := X ^ Y
    X := X ^ Y
}

Dieser Algorithmus funktioniert für alle Werte für x und y, auch wenn sie denselben Wert haben. Es wird jedoch nicht funktionieren, wenn es als Swap (x, x) aufgerufen wird. In dieser Situation hat x den Wert 0. Nun, dies könnte Sie nicht zufriedenstellen, da Sie diese Operation mathematisch als korrekt beweisen können, diesen Kantenfall jedoch immer noch vergessen.

ZeroUltimax
quelle
1
Dieser Trick wurde im Unterhand-C-Wettbewerb verwendet, um eine fehlerhafte RC4-Implementierung zu erstellen . Dass Artikel wieder zu lesen, ich habe gerade bemerkt , dass dieser Hack wahrscheinlich von @DW vorgelegt wurde
CodesInChaos
7
Dieser Fehler ist in der Tat subtil - aber der Fehler ist sprachspezifisch, es handelt sich also nicht wirklich um einen Fehler im Algorithmus. Es ist ein Fehler in der Implementierung. Man könnte sich auch andere Beispiele für Sprachverrücktheiten ausdenken, die es leicht machen, subtile Fehler zu verbergen, aber das war nicht wirklich das, wonach ich suchte (ich suchte etwas auf der Ebene der Abstraktion von Algorithmen). In jedem Fall ist dieser Fehler kein idealer Beweis für den Wert des Beweises. Wenn Sie nicht bereits über Aliasing nachdenken, werden Sie möglicherweise dasselbe Problem übersehen, wenn Sie Ihren "Beweis" für die Richtigkeit aufschreiben.
DW
Deshalb bin ich überrascht, dass dies so hoch gewählt wurde.
ZeroUltimax
2
@DW Das hängt davon ab, in welchem ​​Modell Sie den Algorithmus definieren. Wenn Sie zu einer Ebene zurückkehren, in der Speicherreferenzen explizit angegeben sind (und nicht zu dem allgemeinen Modell, bei dem keine gemeinsame Nutzung vorausgesetzt wird), ist dies ein Algorithmusfehler. Der Fehler ist nicht wirklich sprachspezifisch, sondern tritt in jeder Sprache auf, die das Teilen von Speicherreferenzen unterstützt.
Gilles
16

Es gibt eine ganze Klasse von Algorithmen, die von Natur aus schwer zu testen sind: Pseudozufallszahlengeneratoren . Sie können nicht einen einzelnen Ausgang testen, sondern müssen (viele) Reihen von Ausgängen mit statistischen Mitteln untersuchen. Abhängig davon, was und wie Sie testen, können Sie möglicherweise nicht zufällige Merkmale übersehen.

Ein berühmter Fall, in dem die Dinge schrecklich schief gelaufen sind, ist RANDU . Es bestand die zu diesem Zeitpunkt verfügbare Prüfung, bei der das Verhalten von Tupeln nachfolgender Ausgaben nicht berücksichtigt wurde . Bereits Dreifache zeigen viel Struktur:

Grundsätzlich deckten die Tests nicht alle Anwendungsfälle ab: Während die eindimensionale Verwendung von RANDU (wahrscheinlich größtenteils) in Ordnung war, konnte sie (auf diese Weise) nicht zum Abtasten dreidimensionaler Punkte verwendet werden.

Richtige Pseudo-Zufallsauswahl ist eine knifflige Angelegenheit. Zum Glück gibt es an manchen Tagen leistungsfähige Testsuiten , z. B. dieharder , die darauf spezialisiert sind, alle uns bekannten Statistiken auf einen vorgeschlagenen Generator zu werfen. Reicht das?

Um fair zu sein, ich habe keine Ahnung, was Sie für PRNGs durchführbar beweisen können.

Raphael
quelle
2
schönes Beispiel, aber im Allgemeinen gibt es keine Möglichkeit zu beweisen, dass PRNG keine Mängel aufweist. Es gibt nur eine unendliche Hierarchie von schwächeren vs. stärkeren Tests. tatsächlich zu beweisen, dass man im engeren Sinne "zufällig" ist, ist vermutlich unentscheidbar (habe ich aber nicht gesehen, dass dies bewiesen ist).
VZN
1
Das ist eine gute Idee von etwas, das schwer zu testen ist, aber RNG sind auch schwer zu beweisen. PRNG sind weniger anfällig für Implementierungsfehler als vielmehr dafür, dass sie schlecht spezifiziert sind. Tests wie Diehard sind für einige Zwecke gut, aber für Krypto kann man Diehard bestehen und trotzdem aus dem Raum gelacht werden. Es gibt kein „nachweislich sicheres“ CSPRNG. Das Beste, was Sie hoffen können, ist zu beweisen, dass AES es auch ist, wenn Ihr CSPRNG defekt ist.
Gilles
@Gilles Ich habe nicht versucht, mich mit Krypto zu befassen, sondern nur mit statistischer Zufälligkeit (ich denke, die beiden haben ziemlich orthogonale Anforderungen). Sollte ich das in der Antwort klarstellen?
Raphael
1
Kryptozufälligkeit impliziert statistische Zufälligkeit. Allerdings gibt es meines Wissens keine mathematisch-formale Definition, abgesehen von dem idealen (und mit dem Konzept eines PRNG, das auf einer deterministischen Turing-Maschine implementiert ist, widersprüchlichen) Begriff der informationstheoretischen Zufälligkeit. Hat die statistische Zufälligkeit eine formale Definition, die über "muss unabhängig von den Distributionen sein, mit denen wir sie testen" hinausgeht?
Gilles
1
@vzn: Was es bedeutet, eine zufällige Folge von Zahlen zu sein, kann auf viele verschiedene Arten definiert werden, aber eine einfache ist "große Komolgorov-Komplexität". In diesem Fall ist es leicht zu zeigen, dass die Bestimmung der Zufälligkeit unentscheidbar ist.
Cody
9

2D lokales Maximum

n×nA

(i,j)A[i,j]

A[i,j+1],A[i,j1],A[i1,j],A[i+1,j]A

0134323125014013

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

O(n2)

AXXA(i,j)X(i,j)(i,j)

AXAX(i,j)A

AA

(i,j)AA(i,j)

n2×n2A(i,j)

T(n)n×nT(n)=T(n/2)+O(n)T(n)=O(n)

Wir haben also folgenden Satz bewiesen:

O(n)n×n

Oder haben wir?

Neal Young
quelle
T(n)=O(nlogn)T(n)=T(n/2)+O(n)
2
Dies ist ein schönes Beispiel! Ich liebe es. Danke. (Ich habe endlich den Fehler in diesem Algorithmus herausgefunden. Aus den Zeitstempeln kann man ablesen, wie lange ich gebraucht habe. Es ist mir zu peinlich, die tatsächliche Zeit zu enthüllen. :-)
DW
1
O(n)
8

Dies sind Beispiele für die Ursprünglichkeit, da sie häufig vorkommen.

(1) Primalität in SymPy. Ausgabe 1789 . Auf einer bekannten Website wurde ein falscher Test durchgeführt, der erst nach 10 ^ 14 fehlschlug. Während die Korrektur korrekt war, wurden lediglich Löcher ausgebessert, anstatt das Problem zu überdenken.

(2) Primalität in Perl 6. Perl6 hat is-prime hinzugefügt, das eine Reihe von MR-Tests mit festen Basen verwendet. Es gibt bekannte Gegenbeispiele, aber sie sind ziemlich umfangreich, da die Standardanzahl der Tests sehr hoch ist (im Grunde genommen wird das eigentliche Problem durch Leistungseinbußen ausgeblendet). Dies wird in Kürze behoben.

(3) Primalität in FLINT. n_isprime () gibt true für Composites zurück , da behoben. Grundsätzlich das gleiche Problem wie bei SymPy. Mit der Feitsma / Galway-Datenbank von SPRP-2-Pseudoprimes auf 2 ^ 64 können wir diese nun testen.

(4) Perls Mathematik :: Primalität. is_aks_prime ist kaputt . Diese Sequenz scheint vielen AKS-Implementierungen ähnlich zu sein - viel Code, der entweder versehentlich funktioniert hat (z. B. in Schritt 1 verloren gegangen ist und das Ganze durch die Testabteilung erledigt hat) oder bei größeren Beispielen nicht funktioniert hat. Leider ist AKS so langsam, dass es schwer zu testen ist.

(5) Paris Version vor 2.2 ist_prime. Math :: Pari Ticket . Es wurden 10 zufällige Basen für MR-Tests verwendet (mit festem Startwert anstelle von GMPs festem Startwert bei jedem Aufruf). Es zeigt an, dass 9 ungefähr 1 von 1 Millionen Anrufen ist. Wenn Sie die richtige Zahl auswählen, kann dies relativ häufig zum Scheitern führen, die Zahlen werden jedoch spärlicher, sodass in der Praxis nicht viel davon zu sehen ist. Sie haben seitdem den Algorithmus und die API geändert.

Das ist nicht falsch, aber es ist ein Klassiker der Wahrscheinlichkeitstests: Wie viele Runden geben Sie beispielsweise mpz_probab_prime_p? Wenn wir es 5 Runden geben, sieht es sicher so aus, als ob es gut funktioniert - Zahlen müssen einen Fermat-Test zur Basis 210 und dann 5 vorgewählte Miller-Rabin-Tests zur Basis bestehen. Sie werden kein Gegenbeispiel finden, bis Sie 3892757297131 (mit GMP 5.0.1 oder 6.0.0a) gefunden haben. Sie müssten also viele Tests durchführen, um es zu finden. Aber es gibt Tausende von Gegenbeispielen unter 2 ^ 64. Also erhöhen Sie die Zahl weiter. Wie weit? Gibt es einen Gegner? Wie wichtig ist eine richtige Antwort? Verwechseln Sie zufällige Basen mit festen Basen? Wissen Sie, welche Eingabegrößen Sie erhalten?

1016

Diese sind recht schwer richtig zu testen. Meine Strategie umfasst offensichtliche Komponententests sowie Randfälle und Beispiele für Fehler, die vor oder in anderen Paketen aufgetreten sind, Tests im Vergleich zu bekannten Datenbanken, sofern dies möglich ist (z. B. wenn Sie einen einzelnen Base-2-MR-Test durchführen, haben Sie das rechnerisch Unmögliche reduziert Aufgabe des Testens von 2 ^ 64 Zahlen bis zum Testen von etwa 32 Millionen Zahlen) und schließlich viele randomisierte Tests unter Verwendung eines anderen Pakets als Standard. Der letzte Punkt funktioniert für Funktionen wie Primalität, bei denen es eine ziemlich einfache Eingabe und eine bekannte Ausgabe gibt, aber so einige Aufgaben sind. Ich habe dies verwendet, um sowohl Fehler in meinem eigenen Entwicklungscode als auch gelegentliche Probleme in den Vergleichspaketen zu finden. Aber angesichts des unendlichen Eingaberaums können wir nicht alles testen.

Hier ist ein weiteres Beispiel für den Beweis der Korrektheit. Die BLS75-Methoden und ECPP haben das Konzept eines Primalitätszertifikats. Grundsätzlich können sie, nachdem sie die Suche nach Werten, die für ihre Proofs geeignet sind, abgebrochen haben, diese in einem bekannten Format ausgeben. Man kann dann einen Prüfer schreiben oder ihn von jemand anderem schreiben lassen. Diese laufen im Vergleich zur Erstellung sehr schnell, und jetzt sind entweder (1) beide Codeteile falsch (daher würden Sie andere Programmierer für die Verifizierer bevorzugen) oder (2) die Mathematik hinter der Beweisidee ist falsch. # 2 ist immer möglich, aber diese wurden in der Regel von mehreren Personen veröffentlicht und überprüft (und in einigen Fällen sind sie für Sie einfach genug, um durch sich selbst zu gehen).

Im Vergleich dazu liefern Methoden wie AKS, APR-CL, Trial Division oder der deterministische Rabin-Test keine anderen Ergebnisse als "Prime" oder "Composite". Im letzteren Fall haben wir vielleicht einen Faktor, den wir verifizieren können, aber im ersten Fall haben wir nichts anderes als dieses eine Ausgabebit. Hat das Programm richtig funktioniert? Keine Ahnung.

Es ist wichtig, die Software an mehr als nur ein paar Spielzeugbeispielen zu testen und bei jedem Schritt des Algorithmus einige Beispiele durchzugehen und zu sagen: "Ist es angesichts dieser Eingabe sinnvoll, dass ich in diesem Zustand hier bin?"

DanaJ
quelle
1
Viele davon scheinen entweder (1) Implementierungsfehler zu sein (der zugrunde liegende Algorithmus ist korrekt, aber er wurde nicht korrekt implementiert), die interessant sind, aber nicht den Sinn dieser Frage haben, oder (2) eine absichtliche, bewusste Entscheidung, etwas davon auszuwählen ist schnell und funktioniert meistens, kann aber mit sehr geringer Wahrscheinlichkeit scheitern (für Code, der mit einer zufälligen Basis oder einigen festen / zufälligen Basen getestet wird, würde ich hoffen, dass jeder, der dies tut, weiß, dass er einen Performance-Kompromiss eingeht).
DW
Sie sind beim ersten Punkt richtig - korrekter Algorithmus + Fehler ist nicht der Punkt, obwohl die Diskussion und andere Beispiele sie auch in Konflikt bringen. Das Feld ist mit Vermutungen reif, die für kleine Zahlen arbeiten, aber falsch sind. Für Punkt (2) ist dies für einige zutreffend, aber meine Beispiele Nr. 1 und Nr. 3 waren nicht der Fall - es wurde angenommen, dass der Algorithmus korrekt war (diese 5 Basen geben nachgewiesene Ergebnisse für Zahlen unter 10 ^ 16), dann später entdeckte, dass es nicht war.
DanaJ
Ist dies nicht ein grundlegendes Problem bei Pseudoprimalitätstests?
Asmeurer
Asmeurer, ja in meiner # 2 und der späteren Diskussion über sie. Aber # 1 und # 3 waren beide Fälle, in denen Miller-Rabin mit bekannten Basen verwendet wurde, um deterministisch korrekte Ergebnisse unter einem Schwellenwert zu erhalten. In diesem Fall war also der "Algorithmus" (der den Begriff locker zur Übereinstimmung mit dem OP verwendet) falsch. # 4 ist kein wahrscheinlicher Primetest, aber wie DW betonte, funktioniert der Algorithmus einwandfrei, es ist nur die Implementierung, die schwierig ist. Ich habe es aufgenommen, weil es zu einer ähnlichen Situation führt: Es sind Tests erforderlich, und wie weit gehen Sie über einfache Beispiele hinaus, bevor Sie sagen, dass es funktioniert?
DanaJ
Einige Ihrer Beiträge scheinen zu der Frage zu passen, andere nicht (vgl. Den Kommentar von @ DW). Bitte entfernen Sie die Beispiele (und andere Inhalte), die die Frage nicht beantworten.
Raphael
7

Der Fisher-Yates-Knuth-Shuffling-Algorithmus ist ein (praktisches) Beispiel, zu dem einer der Autoren dieser Website Stellung genommen hat .

Der Algorithmus erzeugt eine zufällige Permutation eines gegebenen Arrays als:

 // To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

ij0ji

Ein "naiver" Algorithmus könnte sein:

 // To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ n-1
       exchange a[j] and a[i]

Wo in der Schleife wird das auszutauschende Element aus allen verfügbaren Elementen ausgewählt. Dies führt jedoch zu einer verzerrten Abtastung der Permutationen (einige sind überrepräsentiert usw.).

Tatsächlich kann man mit einer einfachen (oder naiven) Zählanalyse das Fisher-Yates-Knuth-Mischen herausfinden .

nn!=n×n1×n2..nn1

Das Hauptproblem bei der Überprüfung, ob der Shuffling-Algorithmus korrekt ist oder nicht ( verzerrt oder nicht ), besteht darin, dass aufgrund der Statistik eine große Anzahl von Samples benötigt wird. Der obige Coding-Horror-Artikel erklärt genau das (und mit aktuellen Tests).

Nikos M.
quelle
1
Sehen Sie hier ein Beispiel Korrektheitsbeweis für einen Shuffle - Algorithmus.
Raphael
5

Das beste Beispiel, das ich je gesehen habe, hat mit Collatz-Vermutungen zu tun. Ich war in einem Programmierwettbewerb (mit einem Preisgeld von 500 Dollar auf dem ersten Platz), bei dem eines der Probleme darin bestand, die Mindestanzahl von Schritten zu finden, die erforderlich sind, damit zwei Zahlen dieselbe Zahl erreichen. Die Lösung besteht natürlich darin, abwechselnd in Schritten vorzugehen, bis beide zu etwas gelangen, das zuvor gesehen wurde. Wir erhielten eine Reihe von Zahlen (ich glaube, sie lagen zwischen 1 und 1000000) und sagten, dass die Kollatz-Vermutung auf 2 ^ 64 überprüft worden war, so dass alle Zahlen, die wir erhielten, irgendwann bei 1 konvergieren würden. Ich habe 32-Bit verwendet Ganzzahlen, mit denen Sie die Schritte ausführen können. Es stellt sich heraus, dass es eine undurchsichtige Zahl zwischen 1 und 1000000 (170.000) gibt, die dazu führt, dass eine 32-Bit-Ganzzahl zu gegebener Zeit überläuft. Tatsächlich sind diese Zahlen unter 2 ^ 31 äußerst selten. Wir haben unser System auf RIESIGE Zahlen getestet, die weit über 1000000 liegen, um sicherzustellen, dass kein Überlauf auftritt. Es stellt sich heraus, dass eine viel kleinere Zahl, die wir gerade nicht getestet haben, einen Überlauf verursacht hat. Da ich "int" anstelle von "long" verwendet habe, habe ich nur einen 300-Dollar-Preis statt eines 500-Dollar-Preises erhalten.

Jake
quelle
5

Das Knapsack-0/1- Problem ist eines, von dem fast alle Studenten glauben, dass es mit einem gierigen Algorithmus lösbar ist. Das kommt häufiger vor, wenn Sie zuvor einige gierige Lösungen als Problemversion des Knapsacks anzeigen, in der ein gieriger Algorithmus funktioniert .

Für diese Probleme sollte ich in der Klasse den Proof für Knapsack 0/1 ( dynamische Programmierung ) zeigen, um alle Zweifel zu beseitigen, und auch für die gierige Problemversion. Tatsächlich sind beide Beweise nicht trivial und die Studenten finden sie wahrscheinlich sehr hilfreich. Darüber hinaus enthält CLRS 3ed , Kapitel 16, Seite 425-427 einen Kommentar .

Problem: Dieb rauben ein Geschäft aus und können ein maximales Gewicht von W in ihren Rucksack tragen. Es gibt n Artikel und i-te Artikel wiegen wi und ist vi Dollar wert. Welche Gegenstände sollte der Dieb mitnehmen? seinen Gewinn zu maximieren ?

Rucksack-0/1-Problem : Der Aufbau ist derselbe, aber die Gegenstände dürfen nicht in kleinere Teile zerbrochen werden , sodass der Dieb entweder beschließt , einen Gegenstand zu nehmen oder ihn zu verlassen (binäre Wahl), aber möglicherweise keinen Bruchteil eines Gegenstands nimmt .

Und Sie können von den Schülern einige Ideen oder Algorithmen erhalten, die der gleichen Idee wie das Problem der gierigen Version folgen.

  • Nehmen Sie die Gesamtkapazität des Beutels und setzen Sie so viel wie möglich das wertvollste Objekt ein. Wiederholen Sie diese Methode, bis Sie nicht mehr Objekte einsetzen können, weil der Beutel voll ist oder es kein Objekt mit weniger oder gleichem Gewicht für das Einsetzen in den Beutel gibt.
  • Ein anderer falscher Weg ist zu denken: Setzen Sie leichtere Gegenstände und setzen Sie diese folgenden höchsten zum niedrigsten Preis.
  • ...

Ist es hilfreich für dich? Tatsächlich wissen wir, dass es sich bei dem Münzenproblem um eine Version mit Rucksackproblem handelt. Aber es gibt weitere Beispiele im Wald von Ranzen Problemen, mit gutem Beispiel, was Knapsack 2D (das ist wirklich nützlich , wenn Sie Holz für Make Möbel schneiden wollen , sah ich in einem lokalen aus meiner Stadt), ist es sehr häufig denkt , dass die gierig funktioniert auch hier, aber nicht.

Jonaprieto
quelle
Gierig wurde bereits in der akzeptierten Antwort behandelt , aber insbesondere das Knapsack-Problem ist gut geeignet, um einige Fallen zu stellen.
Raphael
3

Ein häufiger Fehler ist die Implementierung falscher Mischalgorithmen. Siehe Diskussion auf Wikipedia .

n!nn(n1)n

Per Alexandersson
quelle
1
Es ist ein guter Fehler, aber kein gutes Beispiel dafür, wie man die Heuristik der Testfälle täuscht, da das Testen nicht wirklich für einen Mischalgorithmus gilt (es ist zufällig, wie würden Sie es testen? Was würde es bedeuten, wenn ein Testfall fehlschlägt, und Wie würden Sie das am Ausgang erkennen?)
DW
Sie testen es natürlich statistisch. Eine gleichmäßige Zufälligkeit ist weit davon entfernt, dass "irgendetwas in der Ausgabe passieren kann". Wären Sie nicht misstrauisch, wenn ein Programm, das einen Würfel emulieren soll, Ihnen 100 3er hintereinander geben würde?
Per Alexandersson
Wieder spreche ich von der Studentenheuristik "Probiere einige Testfälle von Hand aus". Ich habe gesehen, dass viele Studenten der Meinung sind, dass dies ein vernünftiger Weg ist, um zu überprüfen, ob ein deterministischer Algorithmus korrekt ist, aber ich vermute, sie würden nicht annehmen, dass dies ein guter Weg ist, um zu testen, ob ein Shuffling-Algorithmus korrekt ist (da ein Shuffling-Algorithmus randomisiert ist) Es ist nicht möglich, festzustellen, ob eine bestimmte Ausgabe korrekt ist. In jedem Fall können Sie nicht genügend Beispiele manuell starten, um einen nützlichen statistischen Test durchzuführen. Daher erwarte ich nicht, dass Shuffling-Algorithmen viel dazu beitragen werden, das verbreitete Missverständnis zu beseitigen.
DW
1
@PerAlexandersson: Auch wenn Sie nur ein Shuffle generieren, kann es mit MT mit n> 2080 nicht wirklich zufällig sein. Jetzt ist die Abweichung von den erwarteten Werten sehr gering, also ist es Ihnen wahrscheinlich egal ... aber dies gilt auch, wenn Sie generieren weit weniger als den Zeitraum (wie oben erwähnt).
Charles
2
Diese Antwort scheint von Nikos M. 's ausgefeilterem obsolet gemacht worden zu sein ?
Raphael
2

Pythons PEP450 , mit denen Statistikfunktionen in die Standardbibliothek eingeführt wurden, könnten von Interesse sein. Zur Rechtfertigung einer Funktion, die die Varianz in der Standardbibliothek von Python berechnet, schreibt der Autor Steven D'Aprano:

def variance(data):
        # Use the Computational Formula for Variance.
        n = len(data)
        ss = sum(x**2 for x in data) - (sum(data)**2)/n
        return ss/(n-1)

Das obige scheint bei einem gelegentlichen Test richtig zu sein:

>>> data = [1, 2, 4, 5, 8]
>>> variance(data)
  7.5

Das Hinzufügen einer Konstante zu jedem Datenpunkt sollte die Varianz jedoch nicht ändern:

>>> data = [x+1e12 for x in data]
>>> variance(data)
  0.0

Und Varianz sollte niemals negativ sein:

>>> variance(data*100)
  -1239429440.1282566

Es geht um Zahlen und darum, wie Präzision verloren geht. Wenn Sie maximale Präzision wünschen, müssen Sie Ihre Operationen auf eine bestimmte Weise anordnen. Eine naive Implementierung führt zu falschen Ergebnissen, da die Ungenauigkeit zu groß ist. Das war eines der Themen, um die es in meinem Numerikkurs an der Universität ging.

Christian
quelle
1
n1
2
@Raphael: Obwohl der gewählte Algorithmus fair ist, ist er bekanntermaßen eine schlechte Wahl für Gleitkommadaten.
2
Es geht nicht nur um die Implementierung der Operation, sondern auch darum, wie die Genauigkeit verloren geht. Wenn Sie maximale Präzision wünschen, müssen Sie Ihre Operationen auf eine bestimmte Weise anordnen. Das war eines der Themen, um die es in meinem Numerikkurs an der Universität ging.
Christian
Zusätzlich zu Raffaels präzisem Kommentar ist ein Nachteil dieses Beispiels, dass ich nicht denke, dass ein Beweis der Korrektheit helfen würde, diesen Fehler zu vermeiden. Wenn Sie sich der Feinheiten der Gleitkomma-Arithmetik nicht bewusst sind, können Sie denken, Sie haben dies als richtig erwiesen (indem Sie nachweisen, dass die Formel gültig ist). Es ist daher kein ideales Beispiel, um den Schülern beizubringen, warum es wichtig ist, die Richtigkeit ihrer Algorithmen zu beweisen. Wenn die Schüler dieses Beispiel sahen, besteht mein Verdacht darin, dass sie stattdessen die Lektion "Gleitkomma- / numerisches Rechenmaterial ist schwierig" zeichnen.
DW
1

Dies ist wahrscheinlich nicht ganz das, wonach Sie suchen, aber es ist mit Sicherheit leicht zu verstehen, und das Testen einiger kleiner Fälle, ohne dass andere Überlegungen angestellt werden, führt zu einem falschen Algorithmus.

nn2+n+410<dd divides n2+n+41d<n2+n+41

Vorgeschlagene Lösung :

int f(int n) {
   return 1;
}

n=0,1,2,,39n=40

Dieser Ansatz "Versuche einige kleine Fälle und leite einen Algorithmus aus dem Ergebnis ab" taucht häufig (wenn auch nicht so extrem wie hier) bei Programmierwettbewerben auf, bei denen der Druck besteht, einen Algorithmus zu finden, der (a) schnell zu implementieren ist und (b) ) hat eine schnelle Laufzeit.

Rick Decker
quelle
5
Ich denke nicht, dass dies ein sehr gutes Beispiel ist, da nur wenige Leute versuchen würden, die Teiler eines Polynoms zu finden, indem sie 1 zurückgeben.
Brian S
1
nn3n
Dies könnte insofern relevant sein, als die Rückgabe eines konstanten Werts für Divisoren (oder eine andere Berechnung) das Ergebnis einer falschen algorithmischen Herangehensweise an ein Problem sein kann (z. B. ein statistisches Problem oder die Nichtbehandlung von Kantenfällen des Algorithmus). Die Antwort muss jedoch umformuliert werden
Nikos M.
@NikosM. Heh. Ich habe das Gefühl, dass ich hier ein totes Pferd besiege, aber der zweite Absatz der Frage besagt, dass "wenn ihr Algorithmus an einer Handvoll Beispielen, einschließlich aller Eckfälle, die sie ausprobieren können, richtig funktioniert, dann schließen sie, dass der Algorithmus muss Es gibt immer einen Schüler, der fragt: "Warum muss ich meinen Algorithmus nachweisen, wenn ich ihn nur an ein paar Testfällen ausprobieren kann?" In diesem Fall für die ersten 40 Werte (weit mehr als ein Schüler) wahrscheinlich zu versuchen), Rückkehr 1 ist richtig. Es scheint mir, das ist, was der OP gesucht hat.
Rick Decker
Ok, ja, aber so wie es formuliert ist, ist es trivial (vielleicht typisch korrekt), aber nicht im Sinne der Frage. Müsste noch umformuliert werden
Nikos M.