Korrektheit der Invariante beweisen

06.06.2013, 12:57

matze9999

Korrektheit der Invariante beweisen

Hallo,
ich habe große Schwierigkeiten die Korrektheit eines Algorithmus zu beweisen und würde das ganze mal ganz gerne an dem Beispiel zu Berechnung der Fakultät durchspielen und benötige dafür eure Hilfe.

code:
1: 2: 3: 4: 5: 6: 7:	i = 1 f = 1 while i <= n f = f*i i = i+1 end while

Invariante: f = (i-1)!

I.A.: $[latex]i = 1 \Rightarrow (1-1)! = 1[/latex]$
I.V.: f = (i-1)! (Invariante)
I.S.: ZZ. i --> i+1
f = (i+1-1)! = i!

Stimmt das so? Wahrscheinlich nicht oder? Mein Problem ist, dass ich gar nicht so richtig weiß, was im Induktionsschritt herauskommen muss, damit ich gezeigt habe, dass die Invariante auch im i+1 Durchlauf der Schleife korrekt ist.

Wäre super, wenn mir das mal jemand erklären könnte.

Vielen Dank

Neue Frage »

Antworten »

Korrektheit der Invariante beweisen

Verwandte Themen