AuK/Teile und Herrsche 2 SS09

Wiki-Quelltext dieser Seite.

<language>Java</language>
Diese Seite stellt eine inhaltliche Fortsetzung des Themas [[Teile und Herrsche 1]] dar.

== Zusammenfassung == 

<!--TODO: Um was geht es auf dieser Seite? Welche Fragen werden gestellt, beantwortet und was wird genauer erklärt? -->
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 ==

<!-- Die Informationsfindung in einer beliebig großen Menge von ähnlichen Informationen, ist ein essentielles Problem in der Informatik. Das populärste Beispiel sind Datenbanken, diese halten riesige Datenmengen zur Abfrage einiger weniger Informationen bereit. Wir wollen dieses Problem jedoch an einem wesentlich trivialeren Problem beschreiben.  -->

=== Wie funktionierts? ===

Jeder war bestimmt schon einmal in einer Situation, in der man aus einer großen Menge von Informationen eine Bestimmte wiederfinden 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.

<!-- Als einfaches Beispiel könnte ein sehr großes Bücherregal dienen. Nehmen wir weiterhin an, irgendjemand hat die Bücher anhand ihrer Titel alphabetisch geordnet. Nun hat man folgende Möglichkeiten, jedes Buch vom ersten Beginnend zu betrachten oder in der Mitte (natürlich setzen wir voraus das man die Mitte durch einen kurz Blick genau lokalisiert) zu beginnen und zu prüfen ob unser gesuchter Titel "''kleiner oder größer''" als der Titel des Buches in der Mitte.
-->
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:
<math>$$L= \{ e_{1}, e_{2}, ... , e_{n} \}$$</math>

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 <math>k = \frac{n}{2}</math>. 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 <math>k = \lfloor\frac{n}{2}\rfloor</math> somit nehmen wir bei der Division den ganzzahligen Wert, nach unten gerundet.

Nun haben wir eine linke Teilliste <math>L_{l}=\{a_{1}, a_{2}, ... a_{k}\}</math> und eine rechte Teilliste <math>L_{r}=\{a_{k+1}, a_{k+2}, ... a_{n}\}</math> oder anders dargestellt:

<math>L = \underbrace{a_{1}, a_{2}, ... a_{k}}_{L_{\text{l}}}, \underbrace{a_{k+1}, a_{k+2}, ... a_{n}}_{L_{\text{r}}}</math>


Jetzt wird unser Zielwert x mit dem ersten Element der rechten Liste <math>x < a_{k+1} </math> verglichen, abhängig vom Ergebnis wird mit <math>L_{r}</math> oder <math>L_{l}</math> weiter gearbeitet bzw. das Element ausgegeben. Natürlich kann bereits zu Begin der Elementarfall eintreten das <math>a_{k} = x</math> ist. 

Fassen wir es noch einmal zusammen: 

<math>  
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}%
\right
</math>

----

=== Wie 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''====
<code>	
// Eine Hilfe um mal schnell ein Array beliebiger Länge, zu füllen
int[] createField(int length) {
	int[] field = new int[length];
	for (int i = 0; i < field.length; i++) {
		field[i] = i;
	}
	return field;
}


// Die eigentliche Such Methode, diese Liefert aber lediglich eine Antwort 
//auf die Frage ob ein Element enthalten ist.
boolean searchIterative(int[] field, int x) {
		int start = 0;
		int end = field.length;

		while (start <= end) {
			int middle = (start + end) / 2;
			if (x < middle) {
				end = middle - 1;
			} else if (x > middle) {
				start = middle + 1;
			} else
				return true;
		}
		return false;
	}
</code>

<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 <math>\mathcal{O}(c)</math> 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 <math>\mathcal{O}(c)</math>, 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 ====

<!-- Eventuell zu kompliziert
Um den Aufwand für den mittleren sowie schlechtesten Fall zu ermitteln, betrachten wir folgenden Sahverhalt. 
Ein implizites Resultat der Binären Suche ist ein ''binärer Suchbaum''. Jedesmal wenn ein Vergleich fehlschlägt, entstehen zwei neue Knoten, von dem einer, entsprechend dem Ergebnis des Vergleichs, für einen erneuten Aufruf der Prozedur gewählt wird. 
 TODO -->


<!-- Falsch
<math>T(n)=T\bigg(\frac{n}{2}\bigg)+\mathcal{O}(c)</math>
-->

Ü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. 

