Hilfsmittel Mathematik 2 SS09

Rekursionsgleichungen

Motivation

Ergibt die empirische oder theoretische Analyse des Aufwandes des betrachteten Verfahrend eine explizite Aufwandsfunktion, wie z.B. T_1(n)=n^2 oder T_2(n)=2\cdot n^3+5\cdot n^2-12, so kann die jeweils zugehörige asymptotische Aufwandsordnung unmittelbar abgelesen werden: T_1 liegt in \mathcal{O}(n^2). T_2 liegt in \mathcal{O}(n^3).

Ein systematischer Algorithmenentwurf (s. Folgevorlesungen) führt jedoch oftmals zu rekursiven Ergebnis-Beschreibungen, deren Berechnungsaufwand unmittelbar abgelesen werden kann, allerdings - der Natur des Algorithmus entsprechend - als Rekursionsgleichung der Form T(n)=f(T(n-1)) (oder so ähnlich). Wie gewinnt man daraus die explizite Gestalt für T?

Fibonacci-Zahlen

F(0)=1

F(1)=1

F(n)=F(n-1)+F(n-2), mit n\geq 2

Offensichtlich gilt für den Zeitaufwand:

T(0)=1

T(1)=1

T(n)=T(n-1)+T(n-2), mit n\geq 2.

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

Computeralgebrasysteme

Erklärung CAS

Computeralgebrasysteme (kurz: CAS) sind computergestützte Werkzeuge, welche entweder symbolische oder numerische Aufgaben lösen können. Nur wenige können beides.Weiterhin sind sie in der Lage rekursive Gleichungen in explizite Vorschriften umzuformen. Dabei ist zu beachten, dass die jeweiligen CAS (z.B. Matlab, Mathematica, Maple, Maxima,u.ä.) auf unterschiedlichen mathematischen GFrundlagen aufbauen und zur Umformung solcher Gleichungen verschieden vorgehen. Jedoch diennen allen die sogenannten Z-Transformationen. Diese sind sehr kompliziert und können auch nur für bestimmte Typen rekursiver Gleichungen (Gleichungsklassen) verwendet werden. Aus diesem Grund können CAS nicht für alle rekursiven Gleichungen eine expliziete Lösungen evaluieren.

Funktionen von CAS

Zum Auflösen solcher Gleichungen bieten alle CAS Funktionen an. Hier soll dies beispielhaft anhand des CAS Maple vorgestellt werden. Um eine rekursive Gleichung aufzulösen benutzt man die Funktion rsolve();.Diese benötigt 2 Argumente. Das 1. Argument beinhaltet Wertepaare sowie Funktionsgleichung, während das 2. Argument die aufzulösende Funktionsbezeichnung benötigt. Durch rsolve(); wird die Rekursion in einen explizieten Term umgeformt, d.h er ist unhabhängig von Vorwerten. Eine weitere Funktion heißt simplify();. Sie vereinfacht den erzeugten Term, indem Teilterme zusammengefasst werden und Werte, wen möglich, gekürzt werden. Ihr Argument ist die jeweilige rsolve()-Funktion.Die Dritte und hier letztgenannte Funktion heißt evalf();. Diese Funktion evaluiert den Term und stellt Brüche in dezimaler Form dar. Das Argument ist mit dem von simplify() identisch.

Raten und Einsetzen

Das geschickte Raten( intelligent guesswork) behilft sich einer Wertetabelle und eines guten mathematisch veranlagten Geistes, um den Aufwand einer rekursiven Gleichung zu ermitteln.

Sei die rekursive Gleichung T(n)=3\cdot T\left(\frac{n}{2}\right)+2, mit T(1)=1 gegeben.

Mit Hilfe der Wertetabelle sollen Funktionswerte durch geschicktes Einsetzen verschiedener Argumente ermittelt werden. Für das gewählte Beispiel bieten sich Zweierpotenzen an, da man dann bei jedem Folgeschritt auf das zuvor berechnete Ergebnis zugreifen kann. Um T(2) zu berechnen muss man T(1) einsetzen, welchens gegeben ist. Um T(4) zu berechnen, muss man T(2) einsetzen, welches man in der Wertetabelle zuvor berechnet hat und so weiter.

Würde man n lediglich inkrementieren, so würde man spätestens bei n=3 , also T\left(\frac{3}{2}\right) ins Stocken geraten, da hierfür in der Wertetabelle (noch) kein Wert vorliegt.

rekursive Gleichung: T(n)=3\cdot T\left(\frac{n}{2}\right)+n , n=2^k

Bei der Erstellung der Wertetabelle ist nicht die absolute Zahl von Interesse, sondern eine möglichst geschickte Anordnung der einzelnen Zahlen aus die der Term besteht, sodass wir das Wachstum vom n-ten Wert zu dem (n+1)-ten Wert ermitteln können. Hat man genug Werte ermittelt und ist einem das Verhalten von n zu (n+1) klar, so versucht man das Ganze, z.B. mittels Summen- oder Produktdarstellung, kompakter zu beschreiben.

 T(2^k)=\sum_{i=0}^k 3^{k-i}\cdot2^i 

Danach gilt es, den enstandenen Ausdruck in eine explizite Form umzuwandeln, da man den Aufwand einer Gleichung in Summendarstellung, genauso wie bei rekursiven Gleichungen ,nur schwer ablesen kann.

 T(2^k)=\sum_{i=0}^k 3^{k-i}\cdot2^i 

 T(2^k)=\sum_{i=0}^k 3^{k}\cdot3^{-i}\cdot2^i 

 T(2^k)=\sum_{i=0}^k 3^{k}\cdot\frac{1}{3^i}\cdot2^i 

 T(2^k)=\sum_{i=0}^k 3^{k}\cdot\frac{2^i}{3^i} 

 T(2^k)=\sum_{i=0}^k 3^{k}\cdot\left(\frac{2}{3}\right)^i  

Anmerkung: Konstante Faktoren innerhalb der Summe können vor die Summe gestellt werden

 T(2^k)=3^{k} \sum_{i=0}^k \left(\frac{2}{3}\right)^i 

Formel: \sum_{i=m}^k (x)^i = \frac{x^m-x^{k+1}}{x^m-x}

 T(2^k)=3^k\cdot\frac{\left(\frac{2}{3}\right)^0-\left(\frac{2}{3}\right)^{k+1}}{\left(\frac{2}{3}\right)^0-\frac{2}{3}}

 T(2^k)=3^k\cdot\frac{1-\left(\frac{2}{3}\right)^{k+1}}{\frac{1}{3}}

 T(2^k)=3^k\cdot3\cdot\Bigg(1-\left(\frac{2}{3}\right)^{k+1}\Bigg)

 T(2^k)=3^{k+1}\cdot\Bigg(1-\left(\frac{2}{3}\right)^{k+1}\Bigg)

 T(2^k)=3^{k+1}-2^{k+1}

Bis zum jetzigen Zeitpunkt haben wir immer mit T(2^k) gerechnet. Jedoch ist eine Funktion T:n \rightarrow T(n) gesucht. Zu Beginn wurde die Vereinbarung n=2^k getroffen. Da \log_a{b}=c \Leftrightarrow a^c=b muss k=\log_2{n} substituiert werden.

 T(n)=3^{\log_2{n}+1}-2^{\log_2{n}+1}

 T(n)=3\cdot3^{\log_2{n}}-2\cdot 2^{\log_2{n}}

Formel: a^{\log_a{b}}=b

 T(n)=3\cdot3^{\log_2{n}}-2\cdot n

