Hilfsmittel Mathematik 2 SS10

Aus ProgrammingWiki

Inhaltsverzeichnis

1 Rekursionsgleichungen
2 Iterationsmethode
3 Die Meistermethode
4 Folien
5 Aufgaben
- 5.1 Lösungen

Rekursionsgleichungen

Motivation

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

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

Fibonacci-Zahlen: $F(0)=1$; $F(1)=1$; $F(n)=F(n-1)+F(n-2)$ , mit $n\geq 2$

Offensichtlich gilt für den Zeitaufwand:

$T(0)=1$

$T(1)=1$

$T(n)=T(n-1)+T(n-2)$ , mit $n\geq 2$ .

Die nachfolgenden Abschnitte erläutern verschiedene Methoden, die zur Ermittlung des Aufwandes $T(n)=f(n)$ 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 rsolve(). Sie benötigt 2 Argumente. Das 1. Argument beinhaltet Wertepaare, während das 2. Argument die aufzulösende Funktionsbezeichnung be.... 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 und Werte, wenn möglich, gekürzt werden. Ihr Argument ist die jeweilige rsolve()-Funktion.

Schließlich gibt es noch die Funktion evalf(). Diese 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) versucht, den funktionalen Zusammenhang aus einer Wertetabelle "herauszuvermuten".

Sei die rekursive Gleichung $T(n)=3\cdot T\left(\frac{n}{2}\right)+2$ , mit $T(1)=1$ 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 $T(2)$ zu berechnen, kann man auf $T(1)$ zurückgreifen. Um $T(4)$ zu berechnen, muss man $T(2)$ 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 $n=3$ , also $T\left(\frac{3}{2}\right)$ ins Stocken geraten, da hierfür in der Wertetabelle (noch) kein Wert vorliegt.

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

$n$	$T(n)$
$1$	$1$
$2$	$3\cdot 1+2$
$4$	$3\cdot(3\cdot 1+2)+4$
	$3^2\cdot 1+3\cdot 2+2^2$
$8$	$3\cdot(3^2\cdot 1+3\cdot 2+2^2)+8$
	$3^3\cdot 1+3^2\cdot 2+3\cdot 2^2+2^3$
$16$	$3\cdot(3^3\cdot 1+3^2\cdot 2+3\cdot 2^2+2^3)+16$
	$3^4\cdot 1+3^3\cdot 2+3^2\cdot 2^2+3\cdot 2^3+2^4$

Wir vermuten den folgenden Zusammenhang:

Weitere Transformationen ergeben:

Anmerkung: Konstante Faktoren innerhalb der Summe können vor die Summe gestellt werden

Formel: $\sum_{i=m}^k (x)^i = \frac{x^m-x^{k+1}}{x^m-x}$

Bis zu diesem Punkt haben wir immer mit $T(2^k)$ gerechnet. Gesucht ist jedoch eine Funktion $T:n \rightarrow T(n)$ . Zu Beginn wurde die Vereinbarung $n=2^k$ getroffen. Da $\log_a{b}=c \Leftrightarrow a^c=b$ muss $k=\log_2{n}$ substituiert werden.

Formel: $a^{\log_a{b}}=b$

Aus der obigen Formel ergibt sich, dass wir für $2^{\log_2{n}}$ einfach $n$ schreiben dürfen. Auf $3^{\log_2{n}}$ ist dies nicht direkt anwendbar. Aus der Überlegung, dass $2^x=3$ ist, kann man schlussfolgern, dass $x=\log_2{3}$ . Nun kann man 3, mit $2^{\log_2{3}}$ ersetzen.

Das Ergebnis lautet:

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. Berechnet man einige Werte der Fibonacci-Folge, stellt man fest, dass sich der Aufwand mit einer exponentiellen Aufwandsfunktion beschreiben lässt.

Daher ergibt sich zunächste folgende Aufwandsordnung:

Definition Groß-O: $\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 poitive reelle Zahl $c$ gibt, sodass ab eibem gewissen $n-{0} \exists \mathbb{N}$ sämtliche Funktionswerte $t(n)$ nicht oberhalb von $c\cdot f(n)$ liegen.

Aus der Definition von Groß- $\mathcal{O}$ geht folgende Ungleichung hervor:

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 $T(0)=1$ und $T(1) = 1$ . Ergänzen wir nun die vorher ermittelte Ungleichung, ergibt sich folgendes:

Betrachtet man die erste Ungleichung, stellt man fest, dass $c^{0}=1$ . Das hat zu Folge, dass $a\ge1$ . Der Einfachheit halber wählen wir $a=1$ . Für c ergibt sich, dass $c>1$ .

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:

Damit $T(n)\le a\cdot c^{n}$ muss $\frac{c+1}{c^{2}}=1$ gelten.

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

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

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

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

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

Nebenrechnung:

Einsetzen:

Zusammengefasst:

Allgemein:

Diese rekursive Nottion kann auch in Kurzschreibweise wiedergegeben werden.

Kurznotation:

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

Indem man nun k einsetzt erhält man die expliziete Gleichung:

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:

Da nach Logarithmengesetz $x^{\log_b y}=y^{\log_b x}$ gilt kann man dies auf jeden Term anwenden, welcher einen Logarithmus mit n in der Form $a^{}log_b n$ im Exponenten besitzt. Dadurch erhält man folgende Gleichung-

Zusammenfassend erhält man schließlich:

Da $\log_4 3 < 1,\ \log_4 3\approx 1$ ist der Aufwand $T(n)$ :

Die Meistermethode

Die Mastermethode ist ein sehr einfaches Lösungsverfahren für rekurrente Gleichungen der Form $$T(n) =a\cdot T\left(\frac{n}{b}\right)+f(n).$$

Es funktioniert wie nach Kochbuch oder wie die Suche der passenden Schablone. Dabei hat man drei zur Auswahl:

Fall: $\varepsilon < 0$. Ergebnis: $T(n)=\mathcal{O}\left(n^{\log_ba}\right)$
Fall: $\varepsilon = 0$. Ergebnis: $T(n)=\mathcal{O}\left(n^{\log_ba}\log_2n\right)$
Fall: $\varepsilon > 0$ und wenn $a\cdot f\left(\frac{n}{b}\right)\leq c\cdot f(n)$ mit einer reellen Konstanten $c>0$. Ergebnis: $T(n)=\mathcal{O}(f(n))$

Der Wert von $\varepsilon$ ergibt sich zwangsläufig aus der Herstellung der folgenden Gleichheit: $$\mathcal{O}(n^{\log_b a+\varepsilon})=\mathcal{O}(f(n)).$$

Folien

Die aktuellsten Folien zur Vorlesung:

Vortrag.pdf (2.2 MB)

Aufgaben

Raten und Einsetzen
- Ermitteln Sie die explizite Bildungsvorschrift für $T(n)=3\cdot T(\frac{n}{4})+2n, T(1)=2$ .
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:
- $3\cdot T(\frac{n}{2})+ cn$ ; für n>1, sonst d.
Mastermethode
- Prüfen sie mittels Master-Theorem folgende Gleichungen:
1. $T(n)=3\cdot T(\frac{n}{2})+n^2$
2. $T(n)=\sqrt{2}\cdot T(\frac{n}{2})+\log 2$