AuK/Teile und Herrsche 2 SS10/Aufgaben Lösung

Wiki-Quelltext dieser Seite.

Diese Seite hält die Lösungen der Aufgaben auf der Seite [[AuK/Teile und Herrsche 2 SS10/Aufgaben]] bereit.
== Lösungen zu den Übungsaufgaben ==
===Multiplikation großer ganzer Zahlen nach KARATSUBA und OFMAN===
===Schnelle Matrixmultiplikation nach STRASSEN===
Gegeben sind die zwei Matrizen <math>A</math> und <math>B</math> mit:

<math>
A=\begin{pmatrix}
3 & 8 & 9 & 7\\
6 & 2 & 8 & 4\\
4 & 3 & 6 & 2\\
7 & 6 & 7 & 5
\end{pmatrix}</math> und 
<math>B=\begin{pmatrix}
6 & 4 & 7 & 5\\
3 & 1 & 2 & 9\\
7 & 6 & 8 & 8\\
9 & 3 & 5 & 4
\end{pmatrix}</math>

Die Matrizen zerlegt man nach folgendem Muster in Teilmatrizen:


<math>
C=A\cdot B=
\begin{pmatrix}
A_{1,1} & A_{1,2}\\
A_{2,1} & A_{2,2}
\end{pmatrix}\cdot
\begin{pmatrix}
B_{1,1} & B_{1,2}\\
B_{2,1} & B_{2,2}
\end{pmatrix}
=\begin{pmatrix}
C_{1,1} & C_{1,2}\\
C_{2,1} & C_{2,2}
\end{pmatrix}
</math>

Daraus ergeben sich die 8 Teilmatrizen:

<math>A_{1,1}=\begin{bmatrix}3 & 8\\6 & 2\end{bmatrix}\text{, } A_{1,2}=\begin{bmatrix}9 & 7\\8 & 4\end{bmatrix}\text{, } A_{2,1}=\begin{bmatrix}4 & 3\\7 & 6\end{bmatrix}\text{, } A_{2,2}=\begin{bmatrix}6 & 2\\7 & 5\end{bmatrix}\\
B_{1,1}=\begin{bmatrix}6 & 4\\3 & 1\end{bmatrix}\text{, } B_{1,2}=\begin{bmatrix}7 & 5\\2 & 9\end{bmatrix}\text{, } B_{2,1}=\begin{bmatrix}7 & 6\\9 & 3\end{bmatrix}\text{, } B_{2,2}=\begin{bmatrix}8 & 8\\5 & 4\end{bmatrix}\\</math>

Damit lassen sich <math>M_{1}</math> bis <math>M_{7}</math> berechnen:

<math>
M_{1}=(A_{1,2}-A_{2,2})\cdot(B_{2,1}-B_{2,2})=\begin{pmatrix}3 & 5\\1 & -1\end{pmatrix}\cdot\begin{pmatrix}-1 & -2\\4 & -1\end{pmatrix}=\begin{pmatrix}17 & -11\\-5 & -1\end{pmatrix}\\

M_{2}=(A_{1,1}-A_{2,2})\cdot(B_{1,1}-B_{2,2})=\begin{pmatrix}-3 & 6\\-1 & -3\end{pmatrix}\cdot\begin{pmatrix}-2 & -4\\-2 & -3\end{pmatrix}=\begin{pmatrix}-6 & -6\\8 & 13\end{pmatrix}\\

M_{3}=(A_{1,1}-A_{2,1})\cdot(B_{1,1}-B_{1,2})=\begin{pmatrix}-1 & 5\\-1 & -4\end{pmatrix}\cdot\begin{pmatrix}-1 & -1\\1 & -8\end{pmatrix}=\begin{pmatrix}6 & -39\\-3 & 33\end{pmatrix}\\

M_{4}=(A_{1,1}-A_{1,2})\cdot B_{2,2}=\begin{pmatrix}-6 & 1\\-2 & -2\end{pmatrix}\cdot B_{2,2}=\begin{pmatrix}-43 & -44\\-26 & -24\end{pmatrix}\\

M_{5}=A_{1,1}\cdot(B_{1,2}-B_{2,2})=A_{1,1}\cdot\begin{pmatrix}-1 & -3\\-3 & 5\end{pmatrix}=\begin{pmatrix}-27 & 31\\-12 & -8\end{pmatrix}\\
M_{6}=A_{2,2}\cdot(B_{2,1}-B_{1,2})=\begin{pmatrix}\end{pmatrix}\cdot\begin{pmatrix}\end{pmatrix}=\begin{pmatrix}\end{pmatrix}\\

M_{7}=(A_{2,1}-A_{2,2})\cdot B_{1,1}=\begin{pmatrix}\end{pmatrix}\cdot\begin{pmatrix}\end{pmatrix}=\begin{pmatrix}\end{pmatrix}
</math>
<math>A_{1,1}=\begin{bmatrix}3 & 8\\6 & 2\end{bmatrix}\text{, } A_{1,2}=\begin{bmatrix}9 & 7\\8 & 4\end{bmatrix}\text{, } A_{2,1}=\begin{bmatrix}4 & 3\\7 & 6\end{bmatrix}\text{, } A_{2,2}=\begin{bmatrix}6 & 2\\7 & 5\end{bmatrix}\\
B_{1,1}=\begin{bmatrix}6 & 4\\3 & 1\end{bmatrix}\text{, } B_{1,2}=\begin{bmatrix}7 & 5\\2 & 9\end{bmatrix}\text{, } B_{2,1}=\begin{bmatrix}7 & 6\\9 & 3\end{bmatrix}\text{, } B_{2,2}=\begin{bmatrix}8 & 8\\5 & 4\end{bmatrix}\\</math>

Danach kann man die 4 Teilmatrizen von <math>C</math> durch Addition bzw. Subtraktion berechnen.


<math>
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
</math>