AuK/Hilfsmittel Mathematik 2 SS09

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Rekursionsgleichungen ==

=== Motivation ===

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

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 <math>T(n)=f(T(n-1))</math> (oder so ähnlich). Wie gewinnt man daraus die explizite Gestalt für <math>T</math>?

;Fibonacci-Zahlen
:<math>F(0)=1</math>
:<math>F(1)=1</math>
:<math>F(n)=F(n-1)+F(n-2)</math>, mit <math>n\geq 2</math>

Offensichtlich gilt für den Zeitaufwand:
:<math>T(0)=1</math>
:<math>T(1)=1</math>
:<math>T(n)=T(n-1)+T(n-2)</math>, mit <math>n\geq 2</math>.

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

=== Computeralgebrasysteme ===

'''CAS: Begriff und Reichweite'''

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) auf unterschiedlichen mathematischen Grundlagen aufbauen und bei der Umformung solcher Gleichungen verschieden vorgehen. Im Allg. spielt aber die sog. Z-Transformation eine wichtige Rolle. Z-Transformationen 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 explizite Lösung berechnen.

'''Funktionen von CAS''' 

Um eine rekursive Gleichung aufzulösen benutzt Maple (hier als Referenzsystem) die Funktion <nowiki>rsolve()</nowiki>. Sie benötigt 2 Argumente. Das 1. Argument beinhaltet Wertepaare, während das 2. Argument die aufzulösende Funktionsbezeichnung be....
Durch <nowiki>rsolve();</nowiki> wird die Rekursion in einen explizieten Term umgeformt, d.h er ist unhabhängig von Vorwerten.  

Eine weitere Funktion heißt <nowiki>simplify()</nowiki>. Sie vereinfacht den erzeugten Term, indem Teilterme zusammengefasst und Werte, wenn möglich, gekürzt werden. Ihr Argument ist die jeweilige rsolve()-Funktion.

Schließlich gibt es noch die Funktion <nowiki>evalf()</nowiki>. Diese evaluiert den Term und stellt Brüche in dezimaler Form dar. Das Argument ist mit dem von <nowiki>simplify()</nowiki> identisch.

=== Raten und Einsetzen ===

Das geschickte Raten (intelligent guesswork) versucht, den funktionalen Zusammenhang aus einer Wertetabelle "herauszuvermuten".

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

Mit Hilfe der Wertetabelle sollen Funktionswerte durch 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 beispielsweise <math>T(2)</math> zu berechnen, kann man auf <math>T(1)</math> zurückgreifen. Um <math>T(4)</math> zu berechnen, muss man <math>T(2)</math> 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 <math> n=3 </math>, also <math>T\left(\frac{3}{2}\right)</math> ins Stocken geraten, da hierfür in der Wertetabelle (noch) kein Wert vorliegt. 

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

<table cellpadding="6">
   <tr> 
    <td><math> n </math></td>
    <td><math> T(n) </math></td>
  </tr>
  <tr>
    <td><math> 1 </math></td>
    <td><math> 1 </math></td>
  </tr>
  <tr>
    <td><math> 2 </math></td>
    <td><math> 3\cdot 1+2 </math></td>
  </tr>
  <tr>
    <td><math> 4 </math></td>
    <td><math> 3\cdot(3\cdot1+2)+4 </math></td>
  </tr>
  <tr>
    <td/>
    <td><math> 3^2\cdot1+3\cdot2+2^2 </math></td>
  </tr>
  <tr>
    <td><math> 8 </math></td>
    <td><math> 3\cdot(3^2\cdot1+3\cdot2+2^2)+8 </math></td>
  </tr>
  <tr>
    <td/>
    <td><math> 3^3\cdot1+3^2\cdot2+3\cdot2^2+2^3 </math></td>
  </tr>
  <tr>
    <td><math> 16 </math></td>
    <td><math> 3\cdot(3^3\cdot1+3^2\cdot2+3\cdot2^2+2^3)+16 </math></td>
  </tr>
  <tr>
    <td/>
    <td><math> 3^4\cdot1+3^3\cdot2+3^2\cdot2^1+3\cdot2^3+2^4 </math></td>
  </tr>
