Fibonacci-Zahlen rekursiv

Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Cologne
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 4. Jan 2017 17:54

Fibonacci-Zahlen rekursiv

Beitrag von Cologne » 27. Mär 2017 15:36

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ß

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Fibonacci-Zahlen rekursiv

Beitrag von Prof. Karsten Weihe » 30. Mär 2017 19:04

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

Cologne
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 4. Jan 2017 17:54

Re: Fibonacci-Zahlen rekursiv

Beitrag von Cologne » 31. Mär 2017 18:04

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: ).

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Fibonacci-Zahlen rekursiv

Beitrag von Prof. Karsten Weihe » 31. Mär 2017 18:15

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

Cologne
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 4. Jan 2017 17:54

Re: Fibonacci-Zahlen rekursiv

Beitrag von Cologne » 1. Apr 2017 09:08

Alles klar :lol:

Antworten

Zurück zu „AuD: Theoretische Aufgaben“