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 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 man beginnt in der Mitte (natürlich setzen wir voraus das man die Mitte durch einen kurz Blick genau lokalisiert) und schaut ob unser gesuchter Titel kleiner oder größer ist als die Mitte. 

 Wir erinnern uns an die "längen lexikographische Ordnung"!

Der Trick besteht also darin, den Suchraum stes zu halbieren, und festzustellen in welcher Hälfte unsere gesuchte Information zu finden ist.

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

=== Komplexitätsverhalten ===


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

== die schnelle Matrix Multiplikation ==