Seite 1 von 1

Fibonacci-Zahlen rekursiv

Verfasst: 27. Mär 2017 15:36
von Cologne
Hi !
Wir sitzen gerade am Korrektheitsbeweis zu den Fibonacci-Zahlen (rekursiv)
Wir haben die Invariante folgendermaßen definiert : Für k>=0 Rekursionsschritte sind die Fibonacci Zahlen für (0...k) korrekt gezählt/summiert. -->?
Nun die Uneinigkeit bezüglich des Induktionsschrittes:
Wir nutzen als Basis die Invariante und formulieren den IS folgendermaßen :
-Aufgrund der Induktionshypothese/Invariante müssen für k >=0 Rekursionsschritte die Fibonacci-Zahlen von 0...k korrekt gezählt werden. Damit diese Voraussetzung erfüllt wird, müssen die Fibonacci -Zahlen k-1 ebenfalls korrekt gezählt werden.

Dieser IS lässt uns vermuten, dass wir den Baum von unten nach oben Betrachten, also den Baum im Prinzip in seinem Endzustand betrachten, denn k>= Rekursionsschritte kann man ja nur korrekt berechnen , wenn fib(0) bzw. fib(1) aufgerufen werden.
Mathematisch gesehen macht dieser Induktionsschritt für uns Sinn.

Das Problem entsteht jedoch, wenn wir für den IS den rekursiven Code durchlaufen. Da sich in jedem Rekursionsschritt die Funktion neu aufruft, können wir gar nicht davon ausgehen , dass der unterste Teil des Fib.Baumes bereits ausgegeben wurde. So wissen wir gar nicht , ob auch k-1 Rekursionsschritten die Fib-Zahlen korrekt berechnet wurden, da der Baum noch gar nicht "so weit ist".
Ich hoffe , unser Problem ist einigermaßen zu verstehen. Im Prinzip (so haben wir das Gefühl) sehen wir einen großen Unterschied zwischen der mathematischen Funktionsweise des Baumes und die des Codes von oben nach unten .
Gruß

Re: Fibonacci-Zahlen rekursiv

Verfasst: 30. Mär 2017 19:04
von Prof. Karsten Weihe
Cologne hat geschrieben: Wir sitzen gerade am Korrektheitsbeweis zu den Fibonacci-Zahlen (rekursiv)
Wir haben die Invariante folgendermaßen definiert
Ich würde sie einfach so definieren: Der Aufruf mit n liefert die n-te Fibonacci-Zahl. Probieren Sie es damit!
Cologne hat geschrieben: Für k>=0 Rekursionsschritte sind die Fibonacci Zahlen für (0...k) korrekt gezählt/summiert. -->?
Ich sehe bei dieser Formulierung das Problem, das ich auch in der Vorlesung mehrfach angesprochen hatte: Es führt in Probleme, wenn Sie sich nicht einfach auf einen einzelnen Rekursionsschritt fokussieren, sondern die weiteren Rekursionsschritte quasi "mitzählen" wie bei einer iterativen Implementierung.

KW

Re: Fibonacci-Zahlen rekursiv

Verfasst: 31. Mär 2017 18:04
von Cologne
Vielen Dank !
Mit Ihrer Formulierung, ist es wohl auch nicht mehr nötig, sich Gedanken darum zu machen, "von welchem Ende" man den Baum abarbeitet.
Wir haben uns an der Stelle zu sehr auf die Formulierung von Invarianten für Iterationen beschränkt.
Ich muss dennoch an der Stelle fragen, ob die von mir genannte Invariante falsch oder "schlechter " formuliert war (vielleicht auch bezüglich der Punktevergabe in der Klausur :oops: ).

Re: Fibonacci-Zahlen rekursiv

Verfasst: 31. Mär 2017 18:15
von Prof. Karsten Weihe
Cologne hat geschrieben: Ich muss dennoch an der Stelle fragen, ob die von mir genannte Invariante falsch oder "schlechter " formuliert war (vielleicht auch bezüglich der Punktevergabe in der Klausur :oops: ).
Wenn Sie mit Ihrer Formulierung der Invariante dann beim Beweis klarkommen, dann ist ja alles ok, falls nicht ... :twisted:

KW

Re: Fibonacci-Zahlen rekursiv

Verfasst: 1. Apr 2017 09:08
von Cologne
Alles klar :lol: