Hilfsmittel Mathematik 2 WS13-14
Inhaltsverzeichnis |
Autoren:
Andre Krause s3ankrau@stud.hszg.de Roman Stange s3rostan@stud.hszg.de
O-Notation
\mathcal{O}(f)=\lbrace t \colon \mathbb{N}\to \mathbb{R}^+ \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}^+, 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 kommen 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 |
Rekursionsgleichungen
Eine Rekursionsgleichung ist eine Gleichung oder eine Ungleichung, die eine Funktion durch ihre eigenen Funktionswerte für kleinere Eingaben beschreibt.
Grafische Rekursionen wie den "Droste Effekt" sind bekannt. Dabei erkennt der Betrachter Bilder oder Inhalte, die sich selbst in einer kleineren Version wieder beinhalten. Auch rekursive 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:
n! = \left\{
\begin{array}{l l}
1 & \quad \text{$n = 0$}\\
n \cdot (n - 1)! & \quad \text{$n \geq 1$}
\end{array} \right.
So könnte diese Funktion in Scheme abgebildet werden:
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 irgendeinen einsetzbaren Wert T(i) abhängt, wofür es mehrere Lösungsansätze gibt, 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.
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 diese Zahlenfolge herauszufinden, bedarf der Bildung einer Wertetabelle für T(n). Dazu das nächste Beispiel:
T(1)=1 T(n)=3 \cdot T(\frac n 2)+n
Iterationsmethode
Text
Die Meistermethode
Text
Übungsaufgaben
Text
Lösungen
Text