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?
algorithms
terminology
Mutelogan
quelle
quelle
Antworten:
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.
quelle
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:
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.
quelle
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:
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.
quelle
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).
quelle