Wie wird die Schleifeninvariante in diesem Algorithmus zum Finden der Quadratwurzelgrenze erhalten?

Ursprünglich auf math.SE, aber dort unbeantwortet.

Betrachten Sie den folgenden Algorithmus.

u := 0
v := n+1;
while ( (u + 1) is not equal to v) do
   x :=  (u + v) / 2;
   if ( x * x <= n) 
     u := x;
   else
     v := x;
   end_if
end_while 

Dabei sind u, v und n ganze Zahlen und die Divisionsoperation ist eine ganzzahlige Division.

• Erklären Sie, was vom Algorithmus berechnet wird.
• Stellen Sie anhand Ihrer Antwort auf Teil I als Nachbedingung für den Algorithmus eine Schleifeninvariante her und zeigen Sie, dass der Algorithmus beendet wird und korrekt ist.

In der Klasse wurde gefunden, dass die Nachbedingung und die Invariante 0 ≤ u 2 ≤ n < v 2 , u + 1 ≤ v ist . Ich verstehe nicht wirklich, wie die Nachbedingung und die Invarianten erhalten wurden. Ich denke, die Post-Bedingung war u + 1 = $0 \leq u^2 \leq n < (u + 1)^2$$0 \leq u^2 \leq n < v^2, u + 1 \leq v$$u + 1 = v$... was eindeutig nicht der Fall ist. Ich frage mich also, wie die Nachbedingung und Invariante erhalten wurde. Ich frage mich auch, wie die Vorbedingung unter Verwendung der Nachbedingung erhalten werden kann.

Gilles hat Recht, dass die allgemeine Technik darin besteht, nach interessanten Beobachtungen zu fischen.

In diesem Fall können Sie feststellen, dass das Programm eine Instanz der binären Suche ist, da es die folgende Form hat:

while i + 1 != k
  j := strictly_between(i, k)
  if f(j) <= X then i := j
  if f(j) > X then k := j

Dann sind Sie in Ihrem speziellen Stecker nur f, X... in die allgemeinen invariant für binäre Suche. Dijkstra hat eine nette Diskussion über die binäre Suche .

ist in der Tat eine Nachbedingung der while-Schleife (warum ist dies Ihrer Meinung nach „eindeutig“ nicht der Fall?). Dies ist immer der Fall bei einer while-Schleife, die kein: enthält. Wenn die Schleife beendet wird, kann dies nur daran liegen, dass die Schleifenbedingung (hier u + 1 ≠ v ) falsch ist. Es ist nicht das einzige, was wahr sein wird, wenn die Schleife hier beendet wird (dieser Algorithmus berechnet tatsächlich etwas Interessantes, wie Sie in Ihrer Klasse gesehen haben, also sind u = [dieses interessante Ding] und v = [dieses interessante Ding] auch Nachbedingungen ), aber es ist das offensichtlichste.$u+1=v$break$u+1 \neq v$$u = \text{[this interesting thing]}$$v = \text{[this interesting thing]}$

Um andere interessante Eigenschaften zu finden, gibt es kein allgemeines Rezept. Tatsächlich gibt es einen formalen Sinn, in dem es kein allgemeines Rezept gibt, um Schleifeninvarianten zu finden. Das Beste, was Sie tun können, ist, einige Techniken anzuwenden, die nur in einigen Fällen funktionieren, oder im Allgemeinen nach interessanten Beobachtungen zu fischen (was mit zunehmender Erfahrung immer besser funktioniert).

Wenn Sie die Schleife für einige Iterationen mit dem Wert ausführen , wird dies bei jeder Iteration angezeigt:$n$

• entweder springt auf ( u + v ) / 2 ;$u$$(u+v)/2$
• oder springt nach unten zu ( u + v ) / 2 .$v$$(u+v)/2$

$u$$v$$u$$v$$n+1$$0 \le u \le v \le n+1$

$u$$v$$u$$v$$x = u = v$$u$$v$$u < v$$u$$v$$u+1 \le v$

$v = u+1$$u^2 \le n < v^2$$0 \le u^2$$n$$n$$n$

• $u \le x \le v$
• $x^2 \le n$$u$$x$$u^2 \le n$$v$
• $x^2 > n$$v$$x$$n < v^2$$u$

$u^2 \le n < v^2$

$u^2 \le n$$(u+1)^2 > n$$u$$n$