AuK/Teile und Herrsche 2 SS09

Wiki-Quelltext dieser Seite.

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

 '''Wichtig! Die Seite ist noch NICHT FINAL es können sich noch Fehler und unsauberkeiten finden lassen, erst wenn dieser Text'''
 '''hier nicht mehr zu lesen ist, wird die Seite von Uns als fertig betrachtet!'''

== Zusammenfassung == 

<!--TODO: Um was geht es auf dieser Seite? Welche Fragen werden gestellt, beantwortet und was wird genauer erklärt? -->
Auf dieser Seite soll versucht werden, die Algorithmen ''Binäre Suche'', ''Strassens-Matrix-Multiplikation'' und den ''Multiplikations Algorithmus von Karatsuba'' in Hinblick auf die Arbeitsweisen und den Aufwand (Effiziensanalyse) der einzelnen Verfahren vorzustellen. Dabei findet ihr verschiedene Implementierungen der Algorithmen in Java und Scheme.

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.


== 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 wiederfinden musste. Als Beispiel dient das Suchen einer Seite anhand Ihrer Seitenzahl in dicken Büchern. Die meisten Menschen schauen in das Inhaltsverzeichnis und erhält die Seitenzahl der gesuchten Information. Dann schlägt man das Buch in der Mitte auf und schaut ob die Seiteanzahl 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 man 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 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 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 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}=\{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 < a_{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 Begin der Elementarfall eintreten das <math>a_{k} = x</math> ist. 

Fassen wir es 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},\\
print(a_{k}) &\textrm{wenn } x = a_{k}, \\
\textrm{"nicht Enthalten"} &\textrm{sonst }}
\end{array}%
\right
</math>


<!--REVIEW


DA ist ein Fehler in der Gegenüberstellung mit BinSuch
ihr habt mit x < ak, x = ak, x > ak 
alle Fälle abgedeckt
es gibt keinen "Sonst"-Fall
Du musst noch die maximalzahl an miteinbeziehen ,)
also die Formeln
(1 <= x) und x < ak
dann hast du
x = ak
 x > ak und x < an
und der sonstfall: x > an
und das ist "nicht enthalten"

wenn das Buch korrekt ist, wird es nicht vorkommen
weil in dem Inhaltsverzeichnis keine Seiten sind, die nicht enthalten sind
Außer das Buch hat fehler..
Ich habe so ein Buch hioe
Ich habe so ein Buch hier
von Erich von Däniken
da fehlen die Seite 15x - 21x
dafür sind die sEiten 9x - 15x doppelt hintereinander abgedruckt
Aberr das Buchbeispiel ist nicht so "wasserdicht"
Auf den Bewei O(n) für n/2 wird verzichtet
das bisschen mit lim ( n/2) gegen unendlich kannst du auch zeigen *HAPPY*
also n gegen unendlich *HAPPY*



-->


==== Vergleich mit der herkömlichen 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. 

====In Java====

Siehe [[TuH2_java]]

====In Scheme====

Siehe [[TuH2_scheme]]

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

Wir wollen in diesem Abschnitt die ''Binäre Suche'' in der iterativen als auch rekursiven Variante Untersuchen, zuvor wollen wir kurz abschweifen und die ''squenzielle Suche'' kurz untersuchen. 

Bei der ''sequenziellen Suche'' fällt bereits durch scharfes Hinsehen auf, das es sich im schlechtestem Fall um linearen Aufwand handelt. Den 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 man die Gleichverteilung aller Listen Elemente annehmen muss. Somit kommt ebenfalls ein linearer Aufwand <math>\Theta(n)</math> zustande. 



Die rekursions Gleichung für die ''binäre Suche'' sieht folgender Massen aus.

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

Betrachten wir nun die ''iterative Variante'' der ''binären Suche''. Dazu betrachten wir das Intervall in welchem gesucht wird und das Verhalten dessen Größe während der Suche.
Unsere Variablen für die Positionen im zu durchsuchenden Feld verantwortlich sind haben beim Start folgende Belegungen:

<math>
\begin{array}{lcl}
\text{Start} & = & 0 \\
\text{Ende} & = & Feldleange - 1 \\
\text{Feldleange zu Begin} & = & \text{start} + \text{Ende} \\
\text{Mitte des Feldes} & = & \dfrac{\text{Start} + \text{Ende}}{2} \\
\end{array}
</math>

Das Intervall ändert sich wie folgt:

<math>
\begin{array}{lcl}
\text{Neue Feldlaenge} & = &  \text{Ende} - \text{Start} + 1 \\
 & = & \text{Ende} - (\text{Mitte} + 1) + 1 \\
 & = & \text{Ende} - \text{Mitte des Feldes} \\
 & = & \text{Ende} - \dfrac{\text{Start} + \text{Ende}}{2} \\
 & = & \dfrac{2 \cdot \text{Ende}}{2} - \dfrac{\text{Start} + \text{Ende}}{2} \\
 & = & \dfrac{\text{Ende} - \text{Start}}{2}
