Teile und Herrsche 2 SS09
Inhaltsverzeichnis |
Diese Seite stellt eine inhaltliche Fortsetzung des Themas Teile und Herrsche 1 dar.
Zusammenfassung
Auf dieser Seite soll versucht werden, die Algorithmen Binäre Suche, Strassens-Matrix-Multiplikation und den Multiplikations Algorithmus von Karatsuba in Hinblick auf die Arbeitsweisen und den Aufwand (Effiziensanalyse) der einzelnen Verfahren vorzustellen. Dabei findet ihr verschiedene Implementierungen der Algorithmen in Java und Scheme.
Die Übungsaufgaben zu diesen Themen findet ihr hier Aufgaben - TuH2. Ihr findet aber auch im Text Hinweise und Hilfestellungen zu etwaigen Problemen auf die man während der Bearbeitung stoßen könnte.
Binäre Suche
Wie funktionierts?
Jeder war bestimmt schon einmal in einer Situation, in der man aus einer großen Menge von Informationen eine Bestimmte wieder finden musste. Als Beispiel dient das suchen einer Seite anhand Ihrer Seitenzahl in dicken Büchern. Man schaut in das Inhaltsverzeichnis und erhält die Seitenzahl der gesuchten Information. Nun schlägt man das Buch in der Mitte auf und schaut ob die Seiteanzahl der Seite auf der wir uns nun befinden größer oder kleiner ist, als die Seitenzahl unserer gesuchten Seite. Abhängig vom Ergebnis nehmen wir die vordere oder hintere Hälfte des Buches und schlagen von dieser die Hälfte auf und vergleichen wieder... das wiederholen wir solange bis unsere gesuchte Seite auftaucht.
Der Trick besteht also darin, den Suchraum stets zu halbieren und festzustellen in welcher Hälfte unsere gesuchte Information wohl zu finden ist, diese Hälfte wird dann wieder halbiert und es wird wieder verglichen und so weiter... . Um nun auf einen konkreten Algorithmus und dessen Effizienzanalyse hinzuarbeiten, reduzieren wir das Problem auf eine aufsteigend sortierte Liste mit Integerzahlen.
Also nun zu unserer Liste:
$$L= \{ e_{1}, e_{2}, ... , e_{n} \}$$Wie erwähnt, muss die Liste bereits zu begin geteilt werden, dies geschieht beim Element mit dem Index k, die Mitte der Liste ist also k = \frac{n}{2}. Wobei man ja davon ausgehen kann, das die Liste nicht zwangsläufig ungerad zahlig viele Elemente besitzt, sodass man ein Element in der Mitte ausmachen kann. Also müssen wir unser k folgendermassen korrigieren k = \lfloor\frac{n}{2}\rfloor somit nehmen wir bei der Division den ganzzahligen Wert, nach unten gerundet.
Nun haben wir eine linke Teilliste L_{l}=\{a_{1}, a_{2}, ... a_{k}\} und eine rechte Teilliste L_{r}=\{a_{k+1}, a_{k+2}, ... a_{n}\} oder anders dargestellt:
L = \underbrace{a_{1}, a_{2}, ... a_{k}}_{L_{\text{l}}}, \underbrace{a_{k+1}, a_{k+2}, ... a_{n}}_{L_{\text{r}}}Jetzt wird unser Zielwert x mit dem ersten Element der rechten Liste x < a_{k+1} verglichen, abhängig vom Ergebnis wird mit L_{r} oder L_{l} weiter gearbeitet bzw. das Element ausgegeben. Natürlich kann bereits zu Begin der Elementarfall eintreten das a_{k} = x ist.
Fassen wir es noch einmal zusammen:
BinSuch = \left\{% \begin{array}{ll} BinSuch(L_{\text{l}}) &\textrm{wenn }x<a_{k},\\ BinSuch(L_{\text{r}}) &\textrm{wenn }x>a_{k},\\ print(a_{k}) &\textrm{wenn } x = a_{k}, \\ \textrm{"nicht Enthalten"} &\textrm{sonst }} \end{array}% \rightWie sieht der Algorithmus aus?
Im folgenden wird der Algorithmus, im Code als BinSuch betitelt, in Scheme und Java gezeigt. Man kann den Algorithmus in iterativer und rekursiver Form angeben.
Java - iterativ
<eval> System.out.println("Ist das Element enthalten? " + searchIterative(createField(10), 3)); </eval>
Java - rekursiv
Coming soon...
Komplexitätsverhalten
Best Case
Es liegt nahe das es sich im besten Fall um einen konstanten Aufwand \mathcal{O}(c) handelt.
Warum? Bereits vor dem ersten rekursiven Aufruf mit der jeweiligen Teilliste wird ein Vergleich, des Elements in der Mitte der Liste, mit unserem gesuchten Element durchgeführt. Dieser Vergleich besitzt konstanten Aufwand \mathcal{O}(c), nimmt man nun an, dass die Elemente übereinstimmen ist der Algorithmus beendet ohne das noch weitere Operationen ausgeführt werden müssen. Somit ist der Aufwand des Algorithmus gleich dem der Vergleichsoperation.
Average Case & Worst Case
Überlegen wir nun wieviel Einträge wir mit einer Ausführung unserem Algorithmus untersuchen können.
Vergleich mit der herkömlichen sequenziellen Suche
Betrachten wir nun noch die einfachste Art des Suchens. Man nimmt eine Liste L mit der Länge n, ein gesuchtes Element x und beginnt dieses mit jedem Element der Liste zu vergleichen. Dieses Verfahren besitzt linearen Aufwand. Wobei davon auszugehen ist, das die Wahrscheinlichkeit, das x mit dem Element a aus L übereinstimmt für jedes Element gleich ist.
die Multiplikation nach Karatsuba und Offman
Wir kennen die Multiplikation aus der Schule und haben die sog. Russische Bauernmultiplikation (Multiplikation à la Russe) kennengelernt. Infolge dessen, wollen wir hier noch ein anderes Multiplikationsverfahren analysieren.
Zusätzliche Betrachtung
Nehmen wir uns die Aufwände der eben genannten Multiplikationsverfahren noch einmal zu Brust um zu sehen wie diese sich verhalten. Auf die Herleitung der beiden Verfahren wird an dieser Stelle verzichtet...
Aufwand für die Schulbuchmultiplikation = 4n^2 - 2n = \mathcal{O}(n^2)
Wie funktionierts?
Wir nehmen 2 Zahlen x und y, wir vereinbaren das deren Stelligkeit n gleich und gerade ist. Dann zerlegen wir diese beiden Zahlen in jeweils 2 gleiche Teile. Zusätzlich ist die Basis Zahlendarstellung b zu betrachten. Zusammengefasst sieht das folgender Massen aus.
x = x_{1}b^{\frac{n}{2}}+x_{0} y = y_{1}b^{\frac{n}{2}}+y_{0}Gesucht ist nach wie vor, das Produkt aus x und y.
y \cdot x = ?Dazu multipliziert man zunächst die Teile x_{1} und y_{1} mit der Basis b^{n}. Die erste von 4 Teiloperationen.
y \cdot x = (x_{1} \cdot y_{1})b^{n} \dotsWie kann man das Programmieren?
die schnelle Matrix Multiplikation
Auch Strassens Algorithmus zur Matrixmultiplikation genannt, bietet eine Alternative zur herkömlichen Matrixmultiplikation.