AuK/Teile und Herrsche 2 SS10

Wiki-Quelltext dieser Seite.

Diese Seite setzt das in [[AuK/Teile und Herrsche 1 SS10]] begonnene Thema inhaltlich fort.

Autor:

Felix Deutschmann ([mailto:sifedeut@stud.hs-zigr.de sifedeut@stud.hs-zigr.de])

== Einführung ==
<p>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.</p><p>Weiterhin findet man hier auch die Vorlesungsunterlagen, sowie die Übungsaufgaben zu diesem Thema.</p>

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
== Binäre Suche ==
<p>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?".</p>
<p>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 <math>\mathcal{O}(n)</math> hat einen linearen Aufwand und ist für lange Liste nicht zu empfehlen. Eine Implementierung dieser Suche in Scheme ist folgende:
<code id="4bc0888750c85">(define usortSeqSuch
  (lambda (x ls)
    (cond
      ((null? ls) "Nicht gefunden!")
      ((= x (car ls)) 'Gefunden!)
      (else
       (usortSeqSuch x (cdr ls))))))</code>
<eval id="4bc088875144e">(usortSeqSuch 5 '(99 43 65 44 29 83 10 4 5 8 6))</eval>
</p><p>Dieser Suchalgorithmus hat zwei große sofort erkennbare Schwächen. <ul><li>der Aufwand steigt linear mit wachsender Elementeanzahl</li><li>die Liste wird komplett durchsucht, wenn das Element fehlt</li></ul>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.<code id="4bc08d12e4c7b">(define sortSeqSuch
  (lambda (x ls)
    (cond
      ((null? ls) "nicht gefunden")
      ((< x (car ls)) "nicht gefunden")
      ((= x (car ls)) "gefunden")
      (else
       (sortSeqSuch x (cdr ls))))))</code><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.</p>
<p>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:</p>
<p>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.</p>
<p>Zahlenbereich der ganzen Zahlen <math>\mathbb{Z}</math></p>

== Multiplikation großer ganzer Zahlen ==
== Schnelle Matrizenmultiplikation==
== Quellen ==