Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- ef_informatik:sorting_csharp [2022-03-14 20:08] – [Aufgabe 2: Fibonacci dynamisch] sca
+++ ef_informatik:sorting_csharp [2022-03-14 20:26] (aktuell) – sca
@@ Zeile 759: / Zeile 759: @@
 ==== Aufgabe 2: Fibonacci dynamisch ====
-<nodisp1>
+<nodisp 1>
-Das Problem ist, dass die Anzahl Funktionsaufrufe exponentiell steigt. Dadurch ist die Anzahl rekursiver Funktionsaufrufe bereits für Zahlen wie $n=40$ sehr hoch. Dies liegt daran, dass die Fibonacci-Funktion immer wieder für die gleiche Zahl aufgerufen wird. Zum Beispiel wird in der Berechnung für `Fibonacci(42)` insgesamt $102'334'155$ `Fibonacci(3)` berechnet. Das ist nicht sehr effizient!
+++++Theorie|
+Das Problem im Code der vorherigen Aufgabe ist, dass die Anzahl Funktionsaufrufe exponentiell steigt. Dadurch ist die Anzahl rekursiver Funktionsaufrufe bereits für Zahlen wie $n=42$ sehr hoch (und zwar $433'494'437$). Dies liegt daran, dass die Fibonacci-Funktion immer wieder für die gleiche Zahl aufgerufen wird. Zum Beispiel wird in der Berechnung für `Fibonacci(42)` insgesamt $102'334'155$ `Fibonacci(3)` berechnet. Das ist nicht sehr effizient!
 Lösung: Verhindere, dass die ein Folgenglied mehrfach berechnet wird. Dazu müssen die bereits berechneten Folgenglieder in einer Liste gespeichert werden. Anstelle, dass ein Folgenglied erneut berechnet wird, liest man den Wert aus der Liste aus.
+Diese Art der Programmierung wird **dynamische Programmierung** genannt. Das Speichern der Zwischenresultate wird **Memoisation** genannt.
+++++
+</nodisp>
+=== Teil I ===
+Implementiere nun die rekursive Fibonacci Funktion dynamisch. Das heisst, die Zwischenresultate sollen in einer Liste oder einem Array gespeichert und wieder verwendet werden (Memoisation). Wie weit kannst du nun Folgenglieder der Fibonacci-Folge berechnen?
+=== Teil II ===
+Bestimme nun wieder, wie viele rekursive Funktionsaufrufe nötig sind. Vergleiche die dynamische mit der vorherigen, nicht dynamischen Implementierung.
+<nodisp 2>
+++++Lösung|
+Anzahl rekursive Funktionsaufrufe ist nun **linear** in $n$, genauer: $2n - 1$. Für $n=42$ sind es damit $83$ (dynamisch). Stellt man es den über 400 Millionen Funktionsaufrufe vom nicht dynamischen Code gegenüber, so sieht man, dass dies eine enorme Steigerung der Effizient ist!
+++++
 </nodisp>