Hilfsmittel Mathematik 2 SS11
Inhaltsverzeichnis |
Autor:
Bernd Schönlebe s3bescho@stud.hs-zigr.de
Rekursionsgleichungen (Differenzengleichung)
Bereits eine leicht verständliche Definition der 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 Fibonacci Folge Fn :
- F_n = F_{n-1} + F_{n-2},\!\,
- mit den Startwerten
- F_0 = 0 \quad\text{und}\quad F_1 = 1 und n \ge 2
- Die Mathematische Definition der Fibonacci Folge Fn :
Hier ein Beispiel zum Testen in Scheme:
Die Folge ist nach OEIS|A000045 genormt. Hier ein Auszug aus der Tabelle
- {| class="wikitable" style="text-align:right"
! style="padding-left:1em;" | n ! style="padding-right:1em;" | Fn ! style="padding-left:1em;" | n ! style="padding-right:1em;" | Fn ! style="padding-left:1em;" | n ! style="padding-right:1em;" | Fn ! style="padding-left:1em;" | n ! style="padding-right:1em;" | Fn ! style="padding-left:1em;" | n ! style="padding-right:1em;" | Fn |- | style="padding-left:1em;"| 0 || style="padding-right:1em;" | 0 || style="padding-left:1em;"| 10 || style="padding-right:1em;" | 55 || style="padding-left:1em;"| 20 || style="padding-right:1em;" | 6.765 || style="padding-left:1em;"| 30 || style="padding-right:1em;" | 832.040 || style="padding-left:1em;"| 40 || style="padding-right:1em;" | 102.334.155 |- | style="padding-left:1em;"| 1 || style="padding-right:1em;" | 1 || style="padding-left:1em;"| 11 || style="padding-right:1em;" | 89 || style="padding-left:1em;"| 21 || style="padding-right:1em;" | 10.946 || style="padding-left:1em;"| 31 || style="padding-right:1em;" | 1.346.269 || style="padding-left:1em;"| 41 || style="padding-right:1em;" | 165.580.141 |- | style="padding-left:1em;"| 2 || style="padding-right:1em;" | 1 || style="padding-left:1em;"| 12 || style="padding-right:1em;" | 144 || style="padding-left:1em;"| 22 || style="padding-right:1em;" | 17.711 || style="padding-left:1em;"| 32 || style="padding-right:1em;" | 2.178.309 || style="padding-left:1em;"| 42 || style="padding-right:1em;" | 267.914.296 |- | style="padding-left:1em;"| 3 || style="padding-right:1em;" | 2 || style="padding-left:1em;"| 13 || style="padding-right:1em;" | 233 || style="padding-left:1em;"| 23 || style="padding-right:1em;" | 28.657 || style="padding-left:1em;"| 33 || style="padding-right:1em;" | 3.524.578 || style="padding-left:1em;"| 43 || style="padding-right:1em;" | 433.494.437 |- | style="padding-left:1em;"| 4 || style="padding-right:1em;" | 3 || style="padding-left:1em;"| 14 || style="padding-right:1em;" | 377 || style="padding-left:1em;"| 24 || style="padding-right:1em;" | 46.368 || style="padding-left:1em;"| 34 || style="padding-right:1em;" | 5.702.887 || style="padding-left:1em;"| 44 || style="padding-right:1em;" | 701.408.733 |- | style="padding-left:1em;"| 5 || style="padding-right:1em;" | 5 || style="padding-left:1em;"| 15 || style="padding-right:1em;" | 610 || style="padding-left:1em;"| 25 || style="padding-right:1em;" | 75.025 || style="padding-left:1em;"| 35 || style="padding-right:1em;" | 9.227.465 || style="padding-left:1em;"| 45 || style="padding-right:1em;" | 1.134.903.170 |- | style="padding-left:1em;"| 6 || style="padding-right:1em;" | 8 || style="padding-left:1em;"| 16 || style="padding-right:1em;" | 987 || style="padding-left:1em;"| 26 || style="padding-right:1em;" | 121.393 || style="padding-left:1em;"| 36 || style="padding-right:1em;" | 14.930.352 || style="padding-left:1em;"| 46 || style="padding-right:1em;" | 1.836.311.903 |- | style="padding-left:1em;"| 7 || style="padding-right:1em;" | 13 || style="padding-left:1em;"| 17 || style="padding-right:1em;" | 1.597 || style="padding-left:1em;"| 27 || style="padding-right:1em;" | 196.418 || style="padding-left:1em;"| 37 || style="padding-right:1em;" | 24.157.817 || style="padding-left:1em;"| 47 || style="padding-right:1em;" | 2.971.215.073 |- | style="padding-left:1em;"| 8 || style="padding-right:1em;" | 21 || style="padding-left:1em;"| 18 || style="padding-right:1em;" | 2.584 || style="padding-left:1em;"| 28 || style="padding-right:1em;" | 317.811 || style="padding-left:1em;"| 38 || style="padding-right:1em;" | 39.088.169 || style="padding-left:1em;"| 48 || style="padding-right:1em;" | 4.807.526.976 |- | style="padding-left:1em;"| 9 || style="padding-right:1em;" | 34 || style="padding-left:1em;"| 19 || style="padding-right:1em;" | 4.181 || style="padding-left:1em;"| 29 || style="padding-right:1em;" | 514.229 || style="padding-left:1em;"| 39 || style="padding-right:1em;" | 63.245.986 || style="padding-left:1em;"| 49 || style="padding-right:1em;" | 7.778.742.049 |- |}
Grob gesagt ist ein Element die Summe seiner beiden Vorgänger. Hier ist der Aufwand linear, d.h. zur Berechnung von Fn 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 n=20:
GNUPlot-Quelltext
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>
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. T_1(n)=n^2 oder T_2(n)=2\cdot n^3+5\cdot n^2-12 und man kann daran bereits die Aufwandsordnung nach der Groß-O-Notation ablesen:T_1 liegt in \mathcal{O}(n^2). T_2 liegt in \mathcal{O}(n^3). Sobald man jedoch Algorithmen entwirft, entstehen Gleichungen wie z.B. T(n)=f(T(n-1)) und es ist nicht mehr so einfach den Aufwand abzulesen. Wie erhält man nun die explizite Form für T(n) das von keinem anderen T(i) abhängt? Also der Form T(n)=f(n) 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 Computeralgebrasysteme (kurz CAS). Das sind Programme, die neben dem numerischen auch das symbolische Rechnen beherrschen. Normalerweise würde ein Taschenrechner folgenden Bruch 1/3 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. Maple, Mathematica, Matlab, Maxima) und jedes Softwarepaket geht unterschiedlich vor bei umformen von Gleichungen. Meist benutzt man sogenannte 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.
Verwendung von 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 ''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:
- -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}
Als nächstes kann man sich mit dem Befehl ''simplify'' die Gleichung vereinfachen lassen.
- Eingabe:
simplify(lsg1);
- Ausgabe:
- -1/5\, \sqrt{5} \left( \left( 1/2-1/2\, \sqrt{5} \right) ^{n}- \left( 1/2+1/2\, \sqrt{5} \right) ^{n} \right)
Für die Darstellung in dezimaler Form gibt es dann noch den Befehl ''evalf''. Er hilft hier dabei die asymtoptische Ordnung \mathcal{O} leichter abzuschätzen. Das Argument ist in diesem Fall dasselbe wie bei simplify und nicht dessen Ausgabe.
- Eingabe:
evalf(lsg1);
- Ausgabe:
- - 0.4472135954\, \left( - 0.6180339880\\ \mbox{} \right) ^{n}+ 0.4472135954\,{ 1.618033988\\ \mbox{}}^{n}
Hier kann man die asymptotische Ordnung direkt abgelesen werden: \mathcal{O}(c^{n}). Der Aufwand für die Fibonacci Folge ist damit exponentiell.
Raten und Einsetzen
Die wohl intuitivste Methode zur Findung der Aufwandsfunktion T(n) ist sich die ersten Schritte in der Wertetabelle anzusehen und durch (intelligentes) Raten auf die Funktion zu kommen. Als Beispiel soll folgende Rekursionsgleichung dienen:
- T(1)=1
- T(n)=3\cdot T\left(\frac{n}{2}\right)+n
Auch diese lässt sich wieder einfach in Scheme angeben:
Schon bei dem Versuch n=3 scheitert man praktisch daran das T(\tfrac{1}{2}) noch nicht definiert ist (da nur natürliche ganze Zahlen für n eingesetzt werden dürfen) bzw. das man eine Endlosschleife betritt. Um das zu umgehen setzt man nur Zweierpotenzen ein
n=2^{k} mit k = 1,2,3,....
Daraus ergibt sich folgende Wertetabelle:
| n | T(n) |
| 1 | 1 |
| 2 | 5=3\cdot 1+2 |
| 4 | 19=3\cdot(3\cdot 1+2)+4 |
| 19=3^2\cdot 1+3\cdot 2+2^2 | |
| 8 | 65=3\cdot(3^2\cdot 1+3\cdot 2+2^2)+8 |
| 65=3^3\cdot 1+3^2\cdot 2+3\cdot 2^2+2^3 | |
| 16 | 211=3\cdot(3^3\cdot 1+3^2\cdot 2+3\cdot 2^2+2^3)+16 |
| 211=3^4\cdot 1+3^3\cdot 2+3^2\cdot 2^1+3\cdot 2^3+2^4 | |
| 32 | 665 |
| 64 | 2059 |
Wenn man sich hier die Potenzenschreibweise ansieht kann man folgenden Zusammenhang für 2 und 3 vermuten und anschließend Umformen:
T(2^k)=\sum_{i=0}^k 3^{k-i}\cdot 2^i \to T(2^k)=\sum_{i=0}^k 3^{k}\cdot 3^{-i}\cdot 2^i \to T(2^k)=\sum_{i=0}^k 3^{k}\cdot\frac{1}{3^i}\cdot 2^i \to T(2^k)=\sum_{i=0}^k 3^{k}\cdot\frac{2^i}{3^i} \to T(2^k)=\sum_{i=0}^k 3^{k}\cdot\left(\frac{2}{3}\right)^i \to T(2^k)=3^{k} \sum_{i=0}^k \left(\frac{2}{3}\right)^i
Mit Hilfe von Potenzsummen Gesetzen und der Formel: \sum_{i=m}^k (x)^i = \frac{x^{k+1}-x^m}{x-1} kann die Gleichung wie folgt umgewandelt werden:
T(2^k)=3^k \cdot \tfrac{\tfrac{2}{3}^{k+1}-\tfrac{2}{3}^0}{\tfrac{2}{3}-1} \to T(2^k)=3^k\cdot\tfrac{\tfrac{2}{3}^{k+1}-1}{-\frac{1}{3}} \to T(2^k)=3^k\cdot (-3) \cdot((\tfrac{2}{3})^{k+1}-1) \to T(2^k)=-3^{k+1}\cdot((\tfrac{2}{3})^{k+1}-1) \to T(2^k)=-2^{k+1} + 3^{k+1}
\to T(2^k)=3^{k+1} -2 ^{k+1}Da bis jetzt nur mit T(2^k) gerechnet wurde, wird eine Substiution gesucht die T:n \rightarrow T(n) abbildet. Da n=2^k festgelegt wurde und da \log_a{b}=c \Leftrightarrow a^c=b ist, muss für k einfach nur k=\log_2{n} substituiert werden.
T(n)=3^{\log_2{n}+1}-2^{\log_2{n}+1} \to T(n)=3\cdot 3^{\log_2{n}}-2\cdot 2^{\log_2{n}}
Mit folgender Formel kann man weiter vereinfachen: a^{\log_a{b}}=b
T(n)=3\cdot 3^{\log_2{n}}-2\cdot nSomit ist aus 2^{\log_2{n}} einfach n geworden. Mit etwas Überlegung kann durch den Beweis weiter unten für 3^{\log_2{n}} direkt n^{\log_2{3}} einsetzen.
T(n)=3\cdot n^{\log_2{3}}-2\cdot nBeweis
Beweis: 3^{\log_2 n}=n^{\log_2 3}
Benutzt werden folgende Gesetze
| Logarithmus Gesetz I | \log_a a^{b}=b |
| Logarithmus Gesetz II | \log_a b = \tfrac{log_w b}{log_w a} |
Beweis von 3^{\log_2 n}=n^{\log_2 3} durch Umformen bis Term1=x gleich x=Term2 mit {a,b,c} fur {3,2,n} zur Verallgemeinerung:
| Nr. | Zwischenergebnis | Umformungsschritt |
| \to a^{\log_b c}=x=c^{\log_b a} | Wahl von c^{\log_b a}=x als Start | |
| 1 | \to c^{\log_b a}=x | Erweitern auf beiden Seiten mit log_c |
| 2 | \to \log_c c^{\log_b a}=\log_c x | Umformen nach I |
| 3 | \to \log_b a =\log_c x | Umformen nach II und w \to c |
| 4 | \to \tfrac{\log_c a}{\log_c b}=\log_c x | Erweitern beider Seiten mit \log_c b und \tfrac{1}{\log_c x} |
| 5 | \to \tfrac{\log_c a}{\log_c x}=\log_c b | Umformen nach II |
| 6 | \to \log_x a=\log_c b | Umformen nach II mit w \to a links und w \to b rechts |
| 7 | \to \tfrac{\log_a a}{\log_a x}=\tfrac{\log_b b}{\log_b c} | Vereinfachen |
| 8 | \to \tfrac{1}{\log_a x}=\tfrac{1}{\log_b c} | auf beiden Seiten das Reziproke bilden |
| 9 | \to \log_a x =\log_b c | Rechte Seite Umformen nach I mit \log_a a |
| 10 | \to \log_a x =\log_a a^{\log_b c} | auf beiden Seiten Division durch \log_a |
| 11 | \to x =a^{\log_b c} | Ziel erreicht |
Da man bei der asymptotischen Ordnung nur das schwerwiegendste Element der Gleichung berücksichtigen muss lautet das Ergebnis:
T(n)=\mathcal{O}\left(n^{\log_2{3}}\right) T(n)=\mathcal{O}\left(\approx n^{1.5849}\right)
Konstruktive Induktion
Es gibt die Möglichkeit mittels einer ''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 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:
T(n) = \mathcal{O}(c^n)- Definition der Groß-O Notation
- \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 positive reelle Zahl c gibt, sodass ab einem gewissen n_{0} \in\mathbb{N} sämtliche Funktionswerte c\cdot f(n) oberhalb von t(n) liegen.
Daraus kann man folgende Ungleichung ableiten, die zu es zu beweisen gilt:
T(n)\le a\cdot c^{n}Induktionsanfang
Als erstes soll die Funktion für die ersten beiden Elemente der Rekursionsgleichung bewiesen werden. Da aus der Definition der Fibonacci Folge T(0)=0 und T(1) = 1 ist kann man wie folgt anfangen:
T(0)=0\le a\cdot c^{0} T(1)=1\le a\cdot^{1}
Schon im ersten Fall ergibt sich, dass c^{0}=1 ist und es somit schon aussreicht wenn a\ge1 ist. Um beide Fälle abzudecken reicht also schon a=1 zu setzen.
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) \to T(n)\:\:\le\:\: a\cdot c^{n-1}+a\cdot c^{n-2} \to T(n)\:\:\le\:\: a\cdot c^{n}\cdot c^{-1}+ a\cdot c^{n}\cdot c^{-2} \to T(n)\:\:\le\:\: a\cdot c^{n}\cdot\left(\frac{1}{c}+\frac{1}{c^{2}}\right) \to T(n)\:\:\le\:\: a\cdot c^{n}\cdot\left(\frac{c}{c^{2}}+\frac{1}{c^{2}}\right) \to T(n)\:\:\le\:\: a\cdot c^{n}\cdot\frac{c+1}{c^{2}}
Damit kann man sagen dass T(n)\le a\cdot c^{n} gilt, wenn \frac{c+1}{c^{2}}=1 ist.
0\quad\,=\:\: c^{2}-c-1 \to c _{1/2}=\:\: (\frac{1}{2})_{-}^{+}\sqrt{\frac{1}{4}+1} \to c_{1}\:\:=\:\: \frac{1+\sqrt{5}}{2}, c_{2}\:\:=\:\: \frac{1-\sqrt{5}}{2}
Da die Wurzel von 5 \sqrt{5}>2 ist und somit c_{2} einen negativer Wert erhalten würde, kann man ihn vernachlässigen. Die Lösung der Gleichung ist demnach
c = \frac{1+\sqrt{5}}{2}\approx 1.618Der Aufwand der n-ten Fibonacci-Zahl lässt sich also wie folgt berechnen:
T(n)\:\:=\:\:\mathcal{O}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}\right) T(n)\:\:=\:\:\mathcal{O}\left(\left\approx(1.618)^{n}\right)
Wenn man den dezimalen Wert von c nun nach oben und unten rundet, erhält man eine jeweils obere und untere Schranke für den Aufwand der n-ten Fibonacci-Zahl. Somit kann man sogar sagen so folgendes gilt:
T(n)\:\:=\:\:\Theta\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n}\right) Iterationsmethode
Ein Mittel mit mehr Automatisierung zur Lösung rekursiver Gleichungen ist die Iterationsmethode. Dazu benötigt man die rekursive Gleichung, sowie ein Wertpaar, welches ein n repräsentiert das rekursionsfrei ist. Hierfür wird meistens T(0) oder T(1) angegeben. Außerdem muss sie der Form T(n)=a\cdot T(\frac{n}{b})+f(n) entsprechen. Im folgenden wird das Beispiel aus dem Buch a=3 und b=4, sowie f(n)=n verwendet (Siehe Seite 52).
T(n)=3\cdot T(\frac{n}{4})+n T(1)=1
Nun versucht man die Gleichung solang zu iterieren bis man einen Ausdruck erhält der rekursionsfrei ist. Dieser Prozess ist meistens endlich. Allerdings braucht man dazu eine hergeleitete rekursive Bildungsvorschrift, das sogennate Telescoping. Daraus muss anschließend eine explizite Bildungsvorschrift zur Bestimmung der Ordnung abgeleitet bewerden. Hier wird es nun am Beispiel vorgeführt:
Telescoping Gegeben sei die Aufwandsfunktion T(n) mit
T(n)=3\cdot T(\frac{n}{4})+n Jetzt iteriert man einfach einmal weiter, d.h. man setzt für T(\tfrac{n}{4}) einfach wieder dieselbe Funktion ein und erhält
T(\frac{n}{4})=3\cdot T(\frac{n}{16})+\frac{n}{4} \to T(n)=3\cdot (3\cdot T(\frac{n}{16})+\frac{n}{4})+n
Zusammengefasst kann man schon die rekursive Bildungsvorschrift sehen
T(n)=3^{2}\cdot T(\frac{n}{4^{2}})+3^{1}\cdot \frac{n}{4^{1}}+nAllgemein betrachtet kann man sagen
T(n) = 3^{k}\cdot T(\frac{n}{4^{k}})+3^{k-1} \cdot \frac{n}{4^{k-1}} + nAuch diese kann man wieder in Kurzschreibweise zusammenfassen
T(n)=3^{k}\cdot T(\frac{n}{4^{k}})+\sum_{i=0}^{k-1}(\frac{3}{4})^{i}\cdot nVon der Aufgabenstellung her kann man entnehmen das T(n) nur für n=1 rekursionsfrei ist. Als muss eine Rekursion auf T(1) enden und zwar in der Form
T(\frac{n}{4^{k}})=T(1) \frac{n}{4^{k}}=1
Da man diesen Term nach k umstellen kann erhält man
\to k=\log_4 nSetzt man diesen Ausdruck nun für k ein erhält man die explizite Gleichung
T(n)= 3^{\log_4 n}\cdot 1 +n\cdot \sum_{i=0}^{\log_4 n -1} (\frac{3}{4})^{i}Wie schon bei der konstruktiven Induktion kann man diese geometrische Reihe wie folgt umformen
T(n) = 3^{\log_4 n}+n\cdot(\frac {1-(\frac{3}{4})^{\log_4 n}} {1-\frac{3}{4}} ) Ebenfalls wie bei der konstruktiven Induktion kann man auch hier die Umformung des Logarithmus mittels a^{\log_b c}=c^{\log_b a} anwenden
T(n) = n^{\log_4 3}+ n\cdot \frac{1- n^{\log_4 \frac{3}{4}}}{1- \frac{3}{4}} \to n^{\log_4 3}+ n\cdot \frac{1-n^{\log_4 3 - \log_4 4}}{\frac{1}{4}} \to n^{\log_4 3}+4n\cdot (1-n^{\log_4 3}\cdot n^{-1})
Fasst man das noch zusammen erhält man schließlich:
T(n) = 4n-3n^{\log_4 3}Aus der Überlegung das \log_4 3 < 1 und \log_4 3\approx 1 ist, ergibt sich der Aufwand für T(n) als
T(n) = \mathcal{O}(n)Die Meistermethode
Nun kann es aber sein, dass die Restfunktion f(n) eine höhere Ordnung hat als der T(n) Teil und somit ab einem bestimmten n größer wird als T(n). Um zu überprüfen ob dieser Fall vorliegt wurde die Meistermethode eingeführt. Bedingung dafür ist eine Gleichung der folgenden Form
T(n) =a\cdot T(\frac{n}{b})+f(n) Dabei wird verglichen ob es in eine Aufwandsklasse passt oder nicht. Da man hier von der exponentiellen Ordnung ausgeht, entscheidet also der Exponent darüber, ob eine Klasse der anderen zugehört oder umgekehrt. Man setzt die beiden Ordnungen gleich und ermittelt \epsilon. Dazu benutzt man die Formel
\mathcal{O}(n^{\log_b a+\epsilon})=\mathcal{O}(f(n))Es ergeben sich also 3 verschiedene Fälle für \epsilon, die zu betrachten sind
- \epsilon < 0
- \epsilon = 0
- \epsilon > 0
1.Fall \epsilon < 0
Da man von der exponentiellen Ordnung ausgeht, hat eine kleinere Ordnung für f(n) ,also \mathcal{O}(f(n))<\mathcal{O}(T(n)), zur Folge, dass f(n) \in \mathcal{O}(n^{\log_b a}) ist, also f(n) untergeordnet und vernachlässigbar ist. Der Aufwand für die Gleichung ist somit der von T(n).
Beispiel
Beispiel
Gegeben sei folgende Gleichung
T(n)=4\cdot T(\frac{n}{2})+ 80nZum Vergleich der Ordnung erhält man
\mathcal{O}(n^{\log_2 4+\epsilon})=\mathcal{O}(n) \to \mathcal{O}(n^{2+\epsilon})=\mathcal{O}(n)
Somit erhält man für \epsilon = -1 und der 1. Fall mit \epsilon <0 ist bestätigt. Der Aufwand beträgt also
T(n)=\mathcal{O}(n^{\log_2 4}) =\mathcal{O}(n^{2})
2.Fall \epsilon = 0
Für \epsilon = 0 ergibt sich die gleiche Ordnung für beide Teile und somit kann man keins von beiden vernachlässigen. Damit kann man sagen das f(n) die asymptotisch scharfe Schranke von T(n) ist und damit f(n) \in \Theta(n^{\log_b a}) gilt. Die Addition ist hier folgendermaßen definiert:
T(n)=\mathcal{O}(n^{\log_b a}\cdot \log_b(n))Beispiel
Beispiel
Gegeben sei folgende Gleichung
T(n)=8\cdot T(\frac{n}{2})+1000n^{3}Setzt man die Ordnungen wieder gleich erhält man
\mathcal{O}(n^{\log_2 8 +\epsilon})=\mathcal{O}(n^{3})Da \epsilon in diesem Fall 0 ist, ergibt sich der Aufwand aus
T(n)=\mathcal{O}(n^{3}\cdot \log_2 n)3.Fall \epsilon > 0
Tritt nun doch der Fall ein das der Restteil überwiegt, muss man noch prüfen ob es für folgende Gleichung
a\cdot f(\frac{n}{b})\leq c\cdot f(n) ein c gibt, welches zwischen 1 und 0 liegt. Wenn 0<c<1 gilt, ist der Aufwand der des Resteils
T(n)=\Theta(f(n))Beispiel
Beispiel
Gegeben sei folgende Gleichung
T(n)=3\cdot T(\frac{n}{3})+n^{2}Jetzt stellt man wieder die Ordnungen gleich und vergleicht sie
\mathcal{O}(n^{1+\epsilon})=\mathcal{O}(n^{2})\epsilon = 1 ist also größer als 0 und der dritte Fall tritt ein. Nach der allgemeinen Form der Aufwandsgleichung T(n) gilt hier a=b=3, f(n)=n^{2}. Als nächstes stellt man folgende Ungleichung auf
3\cdot (\frac{n}{3})^{2}\leq c\cdot n^{2} \to \frac{1}{3} \cdot n^{2} \leq c\cdot n^{2}
Für c ergibt sich also c \geq \frac{1}{3} und somit dass 0<c<1 liegt. Das Ergebnis lautet:
T(n)=\mathcal{O}(n^{2})Wann nicht anwenden
Beispiel
Beispiel
Folgende Gleichung kann nicht mit der Meister Methode getestet werden
T(n)=2\cdot T(\frac{n}{2})+n\cdot \log_2 nAufgaben
Raten und Einsetzen Gegeben:
- T(1)=1
- T(n)=2\cdot T(\tfrac{n}{3}) + 4\cdot n
Aufgabe:
- Berechnen Sie die Aufwandsordnung von T(n)
Lösungen
Raten und Einsetzen
Lösung
Gegeben:
- T(1)=1
- T(n)=2\cdot T(\tfrac{n}{3}) + 4\cdot n
Aufgabe:
- Berechnen Sie die Aufwandsordnung von T(n)
Lösung:
1. n durch n=3^{k} ersetzen
Da die rekursive Gleichung auf ein rekursionsfreies Element enden muss, kann man nur bestimmte n einsetzen, sodass man n durch n=b^{k} ersetzt, wobei b der Teiler von n ist. Also setzt man ein:
- n=3^{k}
2. Einsetzen und Tabelle aufstellen
Als nächstes stellt man eine Tabelle auf, welche die Ergebnisse für die ersten k beinhaltet. Dazu setzt man für T(\tfrac{n}{3}) einfach den vorhergehenden Lösungs Term ein.
| k | n | T(n) |
| 0 | 3^{0} | 4 |
| 1 | 3^{1} | 2 \cdot (4) + 4 \cdot 3 ^ {1} |
| 2 | 3^{2} | 2 \cdot (2 \cdot (4) + 4 \cdot 3 ^ {1}) + 4 \cdot 3 ^ {2} |
| 2 ^ {2} \cdot 4 + 2 \cdot 4 \cdot 3 ^{1} + 4 \cdot 3 ^ {2} | ||
| 3 | 3^{3} | 2 \cdot (2 \cdot (2 \cdot (4) + 4 \cdot 3 ^ {1}) + 4 \cdot 3 ^ {2}) + 4 \cdot 3 ^ {3} |
| 2 ^ {3} \cdot 4 + 2 ^ {2} \cdot 4 \cdot 3 ^{1} + 2 \cdot 4 \cdot 3 ^{2} + 4 \cdot 3 ^ {3} | ||
| 4 | 3^{4} | 2 \cdot (2 \cdot (2 \cdot (2 \cdot (4) + 4 \cdot 3 ^ {1}) + 4 \cdot 3 ^ {2}) + 4 \cdot 3 ^ {3}) + 4 \cdot 3 ^ {4} |
| 2 ^ {4} \cdot 4 + 2 ^ {3} \cdot 4 \cdot 3 ^{1} + 2 ^ {2} \cdot 4 \cdot 3 ^{2} + 2 \cdot 4 \cdot 3 ^{3} + 4 \cdot 3 ^ {4} |
3. Explizite Bildungsvorschrift ableiten
Wenn man sich die Potenzen genauer ansieht, dann fallen sie für 2 und steigen für 3 von links nach rechts. Das kann man auch mit einem Summenzeichen ausdrücken. Man merke das man hier bereits kein Element T(n) mehr hat das von einem anderen T(i) abhängt!
T(n)=T(3^{k})=\sum_{i=0}^k 2^{k-i}\cdot 4 \cdot 3^i Diese kann man nun wieder weiter vereinfachen. Zuerst werden die Konstanten 4 und 2^{k} vor das Summenzeichen gezogen. Um 2^{k} zu erhalten, zerlegt man 2^{k-i} in 2^{k} \cdot 2^{-i}
\to T(3^k)=2^{k} \cdot 4 \cdot \sum_{i=0}^k 2^{-i} \cdot 3^{i} Einen negativen Exponenten kann man auch wie folgt schreiben
\to T(3^k)=2^{k} \cdot 4 \cdot \sum_{i=0}^k \tfrac{1}{2^{i}} \cdot 3^{i}= 2^{k} \cdot 4 \cdot \sum_{i=0}^k (\tfrac{3}{2})^{i}Durch Potenzsummen kann man folgende Formel anwenden
- \sum_{i=m}^k (x)^i = \frac{x^{k+1}-x^m}{x-1}
\to T(3^k)= 2^{k} \cdot 4 \cdot ( \tfrac {(\tfrac {3}{2})^{k+1} - 1}{(\tfrac {3}{2}) - 1} ) \to T(3^k)= 2^{k} \cdot 4 \cdot ( \tfrac {(\tfrac {3}{2})^{k+1} - 1}{(\tfrac {1}{2})} ) \to T(3^k)= 2^{k + 1} \cdot 4 \cdot ((\tfrac {3}{2})^{k+1} - 1)
Nun kann man schon ausklammern
\to T(3^k)= (\tfrac {3}{2})^{k+1} \cdot 2^{k + 1} \cdot 4 - 2^{k + 1} \cdot 4Mit Hilfe eines Potenzgesetzes kann man weiter vereinfachen
- (a\cdot b)^r = a^r\cdot b^r
\to T(3^k)= 4 \cdot 3^{k + 1} - 4 \cdot 2^{k + 1}Da bisher mit n=3^{k} gerechnet wurde, wird für k jetzt k=\log_3 n eingesetzt
\to T(n)= 4 \cdot (3^{\log_3 n + 1} - 2^{\log_3 n + 1})Auch hier kann man wieder die Potenzen aufspalten
\to T(n)= 4 \cdot (3 \cdot 3^{\log_3 n} - 2 \cdot 2^{\log_3 n})Und mit folgender Formel weiter vereinfachen
- a^{\log_a{b}}=b
\to T(n)= 4 \cdot (3 \cdot n - 2 \cdot 2^{\log_3 n})Aus dem Beweis weiter oben kann man nun weiter so fortfahren
- a^{\log_b c}=c^{\log_b a}
\to T(n)= 4 \cdot (3 \cdot n - 2 \cdot n^{\log_3 2})Da \log_3 2 < 1 ist, kann diese Potenz in der Aufwandsordnung vernachlässigt werden. Also gilt:
T(n) \in \mathcal{O}(n)