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 mit Hilfe der Asymptotischen Aufwandsordnungen kein Problem dar. Mann kann durch einfaches Ablesen die 2 gennanten Funktionen durch Verwendung der "Groß-Oh-Notation" in <math>\mathcal{O}(n \rightarrow n^2)</math> 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 ==

'''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 <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 geschicktes Einsetzen verschiedener Argumente ermittelt werden.
Für das gewählte Beispiel bieten sich Zweierpotenzen an, Da man dann bei jedem Folgeschritt auf das Ergebnis des zuvor gewählten Argumentes zugreifen kann. Um <math>T(2)</math> zu berechnen muss man <math>T(1)</math> einsetzen, welchens gegeben ist. 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> Tn </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>

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.

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

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

<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 ==

== 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).

 
'''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>

=====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>