AuK/Teile und Herrsche 2 SS09

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
Diese Seite stellt eine inhaltliche Fortsetzung des Themas [[Teile und Herrsche 1]] dar.

 '''Die Seite befindet sich im Release-Candidate-Status. Um die hohen Qualitätsanforderungen zu erfüllen, sind alle Leser eingeladen, auf der'''
 '''Diskusions-Seite zum Wiki über den Inhalt und eventuelle Bugs zu diskutieren. [[Diskussion:Teile_und_Herrsche_2]]'''
 

== Einführende Worte == 

Auf dieser Seite werden, die Algorithmen ''Binäre Suche'', ''Strassens-Matrix-Multiplikation'' und den ''Multiplikations Algorithmus von Karatsuba'' vorgestellt.

Dabei findet ihr verschiedene Implementierungen der Algorithmen in Java und Scheme.

===Übungsaufgaben===

Die Übungsaufgaben zu diesen Themen findet ihr hier  '''[[Aufgaben - TuH2]]'''. 

Ihr findet aber auch im Text Hinweise und Hilfestellungen zu etwaigen Problemen auf die man während der Bearbeitung stoßen könnte. Ihr findet zusätzlich Programmierbeispiele in Java mit einigen Anmerkungen auf folgender Seite, [[TuH2_java]].

===Vorlesungs Folien===
<document>AuK_TuH2_presentation_wikiversion.pdf</document>

== 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 Sachverhalt beschreiben.  -->


=== Funktionsweise === 

Jeder war bestimmt schon einmal in einer Situation, in der man aus einer großen Menge von Informationen eine bestimmte wiederfinden musste. Als Beispiel dient das Suchen einer Seite anhand Ihrer Seitenzahl in dicken Büchern. Die meisten Menschen schauen in das Inhaltsverzeichnis und erhalten die Seitenzahl der gesuchten Information. Dann schlägt man das Buch in der Mitte auf und schaut ob die Seitenanzahl der Seite, auf der man sich nun befindet, größer oder kleiner ist, als die Seitenzahl unserer gesuchten Seite. Abhängig vom Ergebnis nimmt man die vordere oder hintere Hälfte des Buches und schlägt von dieser die Hälfte auf und vergleicht wieder... das wiederholt man solange bis die gesuchte Seite auftaucht.

<!-- 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, dass man die Mitte durch einen kurzen Blick genau lokalisiert) und zu prüfen, ob unser gesuchter Titel "''kleiner oder größer''" als der Titel des Buches in der Mitte ist.
-->
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 verglichen 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:
<math>$$L= \{ e_{1}, e_{2}, ... , e_{n} \}$$</math>

Wie erwähnt, muss die Liste bereits zu Beginn geteilt werden, dies geschieht beim Element mit dem Index k, die Mitte der Liste ist also <math>k = \frac{n}{2}</math>. Wobei man davon ausgehen kann, das die Liste nicht zwangsläufig ungerade 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}=\{e_{1}, e_{2}, ... a_{k}\}</math> und eine rechte Teilliste <math>L_{r}=\{e_{k+1}, e_{k+2}, ... e_{n}\}</math> oder anders dargestellt:

<math>L = \underbrace{e_{1}, e_{2}, ... e_{k}}_{L_{\text{l}}}, \underbrace{e_{k+1}, e_{k+2}, ... e_{n}}_{L_{\text{r}}}</math>


Jetzt wird unser Zielwert x mit dem ersten Element der rechten Liste <math>x < e_{k+1} </math> verglichen, abhängig vom Ergebnis wird mit <math>L_{r}</math> oder <math>L_{l}</math> weiter gearbeitet bzw. das Element ausgegeben. Natürlich kann bereits zu Beginn der Elementarfall eintreten das <math>e_{k} = x</math> ist. 

Fassen wir es noch einmal zusammen: 

<math>  
BinSuch = \left\{%
\begin{array}{ll}
BinSuch(L_{\text{l}}) &\textrm{wenn }x<e_{k},\\
BinSuch(L_{\text{r}}) &\textrm{wenn }x>e_{k+1},\\
print(a_{k}) &\textrm{wenn } x = a_{k}, \\
\textrm{"nicht Enthalten"} &\textrm{wenn } k < 0 \textrm{ oder } k > n\\
\textrm{"nicht Enthalten"} &\textrm{sonst }}
\end{array}%
\right
</math>




''' <tt>Übungsaufgabe: </tt>''' 
Probieren Sie die binäre Suche anhand eines Beispiels aus. Zeichnen Sie den Suchbaum auf.

