AuK/Hilfsmittel Mathematik 2 SS09

Wiki-Quelltext dieser Seite.

= Rekurionsgleichungen =

== Motivation ==

Das Bestimmen des Aufwandes für Gleichungen, wie <math> f(n)=n^2 </math> oder <math> f(n)=2\cdot n^2+12 </math> stellt mithilfe der Asymptotischen Aufwandsordnungen kein Problem dar. Mann kann durch einfaches Ablesen die 2 gennanten Funktionen durch Verwendung der "Groß-Oh-Notation" in O(n->n^2) einordnen.

Aber wie verhält es sich mit rekursiven Gleichungen? Die Fibonacci-Zahlenfolge oder die Fakultät-Zahlenfolge sind typische Vertreter für rekursive Gleichungen und auch gern gewählte Beispiele. 

;definition der Fibonacci-Zahlenfolge

:<math>F(0)=1</math>
:<math>F(1)=1</math>
:<math>F(n)=F(n-1)+F(n-2)</math>, mit <math>n>2</math>

Da es sich um eine rekursive Gleichung handelt ist es sichtlich schwer durch Betrachtung der Definition den Aufwand zu bestimmen.
Auch durch die Betrachtung der der einzelnen Fibonacci-Zahlen( 1,1,2,3,5,8,13,21,34,55,...) ist der genaue Aufwand nicht zu ermitteln.

Die nachfolgenden Abschnitte erläutern verschiedene Methoden, die zur Ermittlung des Aufwandes für rekursive Gleichungen helfen.

== Computeralgebrasysteme ==

== Raten und Einsetzen ==

== Konstruktive Induktion ==

== Iterationsmethode ==

== Die Meistermethode ==

== Folien ==
*Die aktuellsten Folien zur Vorlesung:
:: <document>Vortrag.pdf</document>

== Aufgaben ==

# '''Raten und Einsetzen'''
#* Ermitteln Sie die explizite Bildungsvorschrift für <math> T(n)=3\cdot T(\frac{n}{4})+2n, T(1)=2 </math>. 
# '''Computeralgebrasysteme'''
#* Machen sie sich mit dem CAS Maple und den Funktionen ''rsolve()'', ''simplify()'' und ''evalf()'' vertraut und lösen sie die Aufgabe 3.3 aus dem Buch.
# '''Iterationsmethode'''
#* Lösen sie folgende Gleichung mittels Iterationsmethode:
#* <math>3\cdot T(\frac{n}{2})+ cn</math>; für n>1, sonst d.
# '''Mastermethode'''
#* Prüfen sie mittels Master-Theorem folgende Gleichungen:
## <math>T(n)=3\cdot T(\frac{n}{2})+n^2</math>
## <math>T(n)=\sqrt{2}\cdot T(\frac{n}{2})+\log 2</math>

* und zum abspeichern ;)
:: <document>Aufgaben.pdf</document>

 == Lösungen ==
* zu Aufgabe 1: <document>Hilfsmittel_Mathematik_2_Aufgabe1Loe.pdf</document>
* zu Aufgabe 4: <document>Aufgabe4Loe.pdf</document>