Teile und Herrsche 2 SS09

Aus ProgrammingWiki

Archivierte Version vom 2009-03-21T19:14:10+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Zusammenfassung
2 Binäre Suche
3 die Multiplikation nach Karatsuba und Offman
4 die schnelle Matrix Multiplikation

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.

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 verlgichen 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}\} .

\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}, \\ "Nicht enthalten" &\textrm{sonst }} \end{array}% \right

Wie sieht der Algorithmus aus?

Im folgenden wird der Algorithmus (BinSuch) in Scheme und Java gezeigt. Man kann den Algorithmus in iterativer und rekursiver Form angeben.

Java - iterativ

// 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;
	}

<eval> System.out.println(searchIterative(createField(10), 3)); </eval>

Java - rekursiv Coming soon...

Komplexitätsverhalten

Best Case

Average Case

Worst Case

Vergleich mit der herkömlichen sequenziellen Suche

die Multiplikation nach Karatsuba und Offman

die schnelle Matrix Multiplikation

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