Schleifeninvariante für einen Algorithmus

7

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.Abi,jAA[i]+A[j]=b

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;
Forrest Gump
quelle
3
Herzlich willkommen! Beachten Sie, dass eine Schleifeninvariante allein nicht beweist, dass Ihr Algorithmus korrekt ist. Es muss eine korrekte Invariante in dem Sinne sein, dass es geeignet ist, die gewünschte Nachbedingung zu beweisen. Beachten Sie auch, dass solche Beweise schwieriger werden, wenn Sie die Schleife vorzeitig verlassen. Es kann eine gute Idee sein, den Algorithmus so umzuschreiben, dass immer die gesamte Schleife verarbeitet wird.
Raphael
1
Sie sehen den Preis dafür, klug zu sein: Beweise werden hart. 1) Korrektheit hängt stark von Ader Sortierung ab. 2) iund jwechseln Sie die Rollen am Ende der Schleife je nach Eingang. 3) Die Anzahl der Schleifenausführungen hängt von der Eingabe ab.
Raphael
1
Ich denke, Sie haben vergessen anzugeben, dass Ihr Array zunehmend sortiert werden sollte, wenn Sie möchten, dass dieser Algorithmus korrekt ist.
Gopi
(oups, Raphael hat bereits gesagt, dass :(, obwohl Sie es noch nicht geändert haben.)
Gopi

Antworten:

5

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 ist b.

Zweite Vereinfachung: Es endet immer, da i und jBewegen 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 und x und y sind die Indizes, an denen wir nach dem Sortieren interessiert sind x so klein wie möglich und dann yso groß wie möglich (wir können mehrere mögliche Paare mit der richtigen Summe haben). Hier ist die Invariante:

  • Zu Beginn der Schleife ix und jy.

Wenn i=x und j=yDann 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 ywurde 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,

  • Wenn s<ialso für jeden x[n], A[s]+A[x]b
  • Wenn t>jalso für jeden x[n], A[x]+A[t]b

Auch dies gilt zu Beginn leer. Jetzt überprüfen wir einige Fälle:

  • Wenn i=j, dann in einem beliebigen Paar von Indizes x und y mindestens einer von x oder y ist kleiner als i oder größer als j. Dies schließt aus, dass die Eingabe ein JA ist. Die Schleife endet und sagt NEIN, also sind wir in guter Verfassung.
  • Angenommen, die Schleife wurde nicht beendet. WennA[i]+A[j]=bDie Antwort lautet JA und der Algorithmus funktioniert.
  • Annehmen A[i]+A[j]b.
  • Unterfall: Wenn es eine gibt jnach Hypothese j<j, so dass A[i]+A[j]=b, dann A[j]<A[j] weil das Array so sortiert wurde A[i]+A[j]>b, was verursacht jverringern. Dies zeigt, dass die Invariante für beibehalten wirdi. Um es zu sehenjBeachten Sie nur, dass wenn es eine gibt x so dass A[x]+A[j]=b, dann x<i, was durch die induktive Hypothese ausgeschlossen ist.
  • Unterfall: Wenn es eine gibt inach Hypothese i>i, so dass A[i]+A[j]=b, dann A[i]>A[i] weil das Array so sortiert wurde A[i]+A[j]<b, was verursacht ierhöhen. Dies zeigt, dass die Invariante für beibehalten wirdj. Um es zu seheniBeachten Sie nur, dass wenn es eine gibt x so dass A[i]+A[x]=b, dann x>j, was durch die induktive Hypothese ausgeschlossen ist.
  • Unterfall: Wenn keiner der beiden anderen Fälle zutrifft, wird die Invariante trivial beibehalten.

Schließlich stellen wir fest, dass die Lücke zwischen i 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:

  • Sagen Sie nicht, was der Algorithmus tut. Wenn die Eingabe ein JA ist, gibt Ihnen der Algorithmus IMMER Zertifizierungsindizes, die so nah wie möglich am Ende sind. Der 2. Beweis verbirgt dies geschickt in einer Fallanalyse.
  • Gib den Dingen keine Namen. Nachdem Sie verborgen haben, was der Algorithmus tut, benennen Sie auch nicht den Haltepunkt.
  • Berücksichtigen Sie keine einfachen Fälle. Dieser Algorithmus funktioniert eindeutig für KEINE Instanzen. Wenn wir das nicht im Voraus bemerken, erhalten wir eine kompliziertere Invariante.
Louis
quelle
Dies ist ein schöner High-Level-Beweis, aber wie verwendet man diese Idee in einem grobkörnigen Beweis im Hoare-Stil? Insbesondere, woher bekommen Siex,yvon (da sie möglicherweise nicht existieren)?
Raphael
@ Louis Ich denke auch, dass Sarkasmus eine schlechte Idee ist, da er leicht missverstanden werden kann. Außerdem haben Sie hier eine Fehlzündung, weil Ihre zweite Version ebenfalls auf hohem Niveau ist. Proofs im Hoare-Stil verwenden lokale Argumente, die zwischen einzelnen Code-Anweisungen wechseln. Ich weiß nicht, ob das OP tatsächlich in diese Richtung gehen wollte; Das habe ich angenommen.
Raphael
3

Vielleicht so etwas?

Enthält nach kIterationen der Schleife A[i...j]ein sortiertes Subarray der Größe n - k, wobei kdie ursprünglichen Elemente, von denen keines bmit einem anderen Element summiert Awurde, entfernt wurden.

Vielleicht ist eine klarere Art, dies auszudrücken, einfach:

Nach kIterationen des Schleifenkörpers, für 0 <= k < n, A[i...j]ist eine sortierte (zusammenhängende) Subarray von A[1...n](deren Elemente in der gleichen Reihenfolge sind und den gleichen Wert wie vor der ersten Iteration) des Körpers Schleife enthält kElemente (dh i + j = k + 1) , so dass A[1...n]enthält eine gewünschtes Elementpaar genau dann A[i...j], wenn dies auch der Fall ist.

Diese Schleifeninvariante ist nützlich, da, wenn die Schleife endet (dh die Beendigungsbedingung erreicht), Adas sortierte Array mit einem Element vorliegt und wir schließen können, dass kein Elementpaar darin enthalten ist A.

Hier ist eine Beweisskizze / Idee für diese Invariante:

  • Vor der Schleife A[1...n]befindet sich ein sortiertes Array und i = 1, j = n. Daher ist die Schleifeninvariante nach k = 0Iterationen des Schleifenkörpers garantiert .
  • Angenommen, die Schleifeninvariante gilt für kbis einschließlich k'.
  • Wir zeigen nun, dass die Schleifeninvariante für gilt k' + 1. Es gibt drei Fälle für das Verhalten des Schleifenkörpers während der Iteration, die entsprechen k = k' + 1:
    • A[i] + A[j] = bIn diesem Fall kehrt die Schleife korrekt zurück YESund es erfolgt keine Iteration nach dieser Iteration der Schleife.
    • A[i] + A[j] < bIn diesem Fall können wir das kleinste Element von A, A[i]. Um dies zu sehen, ist zu beachten, dass da A[j]das größte Element in ist A, wenn die Summe davon und eines anderen Elements in Akleiner als ist b, die Summe dieses anderen Elements und jedes Elements von Agarantiert auch kleiner als ist b.
    • A[i] + A[j] > bIn diesem Fall können wir das größte Element von A, A[j]. Die Argumentation ist ähnlich wie für den Fall A[i] + A[j] < b.
  • Nach Beendigung des Schleifenkörpers i = jund Aenthält somit nur ein Element. Da Ajetzt nur ein Element enthalten ist, enthält es trivialerweise Anicht zwei Elemente, die summiert werden b.

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, YESwenn eine Übereinstimmung gefunden wird, oder durch Entfernen von Array-Elementen, bis nur noch eines übrig ist (entweder durch Inkrementieren ioder Dekrementieren j). Dieses Beendigungsargument ist in der obigen Skizze nicht angegeben, sollte jedoch einfach sein.

Da 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 existiertx,y(Beachten Sie, dass ich dies als einzigartig interpretiere x,y, da sonst der bereitgestellte Algorithmus falsch ist; überlegen A = [1]und b = 2) woA[x]+A[y]=bund da wir durch die Schleifeninvariante wissen, dass kein Element A[k], wo k != i = j, zu irgendeinem Element hinzugefügt werden könnte A[k'], wo k' != k, um eine Summe zu erzielen b, dies die Beweisidee vervollständigt.

Annahmen / Fakten für die Kündigungsbedingung:

  • Die Frage wurde richtig interpretiert, dh x und ysind verschieden; Sie müssen Elemente an verschiedenen Positionen im ursprünglichen Array hinzufügen.
  • i = j nach der (normalen) Beendigung des Schleifenkörpers, und die Schleife endet immer;
  • Es gibt keine zwei unterschiedlichen x und yzwischen iund jwenn i = j; In einem Subarray der Größe 1 gibt es keine zwei Indizes.
  • Durch die Schleifeninvariante, denn k != i = jes gibt keine Möglichkeit , hinzuzufügen A[k]zu einem A[k'], k != k'zu erhalten b; Wir haben nur Elemente inkrementiert iund dekrementiert j, die bmit keinem Element des ursprünglichen Arrays summiert werden konnten .

Bitte helfen Sie mir weiter, wenn mir weiterhin etwas Feines fehlt.

Patrick87
quelle
Ich denke, Ihr Beweis ist korrekt (aber beachten Sie, dass ich ihn nur überflogen habe). Wie bist du darauf gekommen? Dies ist eine Lernübung. Es wäre daher sehr hilfreich zu zeigen, wie Sie Ihre Methode zur Lösung des Problems ausgearbeitet haben.
Gilles 'SO - hör auf böse zu sein'
3

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:

  • Der Algorithmus führt niemals einen falschen Schritt aus. Hier besteht der mögliche Fehler darin, auf ein Array-Element außerhalb der Grenzen des Arrays zuzugreifen.
  • Wenn der Algorithmus YESoder zurückgibt NO, ist diese Ausgabe korrekt.
  • Der Algorithmus wird für jede Eingabe beendet.

Für die Richtigkeit müssen Sie das beweisen 1in und 1jn. Dies sollte besser Teil Ihrer Invariante sein. Angesichts der Schleifenbedingungi<jkönnen Sie dies verdichten 1i<jnam 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 bemerkenij (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).

Wann return YESwird ausgeführt,A[i]+A[j]=bist offensichtlich. Für diesen Teil muss also nichts Besonderes bewiesen werden.

Wenn die letzte return NOAnweisung ausgeführt wird, bedeutet dies, dass die Schleife normal beendet wurde (und so weiter)i<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 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 if(x,y) ist ein vorheriger Wert von (i,j) (dh 1xi und jyn und (x,y)(i,j)) dann A[x]+A[y]b. Dies sollte besser in der Schleifeninvariante ausgedrückt werden.

Sind wir dort fertig? Nicht ganz; Alles, was wir über die normale Schleifenbeendigung wissen, ist dasxi,yj,A[x]+A[y]b. Was wäre, wenn wir hättenx>i und yj, oder xi 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 mitbWir 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 die return NOAnweisung 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, wannA[x]+A[y]<b und wann A[x]+A[y]>b.

Schließlich müssen Sie zur Kündigung eine Beziehung herstellen i und jmit der Anzahl der Iterationen durch die Schleife. Hier ist das einfach: entwederi oder j bewegt sich bei jeder Runde, also ji nimmt um ab 1bei jeder Schleifeniteration; Sie müssen keine Schleifeninvariante verwenden, um dies zu beweisen.

Wir haben die folgende Invariante erhalten:

1ijn(x<i,y<j,A[x]+A[y]b)(x<i,A[x]+A[j]<b)(y>j,A[i]+A[y]>b)
Gilles 'SO - hör auf böse zu sein'
quelle
Und Sie vermissen den Teil, nachdem Sie die Invariante haben. Und wie Sie sagen: "Asortiert "muss Teil der Invariante sein.
Raphael
Oh, und ein kleiner Fehler: i<jist nicht invariant.
Raphael
1
@ Raphael Guter Punkt mit i<j. Es ist eigentlich nicht notwendig, dies durch die Induktion zu tragen, aber als methodischer Punkt ist es wichtig. Ich betrachte die Tatsache, dassAändert sich nicht während der Schleife (und bleibt daher sortiert, aber die Tatsache, dass es sich nicht ändert, ist auch kritisch), um hier offensichtlich zu sein (technisch müsste es auch bewiesen werden, aber ich würde es separat tun und bekommen es zuerst aus dem Weg). Was passiert, nachdem Sie die Invariante haben, ist nicht Teil der Frage; Es ist der Teil der Übung, der eher mechanisch ausgeführt werden kann.
Gilles 'SO - hör auf böse zu sein'
Der folgende Teil zeigt, warum die Invariante ausreicht; aber dann haben Sie das (irgendwie) in Ihrer Ableitung behandelt.
Raphael
2

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:

I= A is sorted and has not been changed 1i,jn ji i<i. j>j. A[i]+A[j]b i<i. b>A[i]+A[j] j>j. b<A[i]+A[j]

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 und i,j kann die Rollen wechseln.

Am Ende bekommen Sie i=j Dies ermöglicht es, die letzten beiden Klauseln mit der Tatsache zu kombinieren, dass das letzte Element A[i] summiert sich nicht zu bmit 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 .

Raphael
quelle
Was ich in Ihrer Antwort vermisse, ist, wie Sie sich für diese Invariante entschieden haben. (Das, und das hast du nicht gezeigti und jsind immer innerhalb der Grenzen des Arrays, aber stört mich nicht, ich bin ein Typ für Software-Korrektheit.)
Gilles 'SO - hör auf böse zu sein'
Guter Punkt zu den Indizes. Solche Bedingungen werden oft vergessen, da sie nicht benötigt werden, um die Nachbedingung anzuzeigen, sondern "nur", um zu zeigen, dass Sie dort ankommen. Es sollte eine Hoare-Regel für Array-Zugriffe geben, die Array-Zugriffe schützt, z{1ichEIN.lenGthP.(X.)}}EIN[ich]]=X.;;{P.(EIN[ich]])}}und zwingt Sie, die Indizes im Auge zu behalten.
Raphael