Teile und Herrsche 2 SS10
Inhaltsverzeichnis |
Diese Seite setzt das in AuK/Teile und Herrsche 1 SS10 begonnene Thema inhaltlich fort.
Autor:
Felix Deutschmann (sifedeut@stud.hs-zigr.de)
Einführung
Diese Seite beschäftigt sich mit den Algorithmen Binäre Suche, Multiplikation großer, ganzer Zahlen nach KARATSUBA und OFMAN, sowie Schnelle Matrixmultiplikation, welche hier vorgestellt und demonstriert werden.
Weiterhin findet man hier auch die Vorlesungsunterlagen, sowie die Übungsaufgaben zu diesem Thema.
Binäre Suche
Wer schon einmal etwas gesucht hat, sei es ein Schlüssel an einem Schlüsselbund oder einen Namen im guten alten Telefonbuch oder auch nur eine Seite in einem dicken Buch, der hat sich dabei vielleicht schon eine wichtige Frage gestellt: "Wie finde ich das jetzt am besten?".
Beim Schlüsselbund sieht man sich jeden einzelnen Schlüssel an und prüft, ob es der Schlüssel ist, den man gesucht hat. Man kann diese Vorgehensweise mit dem Suchen in einer unsortierten Liste vergleichen. Bei dieser Art zu suchen prüft man, ob das zu suchende Element x in der Liste L vorkommt - Elementweise. Im ungünstigsten Fall findet man das Element an der letzten Stelle der Liste L. Diese Suche mit \mathcal{O}(n) hat einen linearen Aufwand und ist für lange Liste nicht zu empfehlen. Eine Implementierung dieser Suche in Scheme ist folgende:
<eval id="4bc088875144e">(usortSeqSuch 5 '(99 43 65 44 29 83 10 4 5 8 6))</eval>
Dieser Suchalgorithmus hat zwei große sofort erkennbare Schwächen.
- der Aufwand steigt linear mit wachsender Elementeanzahl
- die Liste wird komplett durchsucht, wenn das Element fehlt
Das zweite Problem können wir mit einem kleinen Trick sofort beheben. Wir nehmen eine aufsteigend sortierte Liste und durchsuchen diese mit dem folgenden leicht modifizierten Algorithmus. Damit können wir dann in einigen Fällen die Suche vorzeitig abbrechen, wenn das Element nicht in der Liste ist.
<eval id="4bc08d9b95e51">(sortSeqSuch 38 '(1 4 7 9 12 17 24 29 31 33 38 41 53 74 86 93 104 137 143 163))</eval>Da aber auch hier der Aufwand linear bleibt, erfüllt die sequentielle Suche nicht unseren Wunsch nach einem geringeren Aufwand.Wenden wir uns also der Suche nach einem Namen im Telefonbuch zu. Wie würde man dabei vorgehen? Bei den meisten Menschen kann man folgendes erkennen:
Zuerst wird das Buch in der Mitte aufgeschlagen. Dann prüfen sie, ob der Anfangsbuchstabe vom gesuchten Namen mit dem aktuellen Index im Telefonbuch übereinstimmt. Wenn das so ist, dann ist die Suche vermutlich noch auf der selben Seite vorbei. Haben sie den Anfangsbuchstaben noch nicht gefunden, so überlegen sie, ob der gesuchte Anfangsbuchstabe vor oder nach dem aktuellen Index auftritt. Daraufhin wird entweder vor oder nach der Mitte des Buches weitergesucht. Aber nicht irgendwie, sondern wieder mit dem selben Verfahren. Auf diese Weise wird der Suchraum kontinuierlich halbiert und man kommt mit dieser Methode deutlich schneller zum Ziel als mit der sequentiellen Suche.
Jetzt wo der Name dieser Suche geklärt ist, befassen wir uns ein wenig näher mit der binären Suche. Dafür reduzieren wir das Suchproblem auf eine Liste mit n Elementen aus dem Zahlenbereich der ganzen Zahlen \mathbb{Z}:
$$L=\{e_{1}, e_{2}, \cdots ,e_{n}\}$$ mit e\in\mathbb{Z} und n\in\mathbb{N}
Unsere Liste L muss nun möglichst in der Mitte geteilt werden. Da das aber bei einer ungeraden Anzahl von Elementen ganzzahlig nicht möglich ist, teilen wir die Anzahl der Listenelemente durch 2 und runden das Ergebnis abschließend auf die nächst kleinere Zahl ab. Mathematisch schreibt man: k=\lfloor\frac{n}{2}\rfloor (k ist der Index des Elementes in der Mitte der Liste L)
Nach der Teilung haben wir nun zwei Teillisten, eine linke und eine rechte:
$$L_{l}=\{e_{1}, e_{2},\cdots, e_{k}\}$$ und
$$L_{r}=\{e_{k+1}, e_{k+2},\cdots, e_{n}\}$$
Wenn nun x unser gesuchtes Element ist, dann wird x mit dem ersten Element der rechten Teilliste verglichen x < e_{k+1}. Abhängig vom Ergebnis dieser Prüfung wird nun mit der rechten oder linken Teillisten fortgefahren. Die verwendete Teilliste wird dann wieder in zwei Teillisten aufgeteilt und die Prüfung beginnt von vorn. Dieser Vorgang wird solange wiederholt, bis entweder x gefunden wurde oder bis alle Teillisten untersucht worden sind. Im besten Fall ist das erste Element e_{k+1} unserer Teilliste L_{r} schon das gesuchte x.
Zur übersichtlichen Darstellung der binären Suche zeigen wir hier die rekursive Bildungsvorschrift:
BiSu = \{ \begin{array}{ll} BiSu(L_{\text{l}}) &\textrm{wenn }x<e_{k+1},\\ BiSu(L_{\text{r}}) &\textrm{wenn }x>e_{k},\\ print(e_{k}) &\textrm{wenn } x = e_{k}, \\ \textrm{"nicht Enthalten"} &\textrm{wenn } k < 0 \textrm{ oder } k > n\\ \textrm{"nicht Enthalten"} &\textrm{sonst } \end{array}
Mit der binären Suche ist es möglich, in einem Telefonbuch mit 250.000 Einträgen und 700 Seiten
mit höchstens 18 \sim \log_2 250000 Namensvergleichen jeden Namen zu finden.Implementierung in Scheme
Aufgrund der oben stehenden interessanten Information schauen wir uns jetzt einmal den Algorithmus in seiner Scheme-Implementierung an.
Bevor wir aber zum eigentlichen Algorithmus kommen, benötigen wir noch die Prozedur teillisten2, welche im Kapitel Teile und Herrsche 1 SS01 im Zusammenhang mit Mergesort behandelt wurde.
Scheme-Implementierung der binären Suche:
Um zu sehen, dass der Algorithmus arbeitet, haben wir zur Vereinfachung eine Liste explizit angegeben. Bei der späteren selbständigen Arbeit mit der binären Suchen können auch die Prozeduren zzls (Erstellt eine Liste mit Zufallszahlen) und mergesort (sortiert eine Liste) verwendet werden. Beide Prozeduren werden für die Übungen bekannt gegeben.
Wir suchen nach dem Element 42:
<eval id="4bc0b3fa50938">(binaersuche 42 suchliste)</eval>
Nachdem wir die binäre Suche nun ausprobieren konnten, stellen wir fest, dass das Ergebnis etwas dürftig ist. Denn die Aussage, dass etwas gefunden wurde ist nicht sinnvoll, wenn man nicht auch noch gesagt bekommt, an welcher Stelle das Element gefunden wurde. Aus diesem Grund fügen wir diese Funktion noch in unsere Prozedur ein. Weiterhin wird noch ein Aufrufzähler eingebaut, welcher die Rekursionsschritte zählt. Diesen können wir dann für die empirische Aufwandsanalyse benutzen.
Zuerst definieren wir einen Zähler und einen Index:
Dann implementieren wir die eben definierten Variablen in der Binären Suche
Und abschließend benötigen wir noch eine Prozedur zum Aufruf der binären Suche:
Ein Aufruf unserer neuen binären Suche ergibt dann das gewünschte Ergebnis.
<eval id="4bc0c4f550f55">;so haben wir die suchliste definiert:</eval>
- verändern könnt ihr sie mit set!
- (define suchliste '(4 8 15 16 23 42 55 63 78 84 92 103))
(binaersuche2 42 suchliste)
Vergleich Sequentielle Suche - Binäre Suche
Da wir nun im vorangegangenen Teilabschnitt die Grundlage für eine empirische Analyse der binären Suche geschaffen haben, möchten wir das an dieser Stelle auch für die sequentielle Suche tun. Somit ist es dann in der Übung möglich die Aufwände der beiden Suchen zu vergleichen.
Dafür müssen wir lediglich die Variable für die Aufrufe implementieren, da diese dann auch für den Index verwendet werden kann:
Weiterhin schaffen wir uns noch eine Prozedur, welche die Variable "calls" zurücksetzt:
Somit können wir mit den folgenden Aufruf machen: <eval>(sortSeqSuch2 42 suchliste)</eval>