AuK/Teile und Herrsche 2 SS09

Wiki-Quelltext dieser Seite.

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? -->

== 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 wieder finden musste. 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 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. Da der zusätzliche Aufwand für das bestimmen der längenlexikographischen Ordnung wie oben erwähnt die Analyse nur unnötig erschwert. 

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

<math>\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 <math>a_{k+1}</math> der rechten Liste <math>x < a_{k+1} </math> verglichen, jenach Ergebniss wird mit <math>L_{r}</math> oder <math>L_{l}</math> weiter gearbeitet. Natürlich kann bereits zu Begin der Elementarfall eintreten das <math>a_{k} = x</math> ist. 

Fassen wir das 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},\\
a_{k} = x &\textrm{sonst}}
\end{array}%
\right
</math>

=== Wie sieht der Algorithmus aus? ===

=== Komplexitätsverhalten ===


== ...und noch ein multiplikations Algortihmus ==

== die schnelle Matrix Multiplikation ==