Hilfsmittel Mathematik 2 WS13-14

Aus ProgrammingWiki

Autoren:

Andre Krause s3ankrau@stud.hszg.de
Roman Stange s3rostan@stud.hszg.de

Inhaltsverzeichnis

1 O-Notation
- 1.1 weitere nützliche asymptotische Ordnungen
2 Rekursionsgleichungen
3 Übungen
- 3.1 Lösungen
4 Quellen:
- 4.1 Weblinks

O-Notation

Veranschaulichung Komplexitätsklassen

$\mathcal{O}(f)=\lbrace t \colon \mathbb{N}\to \mathbb{R}_0^+ \vert \exists c \in \mathbb{R}^+\exists n_0 \in \mathbb{N}$ $\forall n \ge n_0$ $t(n) \le c \cdot f(n)\rbrace$

Beispiel:

Wenn zwei Funktionen gegeben sind vom Bereich natürliche Zahlen in positiv reelle Zahlen: $f,g\colon \mathbb{N} \to \mathbb{R}_0^+$ , dann ist $f$ in der Komplexitätsklasse von $g$ , per Definition genau dann, wenn es ein $n_0$ und eine Konstante $c$ mit der Eigenschaft $f(n)\le c \cdot g(n)$ für alle $n \ge n_0$ .

Mit der obigen Definition wird also verlangt, dass $f(n)$ langfristig unter $g(n)$ liegt. Ab der Stelle $n_o$ dominiert $g(n)$ , da alle $n$ , die noch folgen unterhalb von $g(n)$ sind. Dabei spielt es auch keine Rolle, ob $f(n)$ mit anderen Anstiegen bestückt wird, ebenso wenig würde ein Koeffizient vor $n^2$ der quadratischen Funktion die Sachlage verändern. Man kann also sagen, dass $f(n)$ höchstens von der Komplexität $g(n)$ ist - linear wird dominiert vom quadratischen.

Einordnung der Laufzeitfunktionen
Notation	Bedeutung	Anschauliche Erklärung	Beispiele für Laufzeiten
$f \in \mathcal{O}(1)$	$f$ ist beschränkt	$f$ überschreitet einen konstanten Wert nicht (unabhängig vom Wert des Arguments).	Nachschlagen des $n$ -ten Elementes in einem Feld.
$f \in \mathcal{O}(\log n)$	$f$ wächst logarithmisch	$f$ wächst ungefähr um einen konstanten Betrag, wenn sich das Argument verdoppelt. Die Basis des Logarithmus ist dabei egal.	Binäre Suche im sortierten Feld mit $n$ Einträgen
$f \in \mathcal{O}(\sqrt{n})$	$f$ wächst wie die Wurzelfunktion	$f$ wächst ungefähr auf das Doppelte, wenn sich das Argument vervierfacht	naiver Primzahltest mittels Teilen durch jede ganze Zahl $\leq \sqrt{n}$
$f \in \mathcal{O}(n)$	$f$ wächst linear	$f$ wächst ungefähr auf das Doppelte, wenn sich das Argument verdoppelt.	Suche im unsortierten Feld mit $n$ Einträgen (Bsp.Lineare Suche)
$f \in \mathcal{O}(n \log n)$	$f$ hat super-lineares Wachstum		Fortgeschrittenere Algorithmen zum Sortieren von $n$ Zahlen Mergesort, Heapsort
$f \in \mathcal{O}(n^2)$	$f$ wächst quadratisch	$f$ wächst ungefähr auf das Vierfache, wenn sich das Argument verdoppelt	Einfache Algorithmen zum Sortieren von $n$ Zahlen Selectionsort
$f \in \mathcal{O}(2^n)$	$f$ wächst exponentiell	$f$ wächst ungefähr auf das Doppelte, wenn sich das Argument um eins erhöht	Erfüllbarkeitsproblem der Aussagenlogik (SAT) mittels exhaustivem Verfahren
$f \in \mathcal{O}(n!)$	$f$ wächst faktoriell	$f$ wächst ungefähr auf das $(n+1)$ -fache, wenn sich das Argument um eins erhöht.	TSP (mit Enumerationsansatz), alle Permutationen

weitere nützliche asymptotische Ordnungen

Mit der $\mathcal{O}$ -Notation kann man auf einfache Art ausdrücken, dass eine Funktion $f$ höchstens so schnell wächst, wie eine andere Funktion $g$ . Es gibt noch weitere Notationen, um das Wachstum von Funktionen zu vergleichen:

