Schleifeninvariante < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Suchproblem:
Eingabe: Eine Sequenz von n Zahlen A = <a1,a2,...,an> und Wert v.
Ausgabe: Ein Index i mit v = A[i], falls v in A vorkommt, sonst den Wert NIL.
Aufgabe:
- Programm in Pseudocode für die lineare Suche, die eine Sequenz nach v durchsucht.
- Beweis der Korrektheit unter Verwendung der Schleifeninvariante |
Hallo!
Für die Aufgabe habe ich den folgenden Pseudocode erstellt:
Suche(A,v)
i <- 1
j <- 0
while(j=0 und i [mm] \le [/mm] länge[A]
do if(A[i] = v)
j <- 1
i <- i+1
if(j [mm] \not= [/mm] 0)
return i-1
else
return NIL
Was ist hier wohl die Schleifeninvariante? Der Vergleich if(A[i] = v) und der wert j, der anzeigen soll, ob v in A gefunden wurde?
Und wenn ja, ist folgender Beweis der Korrektheit richtig?:
Initialisierung:
Vor der ersten Iteration der while-Schleife ist der Wert der Laufvariable i = 1.
Die Variable j hat zu diesem Zeitpunkt den Wert 0, dh. der Wert v ist trivialer Weise in A noch nicht gefunden worden, da ja schließlich kein Vergleich stattfand.
Fotsezung:
Der Ausführungsblock der while-Schleife arbeitet so, dass v jeweils mit A[i+1], A[i+2], A[i+3] usw verglichen wird, bis ein A[k] aus A = <a1, a2, ... an> gefunden wird, für das gilt v = A[k].
Terminierung:
Die Schleife endet, sobald ein A[i] aus A gefunden worden ist, für das gilt: A[i] = v. Ist dies der Fall, so nimmt die Var. j den Wert 1 an.
Der gesuchte Index ist in dem Fall dann i-1.
Die Schleife endet aber auch, wenn kein A[i] gefunden worden ist, für das gilt: A[i] = v, und zwar dann, wenn i = n + 1. In diesem Fall bleibt j = 0.
Was sagt ihr dazu? - Bin für jede Kritik dankbar.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:20 Sa 21.02.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