\end{array}
</math>

Kurz gefasst ändert sich das Intervall in jedem Durchlauf der Schleife von der Länge ''n'' auf <math>\dfrac{n - 1}{2}</math>. Was heist das nun konkret? Wir haben 2 Intervalle zwischen denen es sich jeweils zu entscheiden gilt und dafür brauchen wir ''k'' durchläufe. Somit haben <math>2^k</math> Operationen um ''n'' Elemente zu durchsuchen.

<math>2^k = n</math> Das lässt sich mit dem Logarithmus zur Basis 2 errechnen.

 <math>\log_{2} n = k \curvearrowright \mathcal{O}(\log_2 n)</math> 
 Dieses Ergebnis zaubert ein grinsen ins Gesicht, 
 da ein Algorithmus mit logarithmischer Laufzeit äußerst Effizient arbeitet.

Den Unterschied zwischen linearem und logarithmischen Aufwand kann man sich mittels empirischer Analyse vor Augen halten, dazu findet ihr zwei Aufgaben auf der Übungsseite [[http://www.michael-hielscher.de/wiki/index.php/Aufgaben_-_TuH2#Aufgaben_zur_Bin.C3.A4ren_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 Multipliaktionsalgorithmus 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 das 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 mit der Analyse der ''Schulbuchmultiplikation'' auseinander setzen.

=== Wie funktionierts? ===
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 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 das uns unser neuer Algorithmus kein besseres Verfahren liefert.

<!--
Nach der Schulbuchmethode sieht die Rechnung wie folgt aus. 
<math>
\begin{array}{lllll}
14 && \cdot & 73 \\ 
 &&28& \\
+&17&& \\
+&12& \\
+&30& \\
\hline
=&1022&
\end{array}
</math>
-->

Wir haben nach wie vor lediglich 4 Multiplikationen und die Addition der Ergebnisse.
Die Trick den Karatsuba entdeckt hat sieht wie folgt aus, er nutzt lediglich 3 Multiplikationen um folgende Werte zu berechnen,

 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!

<math>
\begin{array}{ccl}
m & = &  a_{1} \cdot b_{1}\\
n & = & (a_{0} - a_{1}) \cdot (b_{0} - b_{1}) \\
o & = & a_{0} \cdot b_{0}
\end{array}
</math>

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







<!-- TODO -->

<!--
<math>
x = x_{1}b^{\frac{n}{2}}+x_{0}
</math>

<math>
y = y_{1}b^{\frac{n}{2}}+y_{0}
</math>

Gesucht ist nach wie vor, das Produkt aus ''x'' und ''y''.

<math>
y \cdot x = ?
</math>

Dazu multipliziert man zunächst die Teile <math>x_{1}</math> und <math>y_{1}</math> mit der Basis <math>b^{n}</math>. Die erste von 4 Teiloperationen.

<math>
y \cdot x = (x_{1} \cdot y_{1})b^{n} \dots
</math>
-->
<!-- TODO -->

=== 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>.
<!--
Wir wenden den zweiten Fall der Meistermethode an:

Wenn <math>f(n) = \Mathcal{O}(n^{\log_b a})</math>
-->
=== Zusätzliche Betrachtung ===
Nehmen wir uns die Aufwände der eben genannten Multiplikationsverfahren noch einmal zu Brust 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>
<!-- TODO: Überarbeiten! Zahlen stimmen noch nicht... -->
[[Bild:Vgl_Mul.png]]

=== Wie kann man Karatsubas Idee Programmieren? ===

Eine Implementation in JAVA

<code>import java.math.*;


public class Karatsuba_class {

	
	public BigInteger karatsuba (BigInteger x, BigInteger y)
	{
		int n = Math.max(x.bitLength(),y.bitLength());
		if (n <= 1) return x.multiply(y);
		
		n=n /2;
		BigInteger xH = x.shiftRight(n);
		BigInteger xL = x.subtract (xH.shiftLeft(n));
		BigInteger yH = y.shiftRight (n);
		BigInteger yL = y.subtract (yH.shiftLeft(n));
		
		BigInteger p1 = karatsuba(xH, yH);
		BigInteger p2 = karatsuba(xL, yL);
		BigInteger p3 = karatsuba (xL.add(xH), yL.add(yH));
		
		return p1.shiftLeft(2*n).add(p3.subtract (p1).subtract (p2).shiftLeft(n)).add(p2);
	}
}</code>

== 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 jede 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,2} & = & 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 immernoch 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.

===Vergleich===
ToDo



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


=== praktische Probleme ===
<!--
Die besprochene Methode weist leider schwächen auf,

*Das rekursive erstellen der Teilmatrizen benötigt unverhältnismässig viel Speicherplatz
-->

[http://www.michael-hielscher.de/wiki/index.php/Aufgaben_-_TuH2#weitere_Aufgaben testest]