Informatiker Board | Druckvorschau: Korrektheit der Invariante beweisen

Geschrieben von matze9999 am 06.06.2013 um 12:57:

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