Was bedeutet es zu sagen, dass ein Algorithmus Sound and Complete ist?

33

Ich hörte verschiedene Interpretationen von Klang und Vollständigkeit . Ich verstehe, dass Vollständigkeit bedeutet, eine Lösung zu finden, wenn es eine gibt. Was bedeutet es , ein Algorithmus heißt Sound .

Was bedeutet es zu sagen, dass ein Algorithmus Sound and Complete ist?

Mutelogan
quelle
Ich schlage vor, Sie überdenken, welche Antwort Sie akzeptiert haben, da eine falsch ist.
Blackjack
Genau das getan :)
mutelogan

Antworten:

49

Dies sind sehr spezifische Begriffe im Zusammenhang mit Logik.

Hier sind einige Ansatzpunkte:

http://en.wikipedia.org/wiki/Soundness

http://en.wikipedia.org/wiki/Completeness_(logic)

Grundsätzlich bedeutet Zuverlässigkeit (eines Algorithmus), dass der Algorithmus keine unwahren Ergebnisse liefert. Wenn ich zum Beispiel einen Sortieralgorithmus habe, der manchmal keine sortierte Liste zurückgibt, ist der Algorithmus nicht korrekt.

Vollständigkeit bedeutet andererseits, dass der Algorithmus alle möglichen Eingaben adressiert und keine verpasst. Wenn mein Sortieralgorithmus also niemals eine unsortierte Liste zurückgeben würde, sondern sich einfach weigern würde, Listen mit der Nummer 7 zu bearbeiten, wäre dies nicht vollständig.

Es ist vollständig und solide, wenn es auf allen Eingaben funktioniert (semantisch gültig in der Welt des Programms) und immer die richtige Antwort erhält.

Erik Dietrich
quelle
Vielen Dank. Ich war wirklich verwirrt darüber, was Solidität bedeutet. Ich bekam mehrere Antworten.
mutelogan
Freut mich, wenn es geholfen hat ... :)
Erik Dietrich
13
Ein Beispiel wäre die binäre Suche. Sie ist gut, aber nicht vollständig. Nicht sortierte Listen können nicht bearbeitet werden.
Malfist
3
@Malfist, aber ist die 'Welt des Programms' nicht nach Listen sortiert?
Andres
1
„Ein Algorithmus verhält sich bei ungültigen Eingaben falsch“ hat keinen Einfluss auf die Richtigkeit oder Vollständigkeit. Daher sind weder binäre Such- noch Vergleichssortierungen relevant - beide Algorithmen sind für gültige Eingaben korrekt und vollständig.
Blaisorblade
15

Ich finde Erik Dietrichs Antwort etwas verwirrend. Folgendes ist besser:

Ein Algorithmus ist gesund , wenn diese Antwort immer dann wahr ist , wenn er eine Antwort zurückgibt. Ein Algorithmus ist vollständig, wenn er garantiert, dass für eine beliebige Eingabe eine korrekte Antwort zurückgegeben wird (oder wenn keine Antwort vorliegt, wird garantiert, dass ein Fehler zurückgegeben wird).

Zwei wichtige Punkte:

  1. Solidität ist eine schwache Garantie. Es verspricht nicht, dass A endet.
  2. Solidität und Vollständigkeit sind verwandte Konzepte. Tatsächlich sind sie das logische Gegenteil voneinander. Dh Soundness sagt, dass wenn eine Antwort zurückgegeben wird, diese Antwort wahr ist. Vollständigkeit besagt, dass eine Antwort wahr ist, wenn sie zurückgegeben wird.

Betrachten Sie als Beispiel einen Sortieralgorithmus A, der als Eingabe eine Liste von Zahlen empfängt. Wir sagen, dass A ein Klang ist, wenn jedes Mal, wenn es ein Ergebnis zurückgibt, das Ergebnis eine sortierte Liste ist. Ebenso sagen wir, dass A vollständig ist, wenn garantiert wird, dass eine sortierte Liste jedes Mal zurückgegeben wird, wenn wir ihr eine Liste mit Zahlen geben.