weitere $\mathcal{O}$ -Notationen
$f=\Omega(g)$	$f \ge g$	$f$ wächst mindest so schnell wie $g$ , falls $g =\mathcal{O}(f)$
$f=\Theta(g)$	$f = g$	$f$ und $g$ wachsen gößenordnungsmäßig gleich schnell, falls $f = \mathcal{O}(g)$ und $g = \mathcal{O}(f)$
$f= o(g)$	$f < g$	$f$ wächst langsamer als $g$ , falls die Folge $(\frac{f(n)}{g(n)})$ eine Nullfolge ist
$f=\omega(g)$	$f > g$	$f$ wächst schneller als $g$ , falls $g =o(f)$

Groß-Omega: Da die $\Omega$ -Notation eine untere Schranke (reeles Vielfaches von $f$ ) für das Wachstum einer Funktion beschreibt, wird sie oft benutzt, um eine untere Schranke aller Algorithmen zur Lösung eines Problems anzugeben und damit die Komplexität des Problems zu charakterisieren.

$\Omega(f)=\lbrace t \colon \mathbb{N}\to \mathbb{R}_0^+ \vert \exists c \in \mathbb{R}^+\exists n_0 \in \mathbb{N}$ $\forall n \ge n_0$ $c \cdot f(n) \le t(n)\rbrace$

Exakte Ordnung(Groß-Theta): Im Idealfall kann man eine asymptotische Beschränkung nach oben und unten durch ein und dieselbe Funktion mit verschiedenen Faktoren angeben. Grafisch entsteht eine Art Band, in dem die Graphen sämtlicher Funktionern aus $\Theta (f)$ verlaufen.

$\Theta(f)=\lbrace t \colon \mathbb{N}\to \mathbb{R}_0^+ \vert \exists c_1,c_2 \in \mathbb{R}^+\exists n_0 \in \mathbb{N}$ $\forall n \ge n_0$ $c_1 \cdot f(n) \le t(n) \le c_2 \cdot f(n)\rbrace$

Veranschaulichung Komplexitätsklassen

Rekursionsgleichungen

Grafische Rekursionen wie der "Droste Effekt" sind bekannt. Dabei erkennt der Betrachter Bilder oder Inhalte, die sich selbst in einer kleineren Version wieder beinhalten. Auch anderen rekursiven Funktionen, die sich also selbst aufrufen und zu denen immer eine Abbruchbedingung gehört, begegnet man oft.

Im folgenden wird die Fakultätsfunktion, als ein Beispiel für Rekursivität genommen. Die Fakultätsfunktion berechnet das Produkt aller ganzer Zahlen kleiner gleich der Zahl selbst. Die Fakultät von $4!$ liefert das Ergebnis $4\cdot3\cdot2\cdot1 = 24$ . Den Zeitaufwand $T(n)$ dafür beschreiben Rekusions-, bzw. rekurrente Gleichungen.

Rekursions- oder rekurrente Gleichungen

Die allgemeine Definition der Fakulttätsfunktion lautet wie folgt:

So könnte diese Funktion in Scheme abgebildet werden:

(define fak (lambda (n) (if(< n 1) 1 (* n (fak(- n 1))))))

(fak 4)

Die Rekursionsgleichung zur Fakultät:

$T(0)=1$
$T(n)=T(n-1)$ , mit $n \geq 1$

Auch für rekursive Gleichungen möchte man natürlich den Aufwand (Schritte, Resourcen, etc.) abschätzen können. Für kleine Schrittfolgen mag die Analyse noch überschaubar sein, doch bei Größeren ist es nicht mehr so schnell ablesbar. Es stellt sich beim Lösen also die Herausforderung dar, den Ausdruck $n$ in $T(n)$ zu finden, der nicht von irgendeinem einsetzbaren Wert $T(i)$ abhängt. Dafür gibt es mehrere Lösungsansätze, die nachfolgend beschrieben werden sollen.

allgemeine Form der Rekursionsgleichung:

$T(n) = f(T(0), T(1), ..., (T(n-1))$

Computeralgebrasysteme (CAS)

Im Laufe der Zeit entwickelten sich die Möglichkeiten der Eingabe, Verarbeitung und Ausgabe numerischer Werte von Taschenrechnern immer weiter. Mit der Einführung der Computeralgebrasysteme (CAS) wurde es möglich, auch mit Symbolen zu rechnen. Das Lösen beispielsweise von Gleichungssystemen oder Extremwertaufgaben, stellt die Besitzer dieser "Rechensklaven" nicht mehr vor große Herausforderungen. Zumeist bringen die CA-Systeme grafische Komponenten mit, die mathematische Objekte visualisieren können.

Merkmale eines modernen CAS
Symbolisches Rechnen	Grafik	Programmierung	Bibliothek	Benutzeroberfläche
Termumformungen, Lösung von Gleichungen, Funktionen, Geometrie, Stochastik	2D, 3D, Animationen, grafische Objekte	Datentypen (Variablen, Felder, Listen, Mengen), Prozeduren/Funktionen, Verzweigungen, Schleifen, Logik	Konstanten, vordefinierte Variablen, Befehle, Algorhitmen, erweiterbar mit fremden oder eigenen Anwendungen	Input-, Output-, Text- und Grafikumgebungen, Menü, Paletten (Buchstaben, Sonderzeichen, Befehle, Schablonen), Kontextmenüs und Hilfen

Um kompetente Lösungen mit einem CAS zu erhalten, ist anzueignendes Wissen des jeweiligen Systems notwendig, wie die betreffende Mathematik darauf widergespiegelt ist. Prinzipiell sind das auf CAS-Seite Implementationen, die eine möglichst enge Verbindung zu entsprechenden mathematischen Begriffen und Methoden haben, jedoch nicht identisch sind. Aus diesem Grund muss man sich mit der Evaluaierung der mathematischen Ausdrücke erst einmal vertraut machen.

Lösungsverfahren für Rekursionsgleichungen basieren auf von Spezialisten getätigten Überlegungen (sog. z-Transformationen). Auf die dafür erforderlichen mathematischen Grundlagen, wird hier nicht eingegangen. Die Hinnahme der naiven Benutzung der im CAS eingebauten Symbolmanipulation, wird durch Ergebnisverifikation (mittels vollständiger Induktion) weitestgehend behoben.

Im folgenden Beispiel wird das Protokoll einer Maxima-Sitzung zur Lösung obiger Gleichung wiedergegeben. Das entscheidende Sprachelement ist solve_rec.

load(solve_rec); > lsg1: solve_rec(T[n]=n*T(n-1), T[n], T[0] = 1); T[n]=n!

Das jeweilige CAS liefert nun das Ergebnis, was abgelesen wird und in die jeweilige Komplexitätsklasse eingeordnet werden kann: $T(n) = \mathcal{O}(n!)$

Raten und Einsetzen

Intelligent guesswork heißt geschicktes Raten. Die explizite Bildungsvorschrift für eine Zahlenfolge herauszufinden, bedarf zunächst der Bildung einer Wertetabelle für $T(n)$ . Dazu das nächste Beispiel:





wobei  eine Zweierpotenz, also ,

Wertepaare
$n$	$T(n)$
$1$	$1$
$2$	$5=3 \cdot 1 + 2$
$4$	$19 = 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^4 \cdot 1 + 3^3 \cdot 2 + 3^2 \cdot 2^2 + 3 \cdot 2^3 + 2^4$
$32$	$665 = 3^5 \cdot 1 + 3^4 \cdot 2 + 3^3 \cdot 2^2 + 3^2 \cdot 2^3 + 3 \cdot 2^4 + 2^5$

Ein Blick auf die Ergebnisse in der Tabellenspalte für $T(n)$ deuten auf exponentielles Wachstum hin. Die Summenausführung hilft nun beim Erraten der Lösung:

$T(2^k) = 3^k \cdot 2^0 + 3^{k-1} \cdot 2 + \ldots + 3^0 \cdot 2^k$
$T(2^k) = \sum_{i=0}^{k}3^{k-i}2^i$

$T(2^k) = 3^k\sum_{i=0}^{k} \left( \dfrac{2}{3} \right)^i$

$T(2^k) = \frac{3^k\left( 1-\left(\frac{2}{3} \right)^{k+1}\right)}{1-\frac{2}{3}}$

$T(2^k) = 3^{k+1}-2^{k+1}$

Um eine Funktion $T\colonn \mapsto T(n)$ abzubilden, ist es notwendig mit $k=\log_2 n$ zu substituieren. Da man sich für die asymptotische Ordnung interessiert, ist dies für alle natürlichen $n$ auch berechtigt. Das Ergebnis ist ables- und damit klassifizierbar:

$T(n) = 3n^{\log_2 3}-2n = \mathcal{O} \left(n^{\log_2 3 \right)$

Iterationsmethode

Iteration wird in der Mathematik angewendet, um sich einer exakten Lösung eines Rechenproblems schrittweise anzunähern. Dies geschieht durch die konsequente Wiederholung des Rechenverfahrens, bis die Lösung gefunden wurde bzw. sich bestmöglichst angenähert hat. Ein Beispiel ist die Approximation an eine Nullstelle einer stetigen Funktion. Auch auf Rekursionsgleichungen kann diese Methode angewendet werden, in dem die rekursive Vorschrift solange iteriert wird, bis ein rekursionsfreier Ausdruck in $n$ gegeben ist, auch Telescoping genannt. Der Vorgang ist beendet, sobald das Argument der Anfangsbedingung erreicht ist. Dies ist in der Regel 1 oder 0.

Auf folgende Rekursionsgleichung wird diese Methode nun angewendet.


, für

Die schrittweise Iteration sieht wie folgt aus:

$T(n) = n + 3 \cdot T\left(\frac{n}{4}\right)$

$= n + 3 \cdot \left(\frac{n}{4} + 3 \cdot T\left(\frac{n}{16}\right)\right)$

$= n + 3 \cdot \left(\frac{n}{4} + 3 \cdot \left(\frac{n}{16} + 3 \cdot T\left(\frac{n}{64}\right)\right)\right)$

$= n + \frac{3}{4}n + \frac{9}{16}n + \frac{27}{64}n + ... + \frac{3^{i-1}}{4^{i-1}}n + 3^i \cdot T\left(\frac{n}{4^i}\right)$

Der Rekursionsgleichung kann entnommen werden, dass die Rekursionsfreiheit nur für $n = 1$ gilt. Dies bedeutet, dass die Rekursion auch auf $T(1)$ enden muss.

$T\left(\frac{n}{4^i}\right) = T(1)$

$= \frac{n}{4^i} = 1$

Diese Gleichung kann nun nach $i$ umgestellt werden.

$i = \log_4 n$

Die weiter oben aufgeführte Iterationsformel kann auch als Summe dargestellt werden.

$T(n) = n\sum_{k=0}^{i-1}\left(\frac{3}{4}\right)^k + 3^i$

$= -4n\cdot\left(\left(\frac{3}{4}\right)^i - 1\right) + 3^i$

$= 4n - 4n\cdot\left(\frac{3}{4}\right)^i + 3^i$

Nun wird für $i$ der Term $\log_4 n$ eingesetzt.

$= 4n - 4n\cdot\left(\frac{3}{4}\right)^{\log_4 n} + 3^{\log_4 n}$

Aufgrund der Rechenregel $a^{\log_4 n} = n^{\log_4 a}$ , ergibt sich folgende Gleichung.

$= 4n - 4n\cdot n^{\log_4 \left(\frac{3}{4}\right)} + n^{\log_4 3}$

$= 4n - 4n\cdot n^{\log_4 3 - \log_4 4} + n^{\log_4 3}$

$= 4n - 4n\cdot n^{\log_4 3 - 1} + n^{\log_4 3}$

$= 4n - 4n\cdot \left(\frac{n^{\log_4 3}}{n}\right) + n^{\log_4 3}$

$= 4n - 3n^{\log_4 3}$

Durch die Annahme, dass $log_4 3 < 1, log_ 4 3 \approx 1$ ist, kann man folgende Aufwandsfunktion ablesen:

Es handelt sich also bei dieser Rekursionsgleichung um einen linear wachsenden Aufwand.

Die Meistermethode

Mit der master method erhält man ein weiteres Werkzeug, die Laufzeitklasse einer rekurrenten Gleichung zu bestimmen. Die allgemeine Form für die Anwendung des Master-Theorems sieht wie folgt aus:

$T(n) = a \cdot T(\textstyle \frac{n}{b}) + f(n)$

$f,T \colon \mathbb{N}\to \mathbb{R}$

Hierbei steht $T(n)$ , wie immer für die zu untersuchende Laufzeitfunktion, während $a$ und $b$ reelle Konstanten, mit der Bedingung das $a \ge 1$ und $b > 1$ sind. Weiterhin benötigt man für die Benutzung noch den Logarithmus von $a$ zur Basis $b$ , $\log_b a$ . Warum? Weil man noch drei Muster als Zutaten dazu bekommt, welche die Funktion $f$ mit $n \to n^{log_b a}$ vergleichen. Die Wertbindungen für $a, b$ erfolgen dabei durch einen Musterabgleich (Matching).

Mit anderen Worten heißt es nach Auslegung der so genannten Kochbuchmethode: „Eine schmackhafte Suppe ist es dann, wenn mindestens eine der Zutaten geschmacklich dazu passt. Ist dem nicht der Fall gießen Sie das ganze, unter kräftigen Rühren in den Ausguss.“

Muster der Meistermethode
Muster 1	Muster 2	Muster 3
Wenn $f(n) \in \mathcal{O}\left( n^{\log_b a - \varepsilon} \right)$ für eine beliebige reelle Konstante $\varepsilon>0$ , dann gilt: $T(n) \in \Theta\left( n^{\log_b a} \right)$	Wenn $f(n) \in \Theta\left( n^{\log_b a} \right)$ , dann gilt: $T(n) \in \Theta\left( n^{\log_b a} \log_2 n\right)$	Wenn $f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right)$ für eine beliebige reelle $\varepsilon>0$ und wenn $a \cdot f( \textstyle \frac{n}{b} ) \le c \cdot f(n)$ , ,mit einer reellen Konstanten $0 < c < 1$ dann gilt: $T(n) \in \Theta(f(n))$

Zeit für ein Beispiel:

Die Informationen, die aus der Formel gewonnen werden, lauten:
$a = 8, b = 2 ,f(n) = 1000n^2$ und $\log_b a = \log_2 8 = 3$

Muster 1 passt: $f(n) \in \mathcal{O}\left( n^{\log_b a - \varepsilon} \right)$ für ein $\varepsilon > 0$
Eingesetzt ergibt das: $1000n^2 \in \mathcal{O}\left( n^{3 - \varepsilon} \right)$
Wähle $\varepsilon > 0: 1000n^2 \in \mathcal{O}\left( n^{2}\right)$ mit $\varepsilon = 1$

Das Ergebnis ist die Laufzeitfunktion: $T(n) \in \Theta( n^{3} )$

Übungen

1. CAS
Bestimmen Sie für folgende Rekursionsgleichung die asymptotische Ordnung $\mathcal{O}$ mit Hilfe von Maxima:



, mit

Orientieren Sie sich dazu am Beispiel 3.2 (s.S. 47) aus dem Buch Algorithmen und Kompläxitäten beziehungsweise am Beispiel aus dem Abschnitt CAS.

Hinweis:

Befehlsübersicht
Maple	Maxima
rsolve(%)	solve_rec(%)
simplify(%)	trigsimp(%)
evalf(%)	ev(%, numer)

2. Meister Methode
Berechnen Sie für folgende Aufwandsfunktion, mithilfe des dritten Musters der Meistermethode, ob gilt: $T(n) \in \Theta(f(n))$

3. Raten und Einsetzen
Rechnen Sie nach und formen Sie um. Werfen Sie untertützend dazu einen Blick auf obiges Thema Raten und Einsetzen.

Lösungen

1. CAS

Lösung anzeigen

2. Meistermethode

Lösung anzeigen

3. Raten und Einsetzen

Lösung anzeigen

Quellen:

Christian Wagenknecht: Algorithmen und Komplexität, Fachbuchverlag Leipzig im Carl Hanser Verlag, München Wien 2003, S. 34-54 ISBN 3446223142
Ralf Hartmut Gütting: Datenstrukturen und Algorithmen, B.G. Teuber, Stuttgart 1992, S. 11-17 ISBN 3446223142

Hilfsmittel Mathematik 2 WS13-14

Aus ProgrammingWiki

Inhaltsverzeichnis

O-Notation

weitere nützliche asymptotische Ordnungen

Rekursionsgleichungen

Rekursions- oder rekurrente Gleichungen

Computeralgebrasysteme (CAS)

Raten und Einsetzen

Iterationsmethode

Die Meistermethode

Übungen

Lösungen

Quellen:

Weblinks

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge

$n$	$T(n)=3\cdot n^{\log_2 3}-2 \cdot n = 3 \cdot 3^{\log_2 n}-2n$
$1$	$3 \cdot 3^{\log_2 1} -2 \cdot 1 = 3\cdot 1 -2 = 1$
$2$	$3 \cdot 3^{\log_2 2} -2 \cdot 2 = 3\cdot 3 -4 = 9 \cdot 4 = 5$
$4$	$3 \cdot 3^{\log_2 4} -2 \cdot 4 = 27 - 8 = 19$
$8$	$3 \cdot 3^{\log_2 8} -2 \cdot 8 =81 -1 6 = 65$
$16$	$3 \cdot 3^{\log_2 16} -2 \cdot 16 = 3^5-32=243-32 = 211$
$32$	$3 \cdot 3^{\log_2 32} -2 \cdot 32 =3^6-64 = 729 - 64 = 665$