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

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

== Raten und Einsetzen ==

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

Mit Hilfe der Wertetabelle sollen Funktionswerte(<math>T(n)</math>) durch geschicktes Einsetzen verschiedener Argumente(<math>n</math>) 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 <math>n</math> lediglich inkrementieren, so würde man spätestens bei <math> n=3 </math>, also <math>T(\frac{3}{2})</math> ins Stocken geraten, da hierfür in der Wertetabelle kein Wert vorliegt. 

rekursive Gleichung: <math> T(n)=3\cdot T(\frac{n}{2})+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}\cdot4^i </math>

Danch 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}\cdot4^i </math>

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

<math> T(2^k)=\sum_{i=0}^k 3^{k}\cdot\frac{1}{3^i}\cdot4^i </math>

<math> T(2^k)=\sum_{i=0}^k 3^{k}\cdot\frac{4^i}{3^i} </math>

<math> T(2^k)=\sum_{i=0}^k 3^{k}\cdot(\frac{4}{3})^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 (\frac{4}{3})^i </math>

''Formel:'' <math> \sum_{i=m}^k (x)^i = \frac{x^m-x^{k+1}}{x^m-x} </math>

(Fortsetzung folgt^^...)

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