Daniel
quelle
Warum bist du verwirrt? "Ein Algorithmus ist gesund, wenn diese Antwort immer dann wahr ist, wenn er eine Antwort zurückgibt." bedeutet dasselbe wie "Grundsätzlich bedeutet Zuverlässigkeit (eines Algorithmus), dass der Algorithmus keine unwahren Ergebnisse liefert." Das bedeutet dasselbe. Was Ihre (sehr kurze) Definition der Vollständigkeit betrifft, stimmt sie nicht mit dem Wikipedia-Link überein, und Sie zitieren keinen eigenen Verweis. Ich muss sagen, Eriks Definitionen sind praktischer. Wenn deine korrekt sind, musst du bessere Beweise und mehr Fleisch vorlegen.
itsbruce
1
Nur um zu verdeutlichen, wenn Sie sagen "Vollständigkeit sagt, dass eine Antwort wahr ist, wenn sie zurückgegeben wird", meinen Sie, dass die Antwort "richtig" ist, oder?
Dois
1
"Eine Antwort ist wahr, wenn sie zurückgegeben wird" bedeutet wörtlich dasselbe wie "wenn eine Antwort zurückgegeben wird, ist sie wahr". Antworten können auch nicht "wahr" sein, sondern nur richtig. softwareengineering.stackexchange.com/a/311649/21277 ist korrekter.
Blaisorblade
2

Diese Begriffe stammen aus der Berechnungstheorie und sind daher im Kontext der Berechnungstheorie aussagekräftiger als im Kontext des Software-Engineerings

In den meisten Standardberechnungsmodellen werden Rechenprobleme als Sprachen dargestellt . Eine Sprache ist eine Reihe von Zeichenfolgen. Ein Algorithmus ist also nur ein System oder eine Prozedur, die entscheidet, ob eine bestimmte Zeichenfolge Mitglied einer Sprache ist (indem sie true oder false zurückgibt). In Bezug auf die Softwareentwicklung befasst sich die Berechnungstheorie speziell mit Funktionen, die so aussehen, vorausgesetzt, dass Zeichenfolgen unveränderlich sind:

boolean some_function(string argument){...}

Wir bezeichnen diese Funktion als vollständig, wenn sie für jedes Argument, das Mitglied der Sprache ist, true zurückgibt. Wir nennen es Sound, wenn es für jedes Argument, das kein Mitglied der Sprache ist, false zurückgibt.

Mit anderen Worten, es ist vollständig, wenn es immer true zurückgibt, wenn es true zurückgeben soll, und klingt, wenn es immer false zurückgibt, wenn es false zurückgeben soll.

Wie überträgt sich dies auf andere Arten von Funktionen? Wie sich herausstellt, ist es fast immer möglich, eine beliebige Datenmenge in einen String zu packen und ihn innerhalb der Funktion wiederherzustellen. Die Einschränkung von Argumenttyp und Arität ist also nichts anderes als eine theoretische Vereinfachung. Die Einschränkung des Rückgabetyps ist jedoch wichtiger. Probleme, die ein boolesches Ergebnis erfordern, werden als Entscheidungsprobleme bezeichnet . Viele Berechnungstheorien beinhalten Entscheidungsprobleme. Die Mengen P und NP sind auf Entscheidungsprobleme beschränkt (und NP könnte zumindest ohne diese Einschränkung nicht angemessen definiert werden). Das Stopp-Problem ist ein weiteres Beispiel für ein stark untersuchtes Entscheidungsproblem.

Ich bin der Meinung, dass diese Begriffe nicht außerhalb des Bereichs von Entscheidungsproblemen verallgemeinern, daher ist der Unterschied zwischen ihnen bei der Erörterung einer allgemeinen Funktion nicht wirklich bedeutsam.

Kevin
quelle
-2

Auf der SO gibt es viel bessere Antworten . Grundsätzlich geben Sie einige Datenerfassungs- und Suchkriterien an. Der Sound-Algorithmus fängt nur den Fisch, der den Kriterien entspricht, es können jedoch einige Datenelemente fehlen. Ein vollständiger Algorithmus erzeugt eine Obermenge der angeforderten Ergebnisse, was bedeutet, dass Sie zusätzlich zu den angeforderten Ergebnissen noch etwas Müll erhalten. Sound-Algorithmus ist konservativer.

Der Statistiker würde wahrscheinlich sagen, dass der Klangalgorithmus auf Typ-I-Fehler voreingenommen ist (er akzeptiert nicht die richtigen Kandidaten), während der vollständige Algorithmus auf Typ-II-Fehler voreingenommen ist (um die falschen Kandidaten zu akzeptieren).

Bildbeschreibung hier eingeben

Valentin Tihomirov
quelle