Ich habe den folgenden Pseudocode für das Problem der Summe der Paare entwickelt:
Geben Sie bei einem Array von ganzen Zahlen und einer ganzen Zahl YES zurück, wenn es in Positionen mit , andernfalls NEIN.
Jetzt sollte ich eine Schleifeninvariante angeben, die zeigt, dass mein Algorithmus korrekt ist. Kann mir jemand einen Hinweis auf eine gültige Schleifeninvariante geben?
PAIRSUM(A,b):
YES := true;
NO := false;
n := length(A);
if n<2 then
return NO;
SORT(A);
i := 1;
j := n;
while i < j do // Here I should state my invariant
currentSum := A[i] + A[j];
if currentSum = b then
return YES;
else
if currentSum < b then
i := i + 1;
else
j := j – 1;
return NO;
algorithms
proof-techniques
loop-invariants
Forrest Gump
quelle
quelle
A
der Sortierung ab. 2)i
undj
wechseln Sie die Rollen am Ende der Schleife je nach Eingang. 3) Die Anzahl der Schleifenausführungen hängt von der Eingabe ab.Antworten:
Erste Vereinfachung: Dieser Algorithmus kann durch Inspektion nicht JA sagen, wenn dies nicht der Fall sein sollte, da das Sagen von JA unmittelbar nach einem Test erfolgt, bei dem überprüft wird, ob die Summe an den aktuellen Positionen istb .
Zweite Vereinfachung: Es endet immer, dai und j Bewegen Sie sich monoton nach oben und unten, und man bewegt sich immer. Somit werden sie schließlich gleich und die Schleife endet.
Nehmen wir also an, dass diese Antwort JA lautet undx und y sind die Indizes, an denen wir nach dem Sortieren interessiert sind x so klein wie möglich und dann y so groß wie möglich (wir können mehrere mögliche Paare mit der richtigen Summe haben). Hier ist die Invariante:
Wenni=x und j=y Dann stoppt der Algorithmus und sagt JA. Die Schleifeninvariante ist zu Beginn trivial und auch dann triviali<x und j>y . Doch wenni=x , und j>y , da das Array sortiert ist A[i]+A[j]>b , wegen wie y wurde ausgewählt. Damitj nimmt in allen zukünftigen Iterationen ab, bis es erreicht ist y . Der andere Fall, woj kommt zu y Erstens ist symmetrisch.
Wie oben erwähnt, wird der Algorithmus immer beendet, was bedeutet, dass der Algorithmus tatsächlich JA sagt, also sind wir fertig.
Bearbeiten: Da es bei dieser Frage um das Schreiben von Korrekturen geht, ist hier eine weitere Option, die meiner Meinung nach verwirrender und grobkörniger ist. Ich weiß nicht, ob Tony Hoare zustimmen würde oder nicht.
Hier ist die Invariante: A die Spitze der Schleife,
Auch dies gilt zu Beginn leer. Jetzt überprüfen wir einige Fälle:
Schließlich stellen wir fest, dass die Lücke zwischeni und j wird immer kleiner, so dass sie irgendwann gleich werden müssen, und der Algorithmus stoppt.
Anmerkungen: Dies ist genau das gleiche Argument, aber schwieriger zu befolgen. Sie können auch solche Beweise mit einigen Expertentechniken schreiben:
quelle
Vielleicht so etwas?
Vielleicht ist eine klarere Art, dies auszudrücken, einfach:
Diese Schleifeninvariante ist nützlich, da, wenn die Schleife endet (dh die Beendigungsbedingung erreicht),
A
das sortierte Array mit einem Element vorliegt und wir schließen können, dass kein Elementpaar darin enthalten istA
.Hier ist eine Beweisskizze / Idee für diese Invariante:
A[1...n]
befindet sich ein sortiertes Array undi = 1
,j = n
. Daher ist die Schleifeninvariante nachk = 0
Iterationen des Schleifenkörpers garantiert .k
bis einschließlichk'
.k' + 1
. Es gibt drei Fälle für das Verhalten des Schleifenkörpers während der Iteration, die entsprechenk = k' + 1
:A[i] + A[j] = b
In diesem Fall kehrt die Schleife korrekt zurückYES
und es erfolgt keine Iteration nach dieser Iteration der Schleife.A[i] + A[j] < b
In diesem Fall können wir das kleinste Element vonA
,A[i]
. Um dies zu sehen, ist zu beachten, dass daA[j]
das größte Element in istA
, wenn die Summe davon und eines anderen Elements inA
kleiner als istb
, die Summe dieses anderen Elements und jedes Elements vonA
garantiert auch kleiner als istb
.A[i] + A[j] > b
In diesem Fall können wir das größte Element vonA
,A[j]
. Die Argumentation ist ähnlich wie für den FallA[i] + A[j] < b
.i = j
undA
enthält somit nur ein Element. DaA
jetzt nur ein Element enthalten ist, enthält es trivialerweiseA
nicht zwei Elemente, die summiert werdenb
.Demonstration der Hinlänglichkeit der Schleifeninvariante, um zu zeigen, dass es nach Beendigung der Schleife keine Lösung gibt
Dies befasst sich mit einer Frage, die in den Kommentaren von Raphael aufgeworfen wurde. Hier einige Erläuterungen dazu, warum diese Schleifeninvariante ausreichen sollte.
Damit die Schleife endet, müssen wir haben
i = j
. Beachten Sie auch, dass diese Schleife immer beendet wird, entweder durch korrektes Ausgeben,YES
wenn eine Übereinstimmung gefunden wird, oder durch Entfernen von Array-Elementen, bis nur noch eines übrig ist (entweder durch Inkrementiereni
oder Dekrementierenj
). Dieses Beendigungsargument ist in der obigen Skizze nicht angegeben, sollte jedoch einfach sein.Dax,y (Beachten Sie, dass ich dies als einzigartig interpretiere x,y , da sonst der bereitgestellte Algorithmus falsch ist; überlegen A[x]+A[y]=b und da wir durch die Schleifeninvariante wissen, dass kein Element
i = j
,A
ist ein sortierte Sub - Arrays der Größe ein. Weil kein Array der Größe 1 die Anforderung erfüllt, dass es existiertA = [1]
undb = 2
) woA[k]
, wok != i = j
, zu irgendeinem Element hinzugefügt werden könnteA[k']
, wok' != k
, um eine Summe zu erzielenb
, dies die Beweisidee vervollständigt.Annahmen / Fakten für die Kündigungsbedingung:
i = j
nach der (normalen) Beendigung des Schleifenkörpers, und die Schleife endet immer;i
undj
wenni = j
; In einem Subarray der Größe 1 gibt es keine zwei Indizes.k != i = j
es gibt keine Möglichkeit , hinzuzufügenA[k]
zu einemA[k']
,k != k'
zu erhaltenb
; Wir haben nur Elemente inkrementierti
und dekrementiertj
, dieb
mit keinem Element des ursprünglichen Arrays summiert werden konnten .Bitte helfen Sie mir weiter, wenn mir weiterhin etwas Feines fehlt.
quelle
Es gibt immer unendlich viele gültige Schleifeninvarianten. Der Trick besteht darin, einen zu finden, der ausreicht, um zu beweisen, was Sie über den Algorithmus beweisen möchten, und den Sie beweisen können (normalerweise durch Induktion über die Anzahl der Schleifeniterationen).
Der Nachweis der Richtigkeit dieses Algorithmus besteht aus drei Teilen:
YES
oder zurückgibtNO
, ist diese Ausgabe korrekt.Für die Richtigkeit müssen Sie das beweisen1≤i≤n und 1≤j≤n . Dies sollte besser Teil Ihrer Invariante sein. Angesichts der Schleifenbedingungi<j können Sie dies verdichten 1≤i<j≤n am Eingang in den Schleifenkörper. Diese Bedingung ist nicht erfüllt, wenn der Schleifentest am Ende erreicht ist, aber es kann nützlich sein, dies zu bemerkeni≤j (weil innerhalb des Schleifenkörpers mit i<j , i und j nur ändern durch 1 , die im schlimmsten Fall diese strikte Ungleichung in Gleichheit verwandeln kann).
WannA[i]+A[j]=b ist offensichtlich. Für diesen Teil muss also nichts Besonderes bewiesen werden.
return YES
wird ausgeführt,Wenn die letztei<j ist falsch), müssen Sie das beweisen ∀i,∀j,A[i]+A[j]≠b . Diese Eigenschaft ist im Allgemeinen offensichtlich nicht wahr: Sie gilt nicht, wenn die Antwort lautet (x,y) ist ein vorheriger Wert von (i,j) (dh 1≤x≤i und j≤y≤n und (x,y)≠(i,j) ) dann A[x]+A[y]≠b . Dies sollte besser in der Schleifeninvariante ausgedrückt werden.
return NO
Anweisung ausgeführt wird, bedeutet dies, dass die Schleife normal beendet wurde (und so weiter)YES
. Sie müssen diese Eigenschaft stärken : Sie haben einen Sonderfall, der verallgemeinert werden muss. Dies ist ein typischer Fall einer Eigenschaft, die nur für den Teil des Arrays gilt, der bereits durchlaufen wurde: Die Schleife ist so aufgebaut, dass ifSind wir dort fertig? Nicht ganz; Alles, was wir über die normale Schleifenbeendigung wissen, ist das∀x≤i,∀y≤j,A[x]+A[y]≠b . Was wäre, wenn wir hättenx>i und y≤j , oder x≤i und y>j : Können wir haben A[x]+A[y]≠b ? Ohne weitere Informationen ist das schwer zu sagen. In der Tat sollten wir einige Fälle besser unterscheiden, wennA[x]+A[y]>b und die Fälle, wenn A[x]+A[y]<b . Mit diesen Eigenschaften können wir die Tatsache verwenden, dass das Array sortiert ist, um Fakten über andere Positionen im Array abzuleiten. nur mit≠b Wir haben nichts zu arbeiten. Wir wissen nicht in welche RichtungA[x]+A[y] Lügen für einige zufällige x<i und y>j ;; aber wir wissen, was an der Grenze passiert: wenni wird erhöht, es liegt daran A[i]+A[j] ist zu klein und wenn j wird dekrementiert, weil A[i]+A[j] es ist zu groß. Überlegen Sie, welche Schleifeninvariante dies ausdrücken könnte. Ich werde unten eine Möglichkeit geben.
Beachten Sie, dass diese Eigenschaft Ihnen nicht direkt die gewünschte Bedingung für dieA[x]+A[y]<b und wann A[x]+A[y]>b .
return NO
Anweisung gibt. Sie müssen sich noch ansehen, was im letzten Durchlauf der Schleife passiert ist, oder alternativ eine stärkere Schleifeninvariante nachweisen, die genauer betrachtet, wannSchließlich müssen Sie zur Kündigung eine Beziehung herstelleni und j mit der Anzahl der Iterationen durch die Schleife. Hier ist das einfach: entwederi oder j bewegt sich bei jeder Runde, also j−i nimmt um ab 1 bei jeder Schleifeniteration; Sie müssen keine Schleifeninvariante verwenden, um dies zu beweisen.
Wir haben die folgende Invariante erhalten:
quelle
Es gibt keine narrensichere Möglichkeit, eine hilfreiche Invariante abzuleiten. Beachten Sie, dass das Problem nicht berechenbar ist (andernfalls könnten wir das Stoppproblem lösen). Daher sind Sie mit Heuristiken, die durch Erfahrung geschult wurden, wieder bei Versuch und Irrtum. Siehe Gilles 'Antwort für einen beispielhaften Denkprozess. Im Allgemeinen benötigen Sie zuerst die gewünschte Post-Bedingung (dh die Ausgabespezifikation) und suchen eine Invariante, die dies impliziert (zusammen mit der negierten Schleifenbedingung).
Folgendes funktioniert meiner Meinung nach:
Dass die letzten drei Klauseln tatsächlich von der Schleife beibehalten werden - vorausgesetzt, Sie beenden nicht mit YES, was trivial korrekt ist -, ist mühsam zu zeigen, da sie stark voneinander abhängig sind undi,j kann die Rollen wechseln.
Am Ende bekommen Siei=j Dies ermöglicht es, die letzten beiden Klauseln mit der Tatsache zu kombinieren, dass das letzte Element A[i] summiert sich nicht zu b mit jedem anderen Element. Die Kombination von Elementen von links und rechts ist in Abschnitt 3 ausgeschlossen. Schließlich sind noch zwei Elemente übrigi kann nicht zusammenfassen b wegen Klausel vier und eins, und ähnlich für zwei Elemente Recht von i .
Wenn Sie die Beweise machen, stellen Sie sicher, dass Sie die Regeln der Hoare-Logik genau befolgen .
quelle