</table>

Wir vermuten den folgenden Zusammenhang:
 <math> T(2^k)=\sum_{i=0}^k 3^{k-i}\cdot2^i </math>

Weitere Transformationen ergeben:
 <math> T(2^k)=\sum_{i=0}^k 3^{k-i}\cdot2^i </math>
 
 <math> T(2^k)=\sum_{i=0}^k 3^{k}\cdot3^{-i}\cdot2^i </math>
 
 <math> T(2^k)=\sum_{i=0}^k 3^{k}\cdot\frac{1}{3^i}\cdot2^i </math>
 
 <math> T(2^k)=\sum_{i=0}^k 3^{k}\cdot\frac{2^i}{3^i} </math>
 
 <math> T(2^k)=\sum_{i=0}^k 3^{k}\cdot\left(\frac{2}{3}\right)^i </math> 
''Anmerkung:'' Konstante Faktoren innerhalb der Summe können vor die Summe gestellt werden
 <math> T(2^k)=3^{k} \sum_{i=0}^k \left(\frac{2}{3}\right)^i </math>
''Formel:'' <math> \sum_{i=m}^k (x)^i = \frac{x^m-x^{k+1}}{x^m-x} </math>
 <math> 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}}</math>
 
 <math> T(2^k)=3^k\cdot\frac{1-\left(\frac{2}{3}\right)^{k+1}}{\frac{1}{3}}</math>
 
 <math> T(2^k)=3^k\cdot3\cdot\Bigg(1-\left(\frac{2}{3}\right)^{k+1}\Bigg)</math>
 
 <math> T(2^k)=3^{k+1}\cdot\Bigg(1-\left(\frac{2}{3}\right)^{k+1}\Bigg)</math>
 
 <math> T(2^k)=3^{k+1}-2^{k+1}</math>
Bis zum jetzigen Zeitpunkt haben wir immer mit <math>T(2^k)</math> gerechnet. Jedoch ist eine Funktion <math>T:n \rightarrow T(n)</math> gesucht. Zu Beginn wurde die Vereinbarung <math>n=2^k</math> getroffen. Da <math> \log_a{b}=c \Leftrightarrow a^c=b </math> muss <math> k=\log_2{n} </math> substituiert werden. 
 <math> T(n)=3^{\log_2{n}+1}-2^{\log_2{n}+1}</math>
 
 <math> T(n)=3\cdot3^{\log_2{n}}-2\cdot 2^{\log_2{n}}</math>
''Formel:'' <math> a^{\log_a{b}}=b </math>
 <math> T(n)=3\cdot3^{\log_2{n}}-2\cdot n</math>
Aus der obigen Formel ergibts sich das wir für <math> 2^{\log_2{n}}</math> einfach n schreiben können. Auf <math>3^{\log_2{n}}</math> 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 <math> 2^x=3 </math> ist, kann man Schlussfolgern, dass <math> x=\log_2{3} </math>. Nun kann man anstatt 3, einfach <math> 2^{\log_2{3}}</math> einsetzen. 
 <math> T(n)=3\cdot2^{\log_2{n}\cdot\log_2{3}}-2\cdot n</math>
 
 <math> T(n)=3\cdot n^{log_2{3}}-2\cdot n</math>
Das Ergebnis lautet:
 <math>T(n)=\mathcal{O}\left(n^{\log_2{3}}\right)</math>.

== 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:
 <math> T(n) = \mathcal{O}(c^n)</math>
;Definition Groß-O
:<math> \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)\}   </math>
:Gesprochen: <math> \mathcal{O} </math> ist die Menge aller Funktionen <math> t:\mathbb{N}\mapsto\mathbb{R}_{0}^{+}</math>, für die es eine poitive reelle Zahl <math> c </math> gibt, sodass ab eibem gewissen <Math> n-{0} \exists \mathbb{N}</math> sämtliche Funktionswerte <math> t(n)</math> nicht oberhalb von <math> c\cdot f(n)</math> liegen.


Aus der Definition von Groß-<math>\mathcal{O}</math> geht folgende Ungleichung hervor:
 <math> T(n)\le a\cdot c^{n}</math>
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 <math> T(0)=1 </math> und <math> T(1) = 1</math>. Ergänzen wir nun die vorher ermittelte Ungleichung, ergibt sich folgendes:
 <math> T(0)=1\le a\cdotc^{0}</math>
 <math> T(1)=1\le a\cdot^{1}</math>
Betrachtet man die erste Ungleichung, stellt man fest, dass <math>c^{0}=1</math>. Das hat zu Folge, dass <math> a\ge1</math>. Der Einfachheit halber wählen wir <math>a=1</math>. Für c ergibt sich, dass <math> c>1 </math>.

Induktionsschritt:

Aus der Definition der Fibonacci-Folge ist bekannt das <math> T(n)=T(n-1)+T(n-2) </math>. Dies gilt es jetzt im Induktionsschritt zu beweisen. 
Es lässt sich folgend Rechnung erstellen:
 <math> T(n)\:\:=\:\: T(n-1)+T(n-2)</math>  
 
 <math> T(n)\:\:\le\:\: a\cdot c^{n-1}+a\cdot c^{n-2}</math>
 
 <math> T(n)\:\:\le\:\: a\cdot c^{n}\cdot c^{-1}+ a\cdot c^{n}\cdot c^{-2} </math>
 
 <math> T(n)\:\:\le\:\: a\cdot c^{n}\cdot\left(\frac{1}{c}+\frac{1}{c^{2}}\right)</math>
 
 <math> T(n)\:\:\le\:\: a\cdot c^{n}\cdot\left(\frac{c}{c^{2}}+\frac{1}{c^{2}}\right)</math>
 
 <math> T(n)\:\:\le\:\: a\cdot c^{n}\cdot\frac{c+1}{c^{2}}</math>
Damit <math> T(n)\le a\cdot c^{n} </math> muss <math> \frac{c+1}{c^{2}}=1 </math> gelten.
 <math> 1\quad\,=\:\: c^{2}-c-1 </math>
 
 <math> c _{1/2}=\:\: (\frac{1}{2})_{-}^{+}\sqrt{\frac{1}{4}+1} </math>
 
 <math> c_{1}\:\:=\:\: \frac{1+\sqrt{5}}{2}</math>, <math> c_{2}\:\:=\:\: \frac{1-\sqrt{5}}{2} </math>

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

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

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

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

== 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 <math>T(n)=a\cdot T(\frac{n}{b})+f(n)</math>.Beispiel aus dem Buch mit <math>a=3</math> und <math>b=4</math>, sowie <math>f(n)=n</math>.
 <math>T(n)=3\cdot T(\frac{n}{4})+n</math>
 <math>T(1)=1</math>
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'''
 <math>T(n)=3\cdot T(\frac{n}{4})+n</math> 

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

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

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

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

Diese rekursive Nottion kann auch in Kurzschreibweise wiedergegeben werden.

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

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

Indem man nun '''k''' einsetzt erhält man die expliziete Gleichung:
 <math>T(n)= 3^{\log_4 n}\cdot 1 +n\cdot \sum_{i=0}^{\log_4 n -1} (\frac{3}{4})^{i}</math>

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:
 <math>T(n) = 3^{\log_4 n}+n\cdot(\frac {1-(\frac{3}{4})^{\log_4 n}} {1-\frac{3}{4}} )</math>   

Da nach Logarithmengesetz <math>x^{\log_b y}=y^{\log_b x}</math> gilt kann man dies auf jeden Term anwenden, welcher einen Logarithmus mit n in der Form <math>a^{}log_b n</math> im Exponenten besitzt. Dadurch erhält man folgende Gleichung-
 <math>T(n) = n^{\log_4 3}+ n\cdot \frac{1- n^{\log_4 \frac{3}{4}}}{1- \frac{3}{4}}</math>   <math>=n^{\log_4 3}+ n\cdot \frac{1-n^{\log_4 3 - \log_4 4}}{\frac{1}{4}}</math>  <math>=n^{\log_4 3}+4n\cdot (1-n^{\log_4 3}\cdot n^{-1})</math>

Zusammenfassend erhält man schließlich:
 <math>T(n) = 4n-3n^{\log_4 3}</math>
Da <math>\log_4 3 \lessapprox 1</math> ist der Aufwand T(n):
 <math>T(n) = \mathcal{O}(n)</math>

== Die Meistermethode ==
Die Mastermethode ist ein Testverfahren mit dem man zeigen kann ob eine rekursive Gleichung der Form <math>T(n) =a\cdot T(\frac{n}{b})+f(n)</math> 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:
 <math>\mathcal{O}(n^{\log_b a+\epsilon})=\mathcal{O}(f(n))</math>
Wie man sieht ergeben sich damit für <math>\epsilon</math> 3 zu betrachtende Fälle.
# <math>\epsilon < 0 </math>
# <math>\epsilon = 0 </math>
# <math>\epsilon > 0 </math>


=====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 <math>f(n) \in \mathcal{O}(n^{\log_b a})</math>. In einem solchen Fall ist die Größe des Aufwandes also die von T(n).

<popup name=Fallbeispiel> 
'''Fallbeispiel'''
 <math>T(n)=4\cdot T(\frac{n}{2})+ 50n</math>

In die obige Gleichung eingesetzt ergibt das:
 <math>\mathcal{O}(n^{\log_2 4+\epsilon})=\mathcal{O}(n)</math> <math>=\mathcal{O}(n^{2+\epsilon})=\mathcal{O}(n)</math>
 
Das gesuchte <math>\epsilon = -1, \epsilon <0 </math>, d.h. 1.Fall bestätigt.

Somit ist der Aufwand 
 <math>T(n)=\mathcal{O}(n^{\log_2 4})</math> <math> =\mathcal{O}(n^{2})</math>
</popup>

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

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

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

Da <math>\epsilon =0</math> gilt für den Aufwand:
 <math>T(n)=\mathcal{O}(n^{3}\cdot \log_2(n))</math>
</popup>

=====3.Fall=====

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

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

<popup name=Fallbeispiel>
'''Fallbeispiel'''

 <math>T(n)=2\cdot T(\frac{n}{2})+n^{2}</math>

 Verglichen: <math>\mathcal{O}(n^{1+\epsilon})=\mathcal{O}(n^{2})</math>
Man erkennt, dass <math>\epsilon = 1</math> ist.
Nach der allgemeinen Form der Aufwandsgleichung T(n) gilt hier <math>a=b=2, f(n)=n^{2}</math>.

 Es folgt: '''II.''' <math>2\cdot (\frac{n}{2})^{2}\leq c\cdot n^{2}</math>
 
  <math>\frac{1}{2} \cdot n^{2} \leq c\cdot n^{2}</math>

Da  <math>\frac{1}{2}\leq c</math>  d.h.  <math>0<c<1</math> ist, gehört diese Aufwandsgleichung in Fall 3.

Somit ergibt sich:
 <math>T(n)=\mathcal{O}(n^{2})</math>
</popup>

== 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 2: <document>Hm-M2-Loe.Aufg2.pdf</document>
* zu Aufgabe 3: <document>HmM2-LoesAufg3.pdf</document>
* zu Aufgabe 4: <document>HmM2-LoesAufg4.pdf</document>