Formal Überprüfung der Richtigkeit eines Algorithmus

StackOverflow https://stackoverflow.com/questions/2149562

Frage

Zunächst einmal ist dies nur möglich, auf Algorithmen, die keine Nebenwirkungen haben?

Zweitens, wo könnte ich lernen über diesen Prozess, jede guten Bücher, Artikel, etc.?

War es hilfreich?

Lösung

COQ ist ein Beweis-Assistent, der richtige ocaml Ausgabe erzeugt. Es ist ziemlich obwohl kompliziert. Ich habe nie zu betrachten es dazu gekommen, aber meine Mitarbeiter begonnen und dann hörte es nach zwei Monaten mit. Es war vor allem, weil er wollte, schneller, Dinge zu erledigen, aber wenn Sie einen Algorithmus, um zu überprüfen, müssen dies könnte eine gute Idee sein.

Hier ist ein Kurs die COQ und Gespräche nutzt über Algorithmen beweisen.
Und hier ist ein Tutorial über wissenschaftliche Arbeiten in COQ zu schreiben.

Andere Tipps

  1. Es ist im Allgemeinen eine Menge leichter , um zu überprüfen / beweisen, Korrektheit, wenn keine Nebenwirkungen beteiligt sind, aber es ist nicht eine absolute Notwendigkeit.
  2. Sie könnten einen Teil der Dokumentation für eine formale Spezifikationssprache aussehen wollen wie Z . Eine formale Spezifikation ist kein Beweis selbst, sondern ist oft die Grundlage für einen.

sind in der Regel Beweise für die Richtigkeit sehr spezifisch für den Algorithmus zur Hand.

Allerdings gibt es mehrere bekannte Tricks, die verwendet werden und wiederverwendet wieder. Zum Beispiel mit rekursiven Algorithmen können Sie verwenden Schleifeninvarianten .

Ein weiterer üblicher Trick reduziert das ursprüngliche Problem zu einem Problem für die Ihre Algorithmus Beweis der Korrektheit leichter zu zeigen, so ist entweder das einfachere Problem zu verallgemeinern oder zeigt, dass das leichte Problem zu einer Lösung des ursprünglichen Problem übersetzt werden kann. Hier ist eine Beschreibung.

Wenn Sie einen bestimmten Algorithmus im Auge haben, können Sie besser machen in der Frage, wie ein Beweis für diesen Algorithmus zu konstruieren, anstatt eine allgemeine Antwort.

kaufen diese Bücher: http://www.amazon.com/Science-Programming -Monographs-Computer / dp / 0387964800

Die Gries Buch, Scientific Programming ist great stuff. Patient, gründlich, abgeschlossen.

Ich denke, dass die Korrektheit eines Algorithmus Überprüfung seiner Konformität Validierung mit einer Spezifikation wäre. Es ist ein Zweig der theoretischen genannt Informatik Formale Methoden was kann das sein, was Sie suchen, wenn Sie müssen so nah Beweis wie möglich zu erhalten. Aus Wikipedia,

  

Formale Methoden sind eine besondere Art   von mathematisch-basierten Techniken für   die Spezifikation, Entwicklung und   Verifikation von Software und Hardware   Systeme

Sie werden die Lage sein, viele Lernressourcen und Tools aus der Vielzahl von Links auf der verlinkten Wikipedia-Seite und aus dem Formal Methods Wiki .

Logik in der Informatik, von Huth und Ryan, gibt einen einigermaßen lesbaren Überblick über moderne Systeme für die Systeme zu überprüfen. Es war einmal Menschen sprachen über Programme richtig erweisen - mit Programmiersprachen, die oder nicht Nebenwirkungen haben können. Der Eindruck, den ich von diesem Buch erhalten und an anderer Stelle ist, dass reale Anwendungen unterschiedlich sind - zum Beispiel beweisen, dass ein Protokoll korrekt ist, oder dass eine Gleitkommaeinheit des Chips korrekt teilen, oder dass eine Sperre freier Routine für verkettete Listen zu manipulieren ist richtig.

ACM Computing Surveys Vol 41 Issue 4 (Oktober 2009) ist eine Sonderausgabe über Software-Verifikation. Es sieht aus wie Sie mindestens eines der Papiere ohne ACM Konto bei der Suche nach „Formale Methoden: Praxis und Erfahrung“ erhalten können.

Das Tool Frama-C , für die Elazar ein Demo-Video in den Kommentaren schon sagt, gibt Sie eine Spezifikationssprache, ACSL , für Funktions Verträge und verschiedene Analysatoren schreiben zur Überprüfung, ob eine C-Funktion erfüllt seinen Vertrag und Sicherheitseigenschaften wie das Fehlen von Laufzeitfehlern.

Eine erweiterte Tutorial, ACSL mit gutem Beispiel , zeigt Beispiele von C tatsächliche Algorithmen angegeben und überprüft werden, und trennen die nebenwirkungsfreie Funktionen aus den effekt Einsen (die nebenwirkungsfreie diejenigen sind als einfacher, und an erster Stelle in dem Lernprogramm). Dieses Dokument ist auch interessant, dass sie nicht von den Designern der Werkzeuge geschrieben wurde es beschreiben, so dass es einen frischen und didaktischen Blick auf diesen Techniken gibt.

Nicht verbunden mit StackOverflow
scroll top