''Siehe Aufgabe1(a) [[Aufgaben_-_TuH2#Aufgabe_.28a.29_-_Durchrechnen]]''


==== Vergleich mit der herkömmlichen sequenziellen Suche ====

Betrachten wir nun noch die einfachste Art des Suchens. Man nimmt eine Liste ''L'' mit der Länge ''n'', ein gesuchtes Element ''x'' und beginnt dieses mit jedem Element der Liste zu vergleichen. Dieses Verfahren besitzt linearen Aufwand. Wobei davon auszugehen ist, das die Wahrscheinlichkeit, das ''x'' mit dem Element ''a'' aus ''L'' übereinstimmt für jedes Element gleich ist.


----

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

Im Folgenden wird der Algorithmus, im Code als ''BinSuch'' betitelt, in Scheme und Java gezeigt. Man kann den Algorithmus in iterativer und rekursiver Form angeben. 

Zu erst benötigen wir wieder die Prozedur "teillisten2", welche im Kapitel "Teile und Herrsche 1" bei Mergesort bereits behandelt wurde.

<code hidden>
(define teillisten2
  (lambda (ls)
    (let ((k (floor (/ (length ls) 2))))
      (letrec
          ((helfer
            (lambda (ls i)
              (if (= i 0)
                  (values '() ls)
                  (call-with-values
                   (lambda ()(helfer (cdr ls)(- i 1)))
                   (lambda (links rechts)
                     (values (cons (car ls) links) rechts)))))))
        (helfer ls k)))))
</code>



Die Binäre Suche in Scheme:

<code>
(define binaersuche
  (lambda (x ls)
    (call-with-values
     (lambda () (teillisten2 ls))
     (lambda (lls rls)
       (cond 
         ((null? rls) "Schluessel nicht enthalten")
         ((= x (car rls)) "Schluessel gefunden")
         ((< x (car rls))
          (if (null? lls)
              "Schluessel nicht enthalten"
              (binaersuche x lls)))
         (else
          (if (null? (cdr rls))
              "Schluessel nicht enthalten"
              (binaersuche x rls))))))))
</code>

Zum Testen der Suche definieren wir uns eine Liste. Der Einfachheit halber wollen wir diese hier explizit angeben - zum selbstständigen Arbeiten können die Prozeduren "zzls" zum Erstellen einer Zufallszahlenliste und "mergesort" zum Sortieren selbiger verwendet werden. Die Prozeduren sind am Ende des Kapitels noch einmal aufgeführt und wurden in der Vorlesung "Teile und Herrsche 1" bereits behandelt.

<code>
(define liste '(4 8 15 16 23 42))
</code>

Wir möchten das Element 23 in der Liste suchen:
<eval>(binaersuche 23 liste)</eval>

Die Prozedur setzt uns davon in Kenntniss, dass das Element gefunden wurde. In der Praxis ist diese Aussage aber höchst unbefriedigend. Wünschenswert ist die Ausgabestelle, an welcher das Element gefunden wurde. Diese Funktionalität soll nun ergänzt werden. Ausserdem möchten wir einen Zähler implementieren, welcher die Anzahl der benötigten Rekursionsschritte aufzeichnet. Diese Information können wir im Anschluss für eine empirische Aufwandsanalyse des Verfahrens verwenden.

Die nötigen Modifikationen können wie folgt aussehen:

<code>
(define binhelfer
  (lambda (x ls)
    (call-with-values
     (lambda () (teillisten2 ls))
     (lambda (lls rls)
       (cond 
         ((null? rls)  "Schluessel nicht enthalten")
         ((= x (car rls)) (and (and (set! index (+ index (length lls))) 
           (and (string-append "Schluessel gefunden an Stelle " 
                (number->string index) ". Anzahl Rekursionen: " 
                (number->string calls))))))
         ((< x (car rls))
          (if (null? lls)
               "Schluessel nicht enthalten"
              (and (set! calls(+ calls 1))
                   (binhelfer x lls))))
         (else
          (if (null? (cdr rls))
              (string-append "Schluessel nicht enthalten. Anzahl Rekursionen: " (number->string calls))
              (and (set! calls (+ calls 1))
                  (and (set! index (+ index (length lls)))(binhelfer x rls))))))))))
</code>
Dabei wird davon ausgegangen, dass eine Zählervariable ''calls'' existiert, welche bei jedem Rekursionsschritt um mit ''(set! calls (+ calls 1))'' inkrementiert wird. 
Ausserdem wurde eine Variable ''index'' eingeführt, welche der Feststellung des Elementindexes bei erfolgreicher Suche dient. In diesem Fall wird mittels der Scheme-Sprachelemente ''sting-append'' und ''number->string'' ein passender Ausgabestring erzeugt. Andernfalls erscheint der Hinweis auf Nichtvorhandensein des Elements.

Aus Gründen der bequemeren Bedienbarkeit und um Fehler zu vermeiden, erstellen wir eine Prozedur ''binaersuche2'', aus welcher heraus die eben modifizierte Variante des Suchverfahrens aufgerufen wird. Diese Prozedur stellt zudem sicher, dass sowohl ''index'' als auch ''calls'' vor der Ausführung wieder auf 0 gesetzt werden. Würde dies nicht passieren, so müsste man bei mehrmaligem Aufrufen der Suchprozedur jedes mal die Variablen per Hand auf 0 zurücksetzen. 
<code>
(define index 0)
(define calls 0)
(define binaersuche2
  (lambda (x ls)
    (set! index 0)
    (set! calls 0)
    (binhelfer x ls)))
</code>


<eval>(binaersuche2 23 liste)</eval>


Die binäre Suche soll nun den Vergleich mit der klassichen sequenziellen Suche antreten, bei welcher, ausgehend vom kleinsten Element, jedes Element daraufhin überprüft wird, ob es das gesuchte Element ist. Wenn nicht, so wird mit dem Folgeelement weitergemacht. Hat man die komplette Liste durchsucht, ohne das gesuchte Element gefunden zu haben, so ist das Element nicht in der Liste enthalten.

Der Schemecode der sequenziellen Suche sieht folgendermaßen aus:

<code>
(define seqsuche
  (lambda (x ls)
    (cond
      ((null? ls) "Schluessel nicht enthalten.")
      ((= x (car ls)) (string-append "Schluessel gefunden an der Stelle " (number->string calls) ". Anzahl Rekursionen " (number->string calls)))
      ((< (car ls) x)(set! calls(+ calls 1))(seqsuche x (cdr ls)))
      (else "Schluessel nicht enthalten."))))
</code>
Auch hier wird die Anzahl der Rekursionsschritte für eine empirische Analyse aufgezeichnet. Da das Verfahren am Anfang der Liste beginnt, entspricht der Rekursionszähler im Fall eines gefundenen Elements gleichzeitig dem Index des Elements. Zusätzlichen Programmieraufwand für die Bestimmung der Position des gesuchten Elements kann damit gespart werden.

<eval>(seqsuche 23 liste)</eval>




''' <tt>Übungsaufgabe: </tt>''' 
Führen Sie eine empirische Analyse der binären Suche und der sequenziellen Suche durch und vergleichen Sie die Ergebnisse.

''Siehe Aufgabe1(b) [[Aufgaben_-_TuH2#Aufgabe_.28b.29_-_Empirische_Analyse]]''


== Visualisierung ==
''Test Canvas''

<canvas width="600" height="400"></canvas>
<code>
(clear canvas)
(home turtle)
</code>
Canvas wird erzeugt

<code>
(clear canvas)
(home turtle)
(left turtle 180)

(define binaersuche_turtle
  (lambda (x ls)
    (call-with-values
     (lambda () (teillisten2 ls))
     (lambda (lls rls)
       (cond 
         ((null? rls) "Schluessel nicht enthalten")
         ((= x (car rls)) "Schluessel gefunden")
         ((< x (car rls))
          (if (null? lls)
              "Schluessel nicht enthalten"
              (and (forward turtle 50)(binaersuche_turtle x lls))))
         (else
          (if (null? (cdr rls))
              "Schluessel nicht enthalten"
              (binaersuche_turtle x rls))))))))

(define listetest '(3 4 5 6 7))

(define v_left 0)
(define turtle_left
 (lambda ()
  (pencolor turtle 255 0 0)
  (if (= v_left 1)
    (forward turtle 50)
    (and (right turtle 45)(forward turtle 50)))))

</code>

<eval>
(binaersuche_turtle 3)
</eval>

=== Komplexitätsverhalten ===
==== Best Case ====

Es liegt nahe, dass es sich bei beiden Suchalgorithmen im besten Fall um einen ''konstanten'' Aufwand <math>\mathcal{O}(1)</math> handelt. Beim ''sequenziellen Suchen'' finden wir das Element am Anfang der zu durchsuchenden Liste und bei der ''binären Suche'' in der Mitte der Liste.

 Diese Erkenntnis ist für die Praxis eher irrelevant 
 von daher sollte man sich das Verhalten 
 im ''Average-'' und ''Worst Case'' genauer betrachten.

==== Average Case & Worst Case ====

In diesem Abschnitt wollen wir die binäre Suche und die sequenzielle Suche auf ihren Aufwand hin untersuchen.

Bei der ''sequenziellen Suche'' fällt bereits durch scharfes Hinsehen auf, das es sich im schlechtestem Fall um linearen Aufwand handelt. Denn die Laufzeit hängt von der Anzahl der Elemente ''n'' innerhalb der Liste ab. Also <math>\mathcal{O}(n)</math> egal ob das Element gefunden wird. Im Durschnitt hingegen kann die Suche lediglich <math>\frac{n}{2}</math> Vergleiche benötigen, wobei die Gleichverteilung aller Listen Elemente annehmen muss. Somit kommt ebenfalls ein linearer Aufwand <math>\Theta(n)</math> zustande. 

Die Rekursionsgleichung für die ''binäre Suche'' sieht folgender Maßen aus.

<math>T(n) = T(\frac{n}{2})+c</math>

Wie kommt dieses dazu? Um diese Frage zu beantworten, betrachten wir die Schritte folgendermaßen:

* Für diese Untersuchung nehmen wir an, das die Schritte in einem Aufruf unserer rekursiven Prozedur einen konstanten Aufwand <math>c</math> besitzt. In den Übungsaufgaben sollten sie sich mit dieser Annahme noch einmal beschäftigen. 

* Wir wissen, das der Suchraum <math>n</math> bei jedem rekursiven Aufruf halbiert wird, und auf eine der beiden Hälften unser Algorithmus erneut angewendet wird. Dies wird durch <math>T(\frac{n}{2})</math> beschrieben.

Unter der Annahme, dass die Länge der Liste ''n'' <math>2^k</math> entspricht, wird sehr schnell deutlich, wie oft der Algorithmus rekursiv hochstens durchlaufen werden kann, bevor das Element gefunden wird oder die Abbruchbedingung eintritt. Dies tritt im WorstCase nach <math>k</math> Schritten ein, da die Liste nur <math>k</math>-mal halbiert werden kann.
Daraus ergibt sich die Beziehung <math> n=2^k \rightarrow k = \log_2 n </math>.

Daraus folgt die asymptotische Ordnung von:
<math>\mathcal{O}(\log_2 n)</math>

Kurz gesprochen heißt dies nun, dass wir für eine Liste mit 1024 Elementen garantieren können, dass wir nach spätestens <math>\log_2 1024 = 10</math> Schritten das Suchergebnis bekommen. Bei einer Liste mit ungefähr 1000000 Elemente mit 20 Schritten. Auf eine graphische Darstellung wird an dieser Stelle verzichtet. Da sie sich mit einer empirischen Analyse sowie der Darstellung mittels Gnuplot in den Übungsaufgaben auseinander setzen können.


''' <tt>Übungsaufgabe: </tt>''' 
Schauen Sie sich die Schemeimplementation der binären Suche etwas genauer an und finden Sie heraus, warum der Aufwand dieser Implementation nicht logarithmisch ist. Entwerfen Sie eine verbesserte Version, welche tatsächlich logarithmischen Aufwand besitzt. 

''Siehe Aufgabe1(c) [[Aufgaben_-_TuH2#Aufgabe_.28c.29_-_Modifikation_der_Binaeren_Suche]]''

== Die Multiplikation nach Karatsuba und Offman ==

Wir kennen die Multiplikation aus der Schule und haben die sog. ''Russische Bauernmultiplikation'' (Multiplikation à la Russe) kennengelernt. Infolge dessen, wollen wir hier noch ein anderes Multiplikationsverfahren analysieren. Zunächst ist die Frage interessant, warum man überhaupt noch einen Multiplikationsalgorithmus benötigt, wir haben ja alle in der Schule eine ganz brauchbare Lösung kennengelernt. Doch leider hat dieser quadratischen Aufwand sprich <math>\mathcal{O}(n^2)</math>. Das heißt konkret, dass wir für die Multiplikation von sehr sehr großen Zahlen Unmengen von Operationen benötigen. Wir gehen an dieser Stelle nicht weiter darauf ein, in der Übung könnt ihr euch mit der Analyse der ''Schulbuchmultiplikation'' auseinander setzen.

=== Wie funktioniert es? ===
Wir nehmen 2 Zahlen ''a'' und ''b'', wir vereinbaren das deren Stelligkeit ''n'' gleich und gerade ist. Dann zerlegen wir diese beiden Zahlen in jeweils 2 gleiche Teile. Im einfachsten Fall <math>n = 1</math> haben wir entsprechend nur eine Operation nämlich <math>a \cdot b</math>. Betrachten wir <math>n = 2</math>, als Beispiel dienten uns die Zahlen 14 und 73. Die beiden Faktoren werden wie folgt zerlegt,

<math>
x = x_{1} \cdot 10 + x_{0}
</math>

Wobei ''B'' für die Basis der Zahlendarstellung steht. In unserm Fall 10.

<math>
a = 14 =1 \cdot 10 + 4
</math>

<math>
b = 73 = 7 \cdot 10 + 3
</math>

Im nächsten Schritt schau wir uns an wie die Multiplikation von a und b mit Hilfe der Ziffern aussieht.

<math>
\begin{array}{ccl}
a \cdot b & = & (a_{1} \cdot 10 + a_{0}) \cdot (b_{1} \cdot 10 + b_{0}) \\
& = & (a_{1} \cdot b_{1}) \cdot 100 + (a_{1} \cdot b_{0} + a_{0} \cdot b_{1}) \cdot 10 + a_{0} \cdot b_{0}\\
& = & (1 \cdot 7) \cdot 100 + (1 \cdot 3 + 4 \cdot 7) \cdot 10 + 4 \cdot 3 \\
& = & 1022
\end{array}
</math>

Ruft man sich das Verfahren ins Gedächtnis, welches wir einmal in der Schule gelernt haben, stellen wir schnell fest, dass uns unser neuer Algorithmus kein besseres Verfahren liefert.

Wir haben nach wie vor lediglich 4 Multiplikationen und die Addition der Ergebnisse.
Der Trick, welchen Karatsuba anwendet, sieht wie folgt aus, er nutzt lediglich 3 Multiplikationen um folgende Werte zu berechnen.
Er stellt die Formel auf geeignete Weise um und erhält:

<math>(a_{1} \cdot b_{1}) \cdot 10^2 + ( (a_{1} \cdot b_{1}) + (a_{0} \cdot b_{0}) - (a_{0} - a_{1}) \cdot (b_{0} - b_{1}) ) \cdot 10 + a_{0} \cdot b_{0}</math>

Diese Formel sieht auf den ersten Blick kompliziert aus, man stellt jedoch fest, dass gewisse Multiplikationen mehrmals auftreten. 
Wir fassen diese folgender Maßen zusammen:

<math>
\begin{array}{ccl}
r & = &  a_{1} \cdot b_{1}\\
s & = & (a_{0} - a_{1}) \cdot (b_{0} - b_{1}) \\
t & = & a_{0} \cdot b_{0}
\end{array}
</math>

Für unser Beispiel:

<math>
\begin{array}{lccll}
r & = & 7 & = &  1 \cdot 7 \\
s & = & -12 & = & (4 - 1) \cdot (3 - 7) \\
t & = & 12 & = & 4 \cdot 3
\end{array}
</math>

 An dieser Stelle wird auch die Absicht deutlich, die Karatsuba verfolgt!
 Die aufwendigeren Multiplikations-Operationen in weniger aufwendige Additions bzw. Subtraktions-
 Operationen aufzuspalten. Dies ist aber noch nicht alles, was den Algorithmus so beschleunigt!

Was bringen diese drei neuen Werte? Karatsuba setzt diese Werte nun folgendermaßen in die ursprüngliche Form ein:

<math>(a_{1} \cdot b_{1}) \cdot 10^2 + ( (a_{1} \cdot b_{1}) + (a_{0} \cdot b_{0}) - (a_{0} - a_{1}) \cdot (b_{0} - b_{1}) ) \cdot 10 + a_{0} \cdot b_{0}</math>

Betrachtet man diese zunächst unübersichtliche Gleichung etwas vereinfacht, wird ein interessanter Vorteil deutlich:

<math>a \cdot b = r \cdot 10^2  + (r + t  - s) \cdot 10 + t</math>

 <math>r</math> und <math>t</math> werden einmal berechnet, 
 aber in der Gesamtberechnung jeweils zwei mal verwendet.

Um das Zahlenbeispiel noch fertig zu berechnen,

<math>7 \cdot 10^2 + (7 + 12 - (-12)) \cdot 10 + 12 = 1022</math>

Für 2-stellige Zahlen sieht dieses Verfahren unnötig kompliziert aus. Betrachten wir nun 4-stelligen Zahlen!

Es werden genauso die beiden Faktoren halbiert, nur mit dem Unterschied, das man nun keine Ziffern mehr hat, sondern 2-stellige Zahlen. Mit diesen lässt es sich ebenso verfahren, wie bereits oben mit den Ziffern dargestellt:

<math>
\begin{array}{ll}
a = & 7245 = 72 \cdot 10 + 45 \\
a_{1} & = 72 \\
a_{0} & = 45
</math>


<math>
\begin{array}{ll}
b = & 5273 = 52 \cdot 10 + 73 \\
b_{1} & = 52 \\
b_{0} &= 73
</math>


<math>
\begin{array}{lccll}
r & = & 3744 & = &  72 \cdot 52 \\
s & = & -567 & = & (45 - 72) \cdot (73 - 52) \\
t & = & 3285 & = & 45 \cdot 73
\end{array}
</math>

Aus diesen Schritten ergibt sich nun:

<math>a \cdot b = r \cdot 10^4  + (r + t  - s) \cdot 10^2 + t</math>

<math>7245 \cdot 5273 = 3744 \cdot 10^4  + (3744 + 3285  - (-567)) \cdot 10^2 + 3285</math>

Wirklich interessant ist nun noch die Multiplikation beliebig langer Zahlen, diese kommt in allgemeiner Form wie folgt zustande:

Die Zerlegung der Faktoren:

<math>a = a_1 \cdot 10^{\frac{n}{2}} + a_0</math>

<math>a = b_1 \cdot 10^{\frac{n}{2}} + b_0</math>

Das Produkt mit Hilfe der '''3''' Multiplikationen von Zahlen der Länge <math>\frac{n}{2} = 2^{k-1}</math>:

<math>a \cdot b = a_1 \cdot b_1 \cdot 10^n +(a_1 \cdot b_1 + a_0 \cdot b_0 -(a_0 - a_1)\cdot (b_0 - b_1) ) \cdot 10^{\frac{n}{2}}+ a_0 \cdot b_0</math>


 Hinweis: Für den Karatsuba-Algorithmus ist es notwendig, dass beide Zahlen die Gleiche Stelligkeit haben und diese Stelligkeit eine Zweierpotenz ist, es muss also  
 gelten: <math>n_{a} = n_{b} = n^k</math>, wobei <math>k \in \mathbb{N}</math>
 Um das in jedem Fall zu gewährleisten, muss bei einer Implementation des Algorithmus sichergestellt werden, dass a und b mit führenden Nullen aufgefüllt werden, falls
 diese Bedingung nicht von vorn herein gegeben ist.
 


''' <tt>Übungsaufgabe: </tt>''' 
Rechnen sie die Karatsuba-Methode einmal per Hand mit den gegebenen Werten durch.

''Siehe Aufgabe2(a) [[Aufgaben_-_TuH2#Aufgabe_.28a.29]]''

=== Aufwandsbetrachtung ===

Wir benötigen zur Bestimmung des Aufwandes die '''Meistermethode'''. Mit dieser bestimmen wir zunächst den Aufwand der Schulbuchmethode. Dies lässt sich mit folgender ''rekursiven Formel'' darstellen <math>T(n)= 4 \cdot T(\frac{n}{2}) + \Theta(n) </math>.

<!-- TODO Das muss noch überprüft werden!!! --> 
Wir wenden den zweiten Fall der Meistermethode an:

Wenn <math>f(n) = \Mathcal{O}(n^{\log_b a})</math>

<math>T(n)=\Theta(n^{\log_2 4}) = \Mathcal{O}(n^{2})</math>

Die ''Rekursionsformel'' des '''Karatsuba Algorithmus''' sieht ähnlich aus, 

<math>T(n)= 3 \cdot T(\frac{n}{2}) + \Theta(n) </math> 

jedoch werden wir sehen, dass die fehlende Multiplikation einen beträchtlichen Effiziensgewinn hervorruft.

Wir wenden auch hier wieder die '''Meistermethode''' an.

<math>T(n)=\Theta(n^{\log_2 3}) \approx \Theta(n^{1,585})</math>

=== Zusätzliche Betrachtung ===
Nehmen wir uns die Aufwände der eben genannten Multiplikationsverfahren noch einmal vor, um zu sehen, wie diese sich verhalten. 
*Aufwand für die Schulbuchmultiplikation = <math>\mathcal{O}(n^2)</math>
*Aufwand für Multiplikation à la Russe = <math>\mathcal{O}(n^2)</math> 
*Aufwand für Karatsubas Algorithmus = <math>\Theta(n^{1,585})</math>

Um den, durch die fehlende Multiplikation verursachten, gigantischen Unterschied noch einmal zu verdeutlichen, sollte man folgende Tabelle betrachten!

<math>
\begin{array}{r|r|r}
n & \textrm{Karatsuba} & \textrm{Schulbuch} \\
\hline
1 = 2^0            &  1  	   &   1 \\
2 = 2^1            &  3 	   &   4 \\
4 = 2^2            &  9 	   &  16 \\
8 = 2^3            & 27 	   &  64 \\
16 = 2^4           & 81 	   & 256 \\
32 = 2^5           & 243 	   & 1.024 \\
64 = 2^6           & 729 	   & 4.096 \\
128 = 2^7          & 2.187 	   & 16.384 \\
256 = 2^8          & 6.561 	   & 65.536 \\
512 = 2^9          & 19.638 	   & 262.144 \\
1.024 = 2^{10}     & 59.049 	   & 1.048.576 \\
1.048.576 = 2^{20} & 3.486.784.401 &	1.099.511.627.776 
\end{array}
</math>

<gnuplot>
set title "Vgl. Karatsuba vs. russisches Schulbuch"
set yrange [0:265000]
set xtics (1000,10000, 50000, 100000, 280000)
set xrange [0:1024]
set xlabel "n"
set ylabel "T(n)"
plot \
<dataset>
1 1
2 3
4 9
6 17
8 27
12 51
16 81
24 154
32 243
45 417
64 729
96 1386
128 2187
192 4159
256 6561
384 12478
512 19638
768 37436
1024 59049
</dataset> using 1:2 title "Karatsuba" with lines lt 4, \
<dataset>
1 1 
2 4
4 16 
6 36
8 64
12 144
16 256 
24 576
32 1024
45 2025
64 4096
96 9216
128 16384
192 36864
224 50176
256 65536
320 102400
384 147456
448 200704
512 262144
</dataset> using 1:2 title "Schulbuch" with lines lt 14
</gnuplot>

== Die schnelle Matrix Multiplikation ==

Ein weiteres Beispiel für den Nutzen der "Teilen und Herrschen"-Strategie ist die Matrixmultiplikation. 

=== Die Schulbuchmethode ===
'''Beschreibung'''

Die Schulbuchmethode dafür sieht vor, jedes Element der ersten Zeile der ersten Matrix, mit der ersten Spalte der zweiten Matrix zu multiplizieren und die Produkte zu summieren. Damit erhält man das Element der ersten Zeile und ersten Spalte der Ergebnismatrix. Diesen Vorgang wiederholt man nun für alle weiteren Kombinationen von Zeilen und Spalten. (Korrekt so?)
Beispiel:

<math>
A =
 \left(
   \begin{array}{cccc}
    2 & 4 & 6 & 5 \\
    3 & 6 & 9 & 3 \\
    1 & 2 & 3 & 4 \\
    4 & 5 & 3 & 7 \\
   \end{array}
 \right)
</math>


<math>
B =
\left(
 \begin{array}{cccc}
   1 & 3 & 5 & 7 \\
   5 & 4 & 3 & 2 \\
   8 & 2 & 6 & 4 \\
   3 & 2 & 6 & 9 \\
   \end{array}
 \right)
</math>


<math>
A*B =
\left(
  \begin{array}{cccc}
    \left(2*1 + 4*5 + 6*8 + 5*3\right)&\left(2*3 + 4*4 + 6*2 + 5*2\right)&\left(2*5 + 4*3 + 6*6 + 5*6\right)&\left(2*7 + 4*2 + 6*4 + 5*9\right)\\
    \left(3*1 + 6*5 + 9*8 + 3*3\right)&\left(3*3 + 6*4 + 9*2 + 3*2\right)&\left(3*5 + 6*3 + 9*6 + 3*6\right)&\left(3*7 + 6*2 + 9*4 + 3*9\right)\\
    \left(1*1 + 2*5 + 3*8 + 4*3\right)&\left(1*3 + 2*4 + 3*2 + 4*2\right)&\left(1*5 + 2*3 + 3*6 + 4*6\right)&\left(1*7 + 2*2 + 3*4 + 4*9\right)\\
    \left(4*1 + 5*5 + 3*8 + 7*3\right)&\left(4*3 + 5*4 + 3*2 + 7*2\right)&\left(4*5 + 5*3 + 3*6 + 7*6\right)&\left(4*7 + 5*2 + 3*4 + 7*9\right)\\
  \end{array}
\right)
</math>

<math>
A*B =
\left(
 \begin{array}{cccc}
   85 & 44 & 88 & 91 \\
   114 & 57 & 105 & 96 \\
   47 & 25 & 53 & 59 \\
   74 & 52 & 95 & 113 \\
 \end{array}
\right)

</math>

Für einfache, d.h. kleine Matrizen ist diese Berechnungsvorschrift für den Menschen einfach zu merken und zu benutzen. Wenn jedoch die Größe der Matrizen wächst,erkennt man schnell, dass sehr viele Einzelberechnungen durchgeführt werden müssen.

'''Aufwandsanalyse'''

Man erkennt, dass für eine (n,n)-Matrix für jedes Element der Ergebnismatrix jeweils jedes Element der entsprechenden Zeile der ersten Matrix, mit jedem Element der entsprechenden Spalte der zweiten Matrix multipliziert werden muss. Daraus ergibt sich ein Aufwand von <math>\mathcal{O}(n^3)</math>

===Strassen-Algorithmus===
'''Beschreibung'''

Einen anderen Ansatz wählt der nach Volker Strassen benannte STRASSEN-Algorithmus. Bei diesem müssen die Ausgangsmatritzen zuerst in Teilmatrizen nach folgendem Muster zerlegt werden:
<math>
C = A * B =
\left(
 \begin{array}{cc}
   A_{1,1} & A_{1,2} \\
   A_{2,1} & A_{2,2} \\
 \end{array}
\right)
*
\left(
 \begin{array}{cc}
   B_{1,1} & B_{1,2} \\
   B_{2,1} & B_{2,2} \\
 \end{array}
\right)
=
\left(
 \begin{array}{cc}
  C_{1,1} & C_{1,2}\\
  C_{2,1} & C_{2,2}\\
 \end{array}
\right)

</math>


Die Teilmatrizen sehen folgender Maßen aus:


<math>
A_{1,1}=
\left(
 \begin{array}{cc}
   2 & 4 \\
   3 & 6 \\
 \end{array}
\right)
A_{1,2}=
\left(
 \begin{array}{cc}
  6 & 5 \\
  9 & 3 \\
 \end{array}
\right)
A_{2,1}=
\left(
 \begin{array}{cc}
  1 & 2 \\
  4 & 5 \\
 \end{array}
\right)
A_{2,2}=
\left(
 \begin{array}{cc}
  3 & 4 \\
  3 & 7 \\
 \end{array}
\right)
</math>

<math>
B_{1,1}=
\left(
 \begin{array}{cc}
  1 & 3 \\
  5 & 4 \\
 \end{array}
\right)
B_{1,2}=
\left(
 \begin{array}{cc}
  5 & 7 \\
  3 & 2 \\ 
 \end{array}
\right)
B_{2,1}=
\left(
 \begin{array}{cc}
  8 & 2 \\
  3 & 2 \\
 \end{array}
\right)
B_{2,2}=
\left(
 \begin{array}{cc}
  6 & 4 \\
  6 & 9 \\
 \end{array}
\right)
</math>


Die Teilmatrizen der Lösungsmatrix C erhält man durch folgende Berechnungen:


<math>
\begin{array}{lll}
C_{1,1} & = & A_{1,1} * B_{1,1} + A_{1,2} * B_{2,1} \\

C_{1,2} & = & A_{1,1} * B_{1,2} + A_{1,2} * B_{2,2} \\

C_{2,1} & = & A_{2,1} * B_{1,1} + A_{2,2} * B_{2,1} \\

C_{2,2} & = & A_{2,1} * B_{1,2} + A_{2,2} * B_{2,2}
\end{array}
</math>


Dies alleine stellt aber noch keine Effizienzverbesserung dar, da immer noch 8 (aufwandsmäßig ungünstige) Matrizenmultiplikationen mit einem Aufwand von <math> T(\frac{n}{2})</math> durchgeführt werden müssen. Die eigentliche Leistung des STRASSEN-Algorithmus liegt in der Berechnung von Hilfsmatrizen nach folgendem Muster:


<math>
\begin{array}{lll}
M_{1} & = & (A_{1,2} - A_{2,2}) * (B_{2,1} + B_{2,2} ) \\

M_{2} & = & (A_{1,1} + A_{2,2}) * (B_{1,1} + B_{2,2} ) \\

M_{3} & = & (A_{1,1} - A_{2,1}) * (B_{1,1} + B_{1,2} ) \\

M_{4} & = & (A_{1,1} + A_{1,2}) * B_{2,2} \\

M_{5} & = & A_{1,1} * (B_{1,2} + B_{2,2}) \\

M_{6} & = & A_{2,2} * (B_{2,1} + B_{1,2}) \\

M_{7} & = & (A_{2,1} + A_{2,2} ) * B_{1,1}
\end{array}
</math>


Die Ergebnismatrix <math>C</math> ergibt sich durch:

<math>
\begin{array}{lll}
C_{1,1} & = & M_{1} + M_{2} - M_{4} + M_{6} \\

C_{1,2} & = & M_{4} + M_{5} \\

C_{2,1} & = & M_{6} + M_{7} \\

C_{2,2} & = & M_{2} - M_{3} + M_{5} - M_{7}
\end{array}
</math>

'''Aufwandsanalyse'''

Strassens Algorithmus benötigt zur Berechnung des Produkts nun nur noch 7 Matrizenmultiplikationen statt 8 wie das oben gezeigte Verfahren. Die Aufwandsanalyse ergibt:
<math>
T(n) = 7* T(\frac{n}{2}) + \mathcal{O}(n^2)

\rightarrow T(n) = \mathcal{O}(n^{log_{2}(7)}) = \mathcal{O}(n^{2,81})
</math> 

Für die klassische Methode ergibt ein Aufwand von <math> T(n) = \mathcal{O}(n^{log_{2}(8)}) = \mathcal{O}(n^3)</math>

Es wird ein ähnliches Ziel wie auch schon beim Karatsuba-Algorithmus verfolgt: Nach Möglichkeit "kostspielige" Multiplikationen durch "günstige" Additionen bzw. Subtraktionen zu ersetzen. So benötigt der STRASSEN-Algoritmus ganze 18 Additionen/Subtraktionen wärend die oben gezeigte Variante mit nur 4 Stück auskommt. Da der Aufwand dieser Matrizenadditionen aber lediglich in <math>\mathcal{O}(n^2)</math> liegt, stellt dieser Tausch bei großen <math>n</math> einen Effizenzgewinn dar.

Der praktische Nutzen des Algorithmus ist allerdings beschränkt, da die ''[http://de.wikipedia.org/wiki/Stabilit%C3%A4t_(Numerik) numerische Stabilität]'', d.h. die Empfindlichkeit gegenüber Rundungsfehlern, schlechter ist als bei der klassischen Methode.

<!-- Beispiel Matrix
<math>
\left(
   \begin{array}{ccc}
     a_{11} & \cdots & a_{1n} \\
     \vdots & \ddots & \vdots \\
     a_{m1} & \cdots & a_{mn}
   \end{array}
\right)
</math>
-->


====In Scheme====

Siehe [[TuH2_scheme]]