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. 

;Beispiel 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 Ablesen den Aufwand zu bestimmen. 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>