Aus der obigen Formel ergibts sich das wir für 2^{\log_2{n}} einfach n schreiben können. Auf 3^{\log_2{n}} ist dies nicht direkt anwendbar. Daher muss man hier den Gedanken folgen, wie man die 3 in eine 2 umwandelt, um die obige Formel erneut anwenden zu können. Aus der Überlegung, dass 2^x=3 ist, kann man Schlussfolgern, dass x=\log_2{3} . Nun kann man anstatt 3, einfach 2^{\log_2{3}} einsetzen.

 T(n)=3\cdot2^{\log_2{n}\cdot\log_2{3}}-2\cdot n

 T(n)=3\cdot n^{log_2{3}}-2\cdot n

Das Ergebnis lautet:

T(n)=\mathcal{O}\left(n^{\log_2{3}}\right).

Konstruktive Induktion

Eine andere Möglichkeit den Aufwand einer Rekursionsgleichung zu ermitteln, ist die Verwendung der Konstruktiven Induktion.

Wie bei der Vollständigen Induktion besteht die Konstruktive Induktion ebenfalls aus Induktionsanfang und Induktionsschritt. Um mit dem Induktionsanfang beginnen zu können, muss erst einmal auf konstruktive Weise eine Ausgangsgleichung ermittelt werden. Am Beispiel der Fibonacci-Folge lässt sich die Konstruktive Induktion erklären. Beim Ausprobieren, eine explizite Gleichung zu finden die sich der Folge annähert, stellt man fest, dass sich der Aufwand exponentiell Beschreiben lässt. Daher ergbit sich vorläufig folgende Gleichung:

 T(n) = \mathcal{O}(c^n)

Definition Groß-O

\mathcal{O}(f)=\{t:\mathbb{N}\mapsto\mathbb{R}_{0}^{+}\mid\exists c\in\mathbb{R}^{+}\quad\exists n_{0} \in\mathbb{N}\quad\forall n\ge n_{0}\quad t(n)\le c\cdot f(n)\}

Gesprochen: \mathcal{O} ist die Menge aller Funktionen t:\mathbb{N}\mapsto\mathbb{R}_{0}^{+}, für die es eine poitive reelle Zahl c gibt, sodass ab eibem gewissen n-{0} \exists \mathbb{N} sämtliche Funktionswerte t(n) nicht oberhalb von c\cdot f(n) liegen.

Aus der Definition von Groß-\mathcal{O} geht folgende Ungleichung hervor:

 T(n)\le a\cdot c^{n}

Es gilt nun mittels vollständiger Induktion zu beweisen, dass ein Wert für a und c existiert, sodass die Ungleichung wahr ist.

Induktionsanfang:

Aus der Definition von Fibonacci ist bekannt, dass T(0)=1 und T(1) = 1. Ergänzen wir nun die vorher ermittelte Ungleichung, ergibt sich folgendes:

 T(0)=1\le a\cdotc^{0}
 T(1)=1\le a\cdot^{1}

Betrachtet man die erste Ungleichung, stellt man fest, dass c^{0}=1. Das hat zu Folge, dass a\ge1. Der Einfachheit halber wählen wir a=1. Für c ergibt sich, dass c>1 .

Induktionsschritt:

Aus der Definition der Fibonacci-Folge ist bekannt das T(n)=T(n-1)+T(n-2) . Dies gilt es jetzt im Induktionsschritt zu beweisen. Es lässt sich folgend Rechnung erstellen:

 T(n)\:\:=\:\: T(n-1)+T(n-2)  

 T(n)\:\:\le\:\: a\cdot c^{n-1}+a\cdot c^{n-2}

 T(n)\:\:\le\:\: a\cdot c^{n}\cdot c^{-1}+ a\cdot c^{n}\cdot c^{-2} 

 T(n)\:\:\le\:\: a\cdot c^{n}\cdot\left(\frac{1}{c}+\frac{1}{c^{2}}\right)

 T(n)\:\:\le\:\: a\cdot c^{n}\cdot\left(\frac{c}{c^{2}}+\frac{1}{c^{2}}\right)

 T(n)\:\:\le\:\: a\cdot c^{n}\cdot\frac{c+1}{c^{2}}

Damit T(n)\le a\cdot c^{n} muss \frac{c+1}{c^{2}}=1 gelten.

 1\quad\,=\:\: c^{2}-c-1 

 c _{1/2}=\:\: (\frac{1}{2})_{-}^{+}\sqrt{\frac{1}{4}+1} 

 c_{1}\:\:=\:\: \frac{1+\sqrt{5}}{2},  c_{2}\:\:=\:\: \frac{1-\sqrt{5}}{2} 

Da \sqrt{5}>2 würde sich für c_{2} ein negativer Wert ergeben. Da es einen negativen Wert für den Aufwand nicht geben kann, entfällt c_{2} .

Daher ist die Lösung der Gleichung c = \frac{1+\sqrt{5}}{2}\approx 1.618.

Der Aufwand für die Berechnung der n-ten Fibonacci-Zahl lässt sich also folgendermaßen beschreiben:

 T(n)\:\:=\:\:\mathcal{O}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}\right) 

Iterationsmethode

Die Iterationsmethode ist ein Mittel zur Lösung rekursiver Gleichungen T(n). Zur Auflösung einer Gleichung wir die rekursive Gleichung, sowie ein Wertpaar benötigt, welches ein rekursionsfreies n repräsentiert. Meistens wird hierfür T(0) oder T(1) angegeben für eine Gleichung der Form T(n)=a\cdot T(\frac{n}{b})+f(n).Beispiel aus dem Buch mit a=3 und b=4, sowie f(n)=n.

T(n)=3\cdot T(\frac{n}{4})+n
T(1)=1

Die Gleichung wird nun solange iteriert bis das rekursionsfreie n des Festwertes ermittelt wurde. Dazu benötigt man eine hergeleitete rekursive Bildungsvorschrift(Telescoping). Zur Bestimmung der Ordnung muss anschließend eine explizite Bildungsvorschrift bestimmt werden. Hier am Beispiel vorgeführt.

Telescoping

T(n)=3\cdot T(\frac{n}{4})+n 

Nebenrechnung: T(\frac{n}{4})=3\cdot T(\frac{n}{16})+\frac{n}{4}

Einsetzen: T(n)=3\cdot (3\cdot T(\frac{n}{16})+\frac{n}{4})+n

Zusammengefasst: T(n)=3^{2}\cdot T(\frac{n}{4^{2}})+3^{1}\cdot \frac{n}{4^{1}}+n

Allgemein: T(n) = 3^{k}\cdot T(\frac{n}{4^{k}})+3^{k-1} \cdot \frac{n}{4^{k-1}} + n

Diese rekursive Nottion kann auch in Kurzschreibweise wiedergegeben werden.

Kurznotation: T(n)=3^{k}\cdotT(\frac{n}{4^{k}})+\sum_{i=0}^{k-1}(\frac{3}{4})^{i}\cdot n

Da aus der Ausgangsgleichung hervorgeht, dass die Funktion T(n) nur für n=1 rekursionsfrei ist, gilt: T(\frac{n}{4^{k}})=T(1) bzw. \frac{n}{4^{k}}=1. Durch logarithmische Umformung erhält man für k=\log_4 n

Indem man nun k einsetzt erhält man die expliziete Gleichung:

T(n)= 3^{\log_4 n}\cdot 1 +n\cdot \sum_{i=0}^{\log_4 n -1} (\frac{3}{4})^{i}

Jedoch ist man hier noch nicht fertig, da hier ein Aufwand betrachtet werden soll bzw. die Ordnung dieses Aufwandes. Offensichtlich handelt es sich bei der Summe um eine geometrische Reihe. Daher kann die Gleichung wie folgt geschrieben werden:

T(n) = 3^{\log_4 n}+n\cdot(\frac {1-(\frac{3}{4})^{\log_4 n}} {1-\frac{3}{4}} )   

Da nach Logarithmengesetz x^{\log_b y}=y^{\log_b x} gilt kann man dies auf jeden Term anwenden, welcher einen Logarithmus mit n in der Form a^{}log_b n im Exponenten besitzt. Dadurch erhält man folgende Gleichung-

T(n) = n^{\log_4 3}+ n\cdot \frac{1- n^{\log_4 \frac{3}{4}}}{1- \frac{3}{4}}   =n^{\log_4 3}+ n\cdot \frac{1-n^{\log_4 3 - \log_4 4}}{\frac{1}{4}}  =n^{\log_4 3}+4n\cdot (1-n^{\log_4 3}\cdot n^{-1})

Zusammenfassend erhält man schließlich:

T(n) = 4n-3n^{\log_4 3}

Da \log_4 3 \lessapprox 1 ist der Aufwand T(n):

T(n) = \mathcal{O}(n)

Die Meistermethode

Die Mastermethode ist ein Testverfahren mit dem man zeigen kann ob eine rekursive Gleichung der Form T(n) =a\cdot T(\frac{n}{b})+f(n) in eine Aufwandsklasse passt oder nicht. Dabei wird der Aufwand von T(n) mit dem von f(n) verglichen. Hierfür wird folgende Gleichung benutzt:

\mathcal{O}(n^{\log_b a+\epsilon})=\mathcal{O}(f(n))

Wie man sieht ergeben sich damit für \epsilon 3 zu betrachtende Fälle.

1. \epsilon < 0
2. \epsilon = 0
3. \epsilon > 0

1.Fall

Trifft der 1. Fall zu heißt das, dass der Aufwand von f(n) kleiner als der Aufwand von T(n) ist, d.h. der Aufwand von f(n) im Aufwand von T(n) aufgeht - mathematisch ausgedrückt f(n) \in \mathcal{O}(n^{\log_b a}). In einem solchen Fall ist die Größe des Aufwandes also die von T(n).

T(n)=4\cdot T(\frac{n}{2})+ 50n

\mathcal{O}(n^{\log_2 4+\epsilon})=\mathcal{O}(n) =\mathcal{O}(n^{2+\epsilon})=\mathcal{O}(n)

T(n)=\mathcal{O}(n^{\log_2 4})  =\mathcal{O}(n^{2})

2.Fall

Stellt man fest, dass beim Vergleich \epsilon = 0 ist, so ist der 2. Fall eingetreten. Man spricht auch davon, dass f(n) \in \theta(n^{\log_b a}). In diesem Fall ist der Aufwand \mathcal{O} für T(n) folgendermaßen definiert.

T(n)=\mathcal{O}(n^{\log_b a}\cdot \log_b(n))

T(n)=8\cdot T(\frac{n}{2})+1000n^{3}

Eingesetzt: \mathcal{O}(n^{\log_2 8 +\epsilon})=\mathcal{O}(n^{3})

T(n)=\mathcal{O}(n^{3}\cdot \log_2(n))

3.Fall

Sollte man beim Vergleich ein positives \epsilon erhalten, so muss man noch folgendes prüfen:

Gibt es für die Gleichung II. a\cdot f(\frac{n}{b})\leq c\cdot f(n) ein c, sodass 0<c<1 ist. Wenn ja, dann gilt:

T(n)=\Theta(f(n))

T(n)=2\cdot T(\frac{n}{2})+n^{2}

Verglichen: \mathcal{O}(n^{1+\epsilon})=\mathcal{O}(n^{2})

Es folgt: II. 2\cdot (\frac{n}{2})^{2}\leq c\cdot n^{2}

 \frac{1}{2} \cdot n^{2} \leq c\cdot n^{2}

T(n)=\mathcal{O}(n^{2})

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

Lösungen

• zu Aufgabe 1: Hilfsmittel_Mathematik_2_Aufgabe1Loe.pdf
• zu Aufgabe 2: Hm-M2-Loe.Aufg2.pdf
• zu Aufgabe 3: HmM2-LoesAufg3.pdf
• zu Aufgabe 4: HmM2-LoesAufg4.pdf