=== Wie funktionierts? ===
Wir nehmen 2 Zahlen ''a'' und ''b'', wir vereinbaren das deren Stelligkeit ''n'' gleich und gerade ist. Dann zerlegen wir diese beiden Zahlen in jeweils 2 gleiche Teile. Im einfachsten Fall <math>n = 1</math> haben entsprechend nur eine Operation nämlich <math>a \cdot b</math>. Betrachten wir <math>n = 2</math>, als Beispiel dienten uns die Zahlen 14 und 73. Die beiden Faktoren werden wie folgt zerlegt,

<math>
x = x_{1} \cdot B + x_{0}
</math>

Wobei ''B'' für die Basis der Zahlendarstellung steht. In unserm Fall 10.

<math>
a = 14 =1 \cdot 10 + 4
</math>

<math>
b = 73 = 7 \cdot 10 + 3
</math>

Im nächsten Schritt schau wir uns an wie die Multiplikation von a und b mit Hilfe der Ziffern aussieht.

<math>
\begin{array}{ccl}
a \cdot b & = & (a_{1} \cdot 10 + a_{0}) \cdot (b_{1} \cdot 10 + b_{0}) \\
& = & (a_{1} \cdot b_{1}) \cdot 100 + (a_{1} \cdot b_{0} + a_{0} \cdot b_{1}) \cdot 10 + a_{0} \cdot b_{0}\\
& = & (1 \cdot 7) \cdot 100 + (1 \cdot 3 + 4 \cdot 7) \cdot 10 + 4 \cdot 3 \\
& = & 1022
\end{array}
</math>

Ruft man sich das Verfahren ins Gedächtnis, welches wir einmal in der Schule gelernt haben, stellen wir schnell fest das uns unser neuer Algorithmus kein besseres Verfahren liefert.
<!-- 
Denn bereits eine Veränderte Darstellung zeigt uns das es sich hierbei fast um die Schulbuchmethode handelt!
<math>
\begin{array}{ll}
  & 1 \cdot 7 \cdot 100\\
+ & 1 \cdot 3 \\
+ & 4 \cdot 7 \\
+ & 4 \cdot 3
\end{array}
</math>
-->
Wir haben nach wie vor lediglich 4 Multiplikationen und die Addition der Ergebnisse. Die Trick den Karatsuba entdeckt hat sieht wie folgt aus, er nutzt lediglich 3 Multiplikationen um folgende Werte zu berechnen,

<math>
\begin{array}{ccl}
m & = &  a_{1} \cdot b_{1}\\
n & = & (a_{0} - a_{1}) \cdot (b_{0} - b_{1}) \\
o & = & a_{0} \cdot b_{0}
\end{array}
</math>

<!-- TODO -->

<!--
<math>
x = x_{1}b^{\frac{n}{2}}+x_{0}
</math>

<math>
y = y_{1}b^{\frac{n}{2}}+y_{0}
</math>

Gesucht ist nach wie vor, das Produkt aus ''x'' und ''y''.

<math>
y \cdot x = ?
</math>

Dazu multipliziert man zunächst die Teile <math>x_{1}</math> und <math>y_{1}</math> mit der Basis <math>b^{n}</math>. Die erste von 4 Teiloperationen.

<math>
y \cdot x = (x_{1} \cdot y_{1})b^{n} \dots
</math>
-->
<!-- TODO -->

=== 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...

<!-- oder sollen wir die hier mit aufnehmen? -->

Aufwand für die Schulbuchmultiplikation = <math>4n^2 - 2n = \mathcal{O}(n^2)</math>

<!-- Aufwand für Multiplikation 'a la Russe = <math>4n^2 - 2n = \mathcal(O)(n^2)</math> -->

<!-- TODO: Gnuplot Schulbuch Multiplikation + Russe-->

=== Wie kann man Karatsubas Idee Programmieren? ===

== die schnelle Matrix Multiplikation ==

Auch '''''Strassens''' Algorithmus zur Matrixmultiplikation'' genannt, bietet eine Alternative zur herkömlichen Matrixmultiplikation.



<!-- Beispiel Matrix
<math>
\left(
   \begin{array}{ccc}
     a_{11} & \cdots & a_{1n} \\
     \vdots & \ddots & \vdots \\
     a_{m1} & \cdots & a_{mn}
   \end{array}
\right)
</math>
-->


=== praktische Probleme ===
<!--
Die besprochene Methode weist leider schwächen auf,

*Das rekursive erstellen der Teilmatrizen benötigt unverhältnismässig viel Speicherplatz
-->