Rekurionsgleichungen

Motivation

Das Bestimmen des Aufwandes für Gleichungen, wie f(n)=n^2 oder f(n)=2\cdot n^2+12 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

F(0)=1

F(1)=1

F(n)=F(n-1)+F(n-2), mit n>2

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:

Vortrag.pdf

Aufgaben

1. Raten und Einsetzen
   • Ermitteln Sie die explizite Bildungsvorschrift für T(n)=3\cdot T(\frac{n}{4})+2n, T(1)=2 .
2. 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.
3. Iterationsmethode
   • Lösen sie folgende Gleichung mittels Iterationsmethode:
   • 3\cdot T(\frac{n}{2})+ cn; für n>1, sonst d.
4. Mastermethode
   • Prüfen sie mittels Master-Theorem folgende Gleichungen:
   1. T(n)=3\cdot T(\frac{n}{2})+n^2
   2. T(n)=\sqrt{2}\cdot T(\frac{n}{2})+\log 2

• und zum abspeichern ;)

Aufgaben.pdf

== Lösungen ==

• zu Aufgabe 1: Hilfsmittel_Mathematik_2_Aufgabe1Loe.pdf
• zu Aufgabe 4: Aufgabe4Loe.pdf