Leistungsstarke Algorithmen, die einfach zu schwer zu implementieren sind - wie können Sie sicher sein, dass sie richtig sind?

9

Ich beziehe mich hier auf die Frage: Leistungsstarke Algorithmen, die zu komplex sind, um sie zu implementieren .

Wenn ein Algorithmus leistungsfähig, aber zu komplex für die Implementierung ist, wie können Sie sicher sein, dass der Algorithmus korrekt ist? Ohne Implementierung können Sie den Algorithmus nicht in einem realen Szenario testen, und ein derart komplexer Algorithmus kann Fehler enthalten, die den Algorithmus ungültig machen können.

Das verstehe ich nicht; Wenn Sie die Techniken haben, um die Richtigkeit eines Algorithmus zu beweisen, dann hätten Sie den Algorithmus, um ihn bereits zu implementieren, nicht wahr? Oder wie können wir sicher sein, dass die Prüftechnik korrekt ist?

Es tut mir leid, wenn ich elementar klinge!

Update von Kaveh (hier wiedergegeben, weil das Argument besser ist!):

Wenn Sie die Richtigkeit eines Algorithmus in einem formalen System wie Coq formal beweisen können, können Sie den Algorithmus auch extrahieren (da Sie den Algorithmus im Wesentlichen implementiert haben). Entscheidend ist jedoch, dass wir für die meisten Algorithmen keine formalen Beweise liefern Korrektheit für den Algorithmus verwenden wir informelle Korrektheitsnachweise. Die Beweise können falsch sein, was von Zeit zu Zeit vorkommt, und selbst ein formaler Beweis der Korrektheit wird uns nicht absolut sicher machen, dass der Algorithmus korrekt ist.

ds.algorithms implementation Graviton
quelle
6
Aus diesem Grund verfügen wir über Techniken, um die Richtigkeit von Algorithmen zu beweisen , auch wenn die (korrekte) Implementierung auf einer realen Maschine schwierig ist.
Raphael
9
Ich stimme Raphael zu. Es scheint, dass die Frage auf der Annahme beruht, dass die Richtigkeit eines Algorithmus normalerweise durch Implementierung bewiesen wird, dies ist jedoch nicht der Fall. Das Beweisen der Richtigkeit eines Algorithmus und das Implementieren eines Algorithmus sind völlig verschiedene Dinge, und eines impliziert nicht das andere in beide Richtungen.
Tsuyoshi Ito
8
Einfache Algorithmen mit komplexen Korrektheitsnachweisen - woher wissen Sie, dass sie richtig sind? Nur weil ein Algorithmus an Testbeispielen arbeitet, heißt das nicht, dass er an allen Eingaben funktioniert.
Peter Shor
2
Ich stimme den meisten Kommentaren zu, aber ich denke, ihnen fehlt ein wichtiger Punkt. Wenn Sie die Richtigkeit eines Algorithmus in einem formalen System wie Coq formal beweisen können, können Sie den Algorithmus auch extrahieren (da Sie den Algorithmus im Wesentlichen implementiert haben). Entscheidend ist jedoch, dass wir für die meisten Algorithmen keine formalen Beweise liefern Korrektheit für den Algorithmus verwenden wir informelle Korrektheitsnachweise. Die Beweise können falsch sein, was von Zeit zu Zeit vorkommt, und selbst ein formaler Beweis der Korrektheit wird uns nicht absolut sicher machen , dass der Algorithmus korrekt ist.
Kaveh
5
"Hüten Sie sich vor Fehlern im obigen Code. Ich habe es nur als richtig erwiesen, nicht ausprobiert." ~ Donald Knuth
Lev Reyzin

Antworten:

11

Vor einigen Jahren gab es eine (ziemlich harte) Debatte über ein ähnliches Thema. Alles begann, als sich mehrere komplexe Beweise als falsch herausstellten und einige Forscher Zweifel an der Natur der Beweise aufkommen ließen (nun, ich hätte "nachweisbare Kryptographie" sagen sollen, aber der Allgemeinheit halber habe ich das nicht getan). . Beide Seiten der Kontroverse beschuldigten den anderen, die Konzepte falsch zu verstehen. Hier ist ein Link für weitere Informationen .

Beweise sind unsere (mathematischen) Werkzeuge, um zu beweisen, dass Theoreme / Algorithmen korrekt sind, aber wenn sie zu komplex werden, können wir ausrutschen und beweisen, dass falsche Dinge richtig sind. Das jüngste 100-Seiten-Proof auf P ≠ NP ist ein hervorragendes Beispiel. Dies schließt jedoch die Natur der Beweise nicht aus: Mit ihnen ist nichts falsch.

Ein letzter Punkt: Ich denke, das Studium der Wissenschaftsphilosophie wird uns mehr Einblick geben. (Siehe unter dem angegebenen Link den Punkt " Woher wissen wir, ob ein mathematischer Beweis korrekt ist? ")

MS Dousti
quelle