AuK/Hilfsmittel Mathematik 2 SS11

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
'''<b>Autor:</b>'''
 Bernd Schönlebe
 
== Rekursionsgleichungen (Differenzengleichung)==

[[Datei:Droste.jpg|200px|thumb|right|Beispiel einer Rekursion in einer frühen Werbung um 1900]]
Bereits eine leicht verständliche Definition der [http://de.wikipedia.org/wiki/Rekursion Rekursion] wirft eine scheinbar ebenso einfache Frage auf:
:'''Rekursion'''
::Siehe: "Rekursion".
Wie lange muss man "Rekursion" nachschlagen um die Definition zu erfahren? Bzw. wieviele Schritte werden benötigt? In diesem Fall sind es unendlich viele Wiederholungen, denn es handelt sich um einen Infiniten Regress. Im folgendem Beispiel ist schon eine Abbruchbedingung mit eingebaut:
:'''Rekursion'''
::Wenn Sie es noch nicht verstanden haben, Siehe: "Rekursion".
Hier kann man die vorhergehenden Fragen nicht so leicht beantworten, denn das Verhalten der Abruchbedingung ist unbekannt, aber immerhin ist es möglich, dass es zum Abbruch der Schleife kommt und somit eine Antwort gegeben werden kann. Ein Beispiel aus der Mathematik verdeutlich ein weiteres Problem: 
:'''Die Fibonacci Folge'''
::Die Mathematische Definition der [http://de.wikipedia.org/wiki/Fibonacci-Folge Fibonacci Folge] ''F<sub>n</sub>'' :
:::<math>F_n = F_{n-1} + F_{n-2},\!\,</math>
::mit den Startwerten
:::<math>F_0 = 0 \quad\text{und}\quad F_1 = 1.</math>


Hier ein Beispiel zum Testen in Scheme:

<code id="4b960fdc15037" rows="20" cols="90">(define fib
  (lambda (n)
    (if (< n 2)
         1
         (+ (fib (- n 1)) (fib (- n 2))))))</code>
<run id="4b960fdc15804">
(fib 5)
</run>


Grob gesagt ist ein Element die Summe seiner beiden Vorgänger. Hier ist der Aufwand linear, d.h. zur Berechnung von ''F<sub>n</sub>'' werden ''n'' Schritte benötigt. Oder wenn wenn man ''n'' verdoppelt , verdoppelt sich die Anzahl der Schritte zur Berechnung. Aber wie ist der Verlauf der Ergebnisse? Wie groß werden die Ergebnisse wenn man ''n'' verdoppelt oder vervierfacht und wieviel Speicher benötigt man dafür? Im Folgenden sieht man eine graphische Darstellung des Verlaufes bis <math>n=20</math>:


<gnuplot>
set xlabel "n"
set ylabel "T(n)"
set data style lines
plot \
<dataset>
0	0
1	1
2	1
3	2
4	3
5	5
6	8
7	13
8	21
9	34
10	55
11	89
12	144
13	233
14	377
15	610
16	987
17	1597
18	2584
19	4181
20	6765
</dataset>
</gnuplot>

=== Motivation === 
Da man aber nun trotzdem eine Abschätzung für den Aufwand (Schritte, Resourcen, etc. ) braucht und dieser meist nicht direkt ablesbar ist, hat man mehrere Mathematische Methoden entwickelt. Nun könnte man entweder empirisch oder theoretisch die Aufwandsfunktion ermitteln.Daraus entsteht z.B. <math>T_1(n)=n^2</math> oder <math>T_2(n)=2\cdot n^3+5\cdot n^2-12</math> und man kann daran bereits die Aufwandsordnung nach der Groß-O-Notation ablesen:<math>T_1</math> liegt in <math>\mathcal{O}(n^2)</math>. <math>T_2</math> liegt in <math>\mathcal{O}(n^3)</math>. Sobald man jedoch Algorithmen entwirft, entstehen Gleichungen wie z.B. <math>T(n)=f(T(n-1))</math> und es ist nicht mehr so einfach den Aufwand abzulesen. Wie erhält man nun die explizite Form für <math>T(n)</math> das von keinem anderen <math>T(i)</math> abhängt? Also der Form <math>T(n)=f(n)</math> entspricht?

=== Computeralgebrasysteme(CAS) === 

Um solche schwierigen Aufgaben dem Mathematiker abzunehmen, hat man sich bequeme Werkzeuge entwickelt, welche diese Arbeit an den Computer delegieren. Es handelt sich um sogenannte [http://de.wikipedia.org/wiki/Computeralgebrasystem Computeralgebrasysteme] (kurz CAS). Das sind Programme, die neben dem numerischen auch das symbolische Rechnen beherrschen. Normalerweise würde ein Taschenrechner folgenden Bruch <sup>1</sup>''/''<sub>3</sub> als Dezimalzahl mit begrenzter Genauigkeit speichern und anzeigen. Ein Symbolischer Rechner dagegen wird es als Division zweier ganzer Zahlen speichern und davon, wenn gewünscht, die dezimale Anzeige ableiten. Außerdem wird im weiteren Verlauf der Rechnung mit diesem Symbol auch immer wieder die Division der beiden Zahlen eingesetzt, sodass das Ergebnis keine wachsende Ungenauigkeit erfährt. Aber natürlich können Sie inzwischen mehr als nur einen Bruch zweier ganzer Zahlen zu speichern. Hier ein Auszug:
::-Termumformungen
::-Termvereinfachung
::-Gleichungslösen
::-Extremwertbestimmung
::-Graphische Kurvendarstellung
Es gibt verschiedene CAS (z.B. [http://de.wikipedia.org/wiki/Maple_(Software) Maple], [http://de.wikipedia.org/wiki/Mathematica Mathematica], [http://de.wikipedia.org/wiki/Matlab Matlab], [http://de.wikipedia.org/wiki/Maxima_(Computeralgebrasystem) Maxima]) und jedes Softwarepaket geht unterschiedlich vor bei umformen von Gleichungen. Meist benutzt man sogenannte [http://de.wikipedia.org/wiki/Z-Transformation Z-Transformationen], die wiederum ein sehr schwieriges Thema in der Mathematik darstellen. Im Folgenden wird Maple benutzt um eine solche Lösung mit einem CAS zu demonstrieren.

===Einführung Maple===

1980 wurde durch Keith O. Geddes und Gastón H. Gonnet die erste Version von Maple programmiert. Inzwischen ist es bei Version 14 angekommen und hat somit bereits eine eigene Geschichte von Optimierungen hinter sich. Das Lösen der Anwandsgleichung wird hier duch den Befehl [http://www.maplesoft.com/support/help/Maple/view.aspx?path=rsolve ''rsolve''] erledigt. Er verlangt als erstes Argument eine Liste mit Elementen und als zweites Argument ein Element nachdem aufgelöst werden soll.


Beispiel Fibonacci:

:Eingabe:

 lsg1 := rsolve({T(0) = 0, T(1) = 1, T(n) = T(n-1)+T(n-2)}, T(n));


:Ausgabe:

:<math>-1/5\, \sqrt{5} \left( 1/2-1/2\, \sqrt{5} \right) ^{n}+1/5\, \sqrt{5} \left( 1/2+1/2\, \sqrt{5} \right) ^{n}</math>


Als nächstes kann man sich mit dem Befehl [http://www.maplesoft.com/support/help/Maple/view.aspx?path=simplify%2fdetails ''simplify''] die Gleichung vereinfachen lassen.


:Eingabe:

 simplify(lsg1);


:Ausgabe:

:<math>-1/5\, \sqrt{5} \left(  \left( 1/2-1/2\, \sqrt{5} \right) ^{n}- \left( 1/2+1/2\, \sqrt{5} \right) ^{n} \right)</math>


Für die Darstellung in dezimaler Form gibt es dann noch den Befehl [http://www.maplesoft.com/support/help/AddOns/view.aspx?path=evalf ''evalf'']. Er hilft hier dabei die asymtoptische Ordnung <math>\mathcal{O}</math> leichter abzuschätzen. Das Argument ist in diesem Fall dasselbe wie bei ''simplify'' und nicht dessen Ausgabe.


:Eingabe:

 evalf(lsg1);


:Ausgabe:

:<math>- 0.4472135954\, \left( - 0.6180339880\\
\mbox{} \right) ^{n}+ 0.4472135954\,{ 1.618033988\\
\mbox{}}^{n}</math>


Hier kann man die asymptotische Ordnung direkt abgelesen werden: <math>\mathcal{O}(c^{n})</math>. Der Aufwand für die Fibonacci Folge ist damit exponentiell.

== Raten und Einsetzen == 

Die wohl intuitivste Methode zur Findung der Aufwandsfunktion <math>T(n)</math> ist sich die ersten Schritte in der Wertetabelle anzusehen und durch (intelligentes) Raten auf die Funktion zu kommen. Als Beispiel soll folgende Rekursionsgleichung dienen:

:<math>T(1)=1</math>
:<math>T(n)=3\cdot T\left(\frac{n}{2}\right)+n </math>


Auch diese lässt sich wieder einfach in Scheme angeben:

<code id="4d979f54dea25">(define t
  (lambda (n)
    (if (= n 1)
         1
         (+ (* 3 (t (/ n 2))) n))))</code>
<run id="4d979f54deb13">
(t 256)
</run>


Schon bei dem Versuch <math>n=3</math> scheitert man praktisch daran das <math>T(\tfrac{1}{2})</math> noch nicht definiert ist (da nur natürliche ganze Zahlen für <math>n</math> eingesetzt werden dürfen) bzw. das man eine Endlosschleife betritt. Um das zu umgehen setzt man nur Zweierpotenzen ein 

<math>n=2^{k}</math> mit ''k = 1,2,3,....''


Daraus ergibt sich folgende Wertetabelle:

{|class="wikitable"
|-
| <math>n</math>||<math>T(n)</math>
|-
| <math>1</math>||<math>1</math>
|-
| <math>2</math>||<math>5=3\cdot 1+2</math>
|-
| <math>4</math>||<math>19=3\cdot(3\cdot 1+2)+4</math>
|-
| ||<math>19=3^2\cdot 1+3\cdot 2+2^2</math>
|-
| <math>8</math>||<math>65=3\cdot(3^2\cdot 1+3\cdot 2+2^2)+8</math>
|-
| ||<math>65=3^3\cdot 1+3^2\cdot 2+3\cdot 2^2+2^3</math>
|-
| <math>16</math>||<math>211=3\cdot(3^3\cdot 1+3^2\cdot 2+3\cdot 2^2+2^3)+16</math>
|-
| ||<math>211=3^4\cdot 1+3^3\cdot 2+3^2\cdot 2^1+3\cdot 2^3+2^4</math>
|-
| <math>32</math>||<math>665</math>
|-
| <math>64</math>||<math>2059</math>
|}


Wenn man sich hier die Potenzenschreibweise ansieht kann man folgenden Zusammenhang für <math>2</math> und <math>3</math> vermuten und anschließend Umformen:

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

Mit Hilfe von [http://de.wikipedia.org/wiki/Formelsammlung_Algebra#Potenzsummen Potenzsummen] Gesetzen und der Formel:<math> \sum_{i=m}^k (x)^i = \frac{x^m-x^{k+1}}{x^m-x}</math> kann die Gleichung wie folgt umgewandelt werden:

 <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>\to T(2^k)=3^k\cdot\frac{1-\left(\frac{2}{3}\right)^{k+1}}{\frac{1}{3}}</math>
 
 <math>\to T(2^k)=3^k\cdot 3\cdot\Bigg(1-\left(\frac{2}{3}\right)^{k+1}\Bigg)</math>
 
 <math>\to T(2^k)=3^{k+1}\cdot\Bigg(1-\left(\frac{2}{3}\right)^{k+1}\Bigg)</math>
 
 <math>\to T(2^k)=3^{k+1}-2^{k+1}</math>


Da bis jetzt nur mit <math>T(2^k)</math> gerechnet wurde, wird eine Substiution gesucht die <math>T:n \rightarrow T(n)</math> abbildet. Da <math>n=2^k</math> festgelegt wurde und da <math>\log_a{b}=c \Leftrightarrow a^c=b </math> ist, muss für <math>k</math> einfach nur <math>k=\log_2{n}</math> substituiert werden. 

 <math> T(n)=3^{\log_2{n}+1}-2^{\log_2{n}+1}</math>
 
 <math>\to T(n)=3\cdot 3^{\log_2{n}}-2\cdot 2^{\log_2{n}}</math>


Mit folgender Formel kann man weiter vereinfachen: <math> a^{\log_a{b}}=b </math>

 <math> T(n)=3\cdot 3^{\log_2{n}}-2\cdot n</math>


Somit ist aus <math>2^{\log_2{n}}</math> einfach <math>n</math> geworden. Mit etwas Überlegung kann durch den Beweis weiter unten für <math>3^{\log_2{n}}</math> direkt <math> n^{\log_2{3}}</math> einsetzen. 

 <math> T(n)=3\cdot n^{\log_2{3}}-2\cdot n</math>
<popup name=Beweis>
===Beweis: <math>3^{\log_2 n}=n^{\log_2 3}</math>===

Benutzt werden folgende Gesetze
{|class="wikitable"
|-
|'''Logarithmus Gesetz I''' ||<math>\log_a a^{b}=b</math>
|-
|'''Logarithmus Gesetz II''' ||<math>\log_a b = \tfrac{log_w b}{log_w a}</math>
|}

Beweis von <math>3^{\log_2 n}=n^{\log_2 3}</math> durch Umformen bis <math>Term1=x</math> gleich <math>x=Term2</math> mit {a,b,c} fur {3,2,n} zur Verallgemeinerung:

{|class="wikitable"
|-
| Nr.|| Zwischenergebnis || Umformungsschritt
|-
| ||<math>\to a^{\log_b c}=x=c^{\log_b a}</math> ||Wahl von <math>c^{\log_b a}=x</math> als Start
|-
| 1||<math>\to c^{\log_b a}=x</math> ||Erweitern auf beiden Seiten mit <math>log_c</math>
|-
| 2||<math>\to \log_c c^{\log_b a}=\log_c x</math> ||Umformen nach '''I'''
|-
| 3||<math>\to \log_b a =\log_c x</math>||Umformen nach '''II''' und <math>w \to c</math>
|-
| 4||<math>\to \tfrac{\log_c a}{\log_c b}=\log_c x</math>||Erweitern beider Seiten mit <math>\log_c b</math> und <math>\tfrac{1}{\log_c x}</math>
|-
| 5||<math>\to \tfrac{\log_c a}{\log_c x}=\log_c b</math>||Umformen nach '''II'''
|-
| 6||<math>\to \log_x a=\log_c b</math>||Umformen nach '''II''' mit <math>w \to a</math> links und <math>w \to b</math> rechts
|-
| 7||<math>\to \tfrac{\log_a a}{\log_a x}=\tfrac{\log_b b}{\log_b c}</math>||Vereinfachen
|-
| 8||<math>\to \tfrac{1}{\log_a x}=\tfrac{1}{\log_b c}</math>||auf beiden Seiten das Reziproke bilden
|-
| 9||<math>\to \log_a x =\log_b c</math>||Rechte Seite Umformen nach '''I''' mit <math>\log_a a</math>
|-
| 10||<math>\to \log_a x =\log_a a^{\log_b c}</math>||auf beiden Seiten Division durch <math>\log_a</math>
|-
| 11||<math>\to x =a^{\log_b c}</math>||Ziel erreicht
|}
</popup>


Da man bei der asymptotischen Ordnung nur das schwerwiegendste Element der Gleichung berücksichtigt wird lautet das Ergebnis:

 <math>T(n)=\mathcal{O}\left(n^{\log_2{3}}\right)</math>
 <math>T(n)=\mathcal{O}\left(\approx n^{1.5849}\right)</math>

== Konstruktive Induktion == 


Es gibt die Möglichkeit mittels einer [http://de.wikipedia.org/wiki/Vollst%C3%A4ndige_Induktion ''vollständigen Induktion''] den Aufwand einer Rekursionsgleichung zu ermitteln. Im Prinzip beweist man das eine Funktion für das Startelement und für alle folgenden Elemente oberhalb der gegebenen Rekursionsgleichung liegt. Da man nicht ausschließen kann, dass es keine Lösung gibt, muss man hier die sogenannte [http://de.wikipedia.org/wiki/Beweis_(Mathematik)#Konstruktive_und_nicht-konstruktive_Beweise konstruktive Methode] anwenden. Zu erst einmal wird auf konstruktive Weise eine Ausgangsgleichung ermittelt.Sieht man sich den Graphen weiter oben an, kann man vermuten das es sich um einen exponentiellen Aufwand (an Speicher) handelt. Folgende Aufwandsordnung würde man also daraus entnehmen:

 <math> T(n) = \mathcal{O}(c^n)</math>

;Definition der Groß-O Notation
:<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 positive reelle Zahl <math> c </math> gibt, sodass ab einem gewissen <Math>n_{0} \in\mathbb{N}</math> sämtliche Funktionswerte <math> c\cdot f(n)</math> oberhalb von <math> t(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\cdot c^{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>

-Vermutung expon. Funktion

-Induktionsanfang

-Induktionsschritt

-Beweis das Omega(...) für T(n) gilt

...

== Iterationsmethode == 
(20min.)

-Expansion der Gleichung

-Ableitung der Summenformel

-log Umformung

...


== Die Meistermethode == 
(20min.)

-Einleitung: T(n)= a * T(n/b) + f(n)

-3 Fallunterscheidungen

-Anwendung nach Fall 2

-Anwendung nach Fall 3

-wann nicht anwenden

...


== Aufgaben ==

# '''Computeralgebrasysteme(10min.)'''
# '''Raten und Einsetzen(20min.)'''
# '''Konstruktive Induktion(20min.)'''
# '''Iterationsmethode(20min.)'''
# '''Mastermethode(20min.)'''

...


=== Lösungen ===

...