Aufgaben Lösung

Aus ProgrammingWiki

< AuK | Teile und Herrsche 2 SS10

Wechseln zu: Navigation, Suche

Diese Seite hält die Lösungen der Aufgaben auf der Seite AuK/Teile und Herrsche 2 SS10/Aufgaben bereit.

Inhaltsverzeichnis

1 Lösungen zu den Übungsaufgaben

Lösungen zu den Übungsaufgaben

Binäre Suche

Die Korrigierte Datei der Binären Suche Übung 1 Binäre Suche: Oder Schlicht in der Aufgaben Datei (tipp-l4) eingeben...

Simabrzo_Richtig-bin-suche.zip (0.1 MB)

Übung 2 der Binären suche:

Multiplikation großer ganzer Zahlen nach KARATSUBA und OFMAN

Hier die Maxima-Datei:

Fdeutschmann_Karatsuba.zip (0.1 MB)

$3812 \cdot 3264$

$a=3812\Rightarrow a_1=38 \textrm{ und }a_0=12\\ b=3264\Rightarrow b_1=32 \textrm{ und }b_0=64$

Damit berechnet man $r$ , $s$ und $t$ :

$r=a_{1}\cdot b_{1}=38\cdot32=1216\\ s=(a_{0}-a_{1})\cdot(b_{0}-b_{1})=-832\\ t=a_{0}\cdot b_{0}=768\\ \\ a\cdot b = r\cdot z^{n}+(r+t-s)z^{\frac{n}{2}}+t=1216\cdot10^4+(1216+768+832)\cdot10^2+768=\underline{\underline{12442368}}$

$837147 \cdot 479253$

$a=837147\Rightarrow a_1=837 \textrm{ und }a_0=147\\ b=479253\Rightarrow b_1=479 \textrm{ und }b_0=253$

Damit berechnet man $r$ , $s$ und $t$ :

$r=a_{1}\cdot b_{1}=837\cdot479=400923\\ s=(a_{0}-a_{1})\cdot(b_{0}-b_{1})=(147-837)\cdot(253-479)=155940\\ t=a_{0}\cdot b_{0}=147\cdot253=37191\\ \\ a\cdot b = r\cdot z^{n}+(r+t-s)z^{\frac{n}{2}}+t=400923\cdot10^6+(400923+37191-155940)\cdot10^3+37191=\underline{\underline{401205211191}}$

$34 \cdot 56$

$a=34\Rightarrow a_1=3 \textrm{ und }a_0=6\\ b=56\Rightarrow b_1=5 \textrm{ und }b_0=6$

Damit berechnet man $r$ , $s$ und $t$ :

$r=a_{1}\cdot b_{1}=3\cdot5=15\\ s=(a_{0}-a_{1})\cdot(b_{0}-b_{1})=(4-3)\cdot(6-5)=1\\ t=a_{0}\cdot b_{0}=4\cdot6=24\\ \\ a\cdot b = r\cdot z^{n}+(r+t-s)z^{\frac{n}{2}}+t=15\cdot10^2+(15+24-1)\cdot10^1+24=\underline{\underline{1904}}$

Schnelle Matrixmultiplikation nach STRASSEN

Hier die Maxima-Datei:

Fdeutschmann_Strassen.zip (0.1 MB)

Gegeben sind die zwei Matrizen $A$ und $B$ mit:

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

Die Matrizen zerlegt man nach folgendem Muster in Teilmatrizen:

$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}$

Daraus ergeben sich die 8 Teilmatrizen:

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

Damit lassen sich $M_{1}$ bis $M_{7}$ berechnen:

$M_{1}=(A_{1,1}+A_{2,2})\cdot(B_{1,1}+B_{2,2})=\begin{pmatrix}70 & 84\\81 & 87\end{pmatrix}\\ M_{2}=(A_{2,1}+A_{2,2})\cdot B_{1,1}=\begin{pmatrix}37 & 58\\34 & 36\end{pmatrix}\\ M_{3}=A_{1,1}\cdot(B_{1,2}-B_{2,2})=\begin{pmatrix}40 & 17\\39 & 13\end{pmatrix}\\ M_{4}=A_{2,2})\cdot (B_{2,1}-B_{1,1})=\begin{pmatrix}19 & 31\\33 & 37\end{pmatrix}\\ M_{5}=(A_{1,1}+A_{1,2})\cdot B_{2,2}=\begin{pmatrix}66 & 66\\54 & 51\end{pmatrix}\\ M_{6}=(A_{2,1}-A_{1,1})\cdot(B_{1,1}+B_{1,2})=\begin{pmatrix}52 & 43\\-9 & -10\end{pmatrix}\\ M_{7}=(A_{1,2}-A_{2,2})\cdot(B_{2,1}+B_{2,2}=\begin{pmatrix}60 & 84\\15 & 21\end{pmatrix})$

Danach kann man die 4 Teilmatrizen von $C$ durch Addition bzw. Subtraktion berechnen.

$C_{1,1}=M_1 + M_4 - M_5 + M_7=\begin{pmatrix}83 & 133\\75 & 94\end{pmatrix}\\ C_{1,2}=M_3 + M_5=\begin{pmatrix}106 & 83\\93 & 64\end{pmatrix}\\ C_{2,1}=M_2 + M_4=\begin{pmatrix}56 & 89\\67 & 73\end{pmatrix}\\ C_{2,2}=M_1 - M_2 + M_3 + M_6=\begin{pmatrix}125 & 86\\77 & 54\end{pmatrix}$

Durch Zusammensetzen der Teilmatrizen zur Ergebnismatrix $C$ ergibt sich das Ergebnis der Rechnung:

$C=\begin{pmatrix}C_{1,1} & C_{1,2}\\C_{2,1} & C_{2,2}\end{pmatrix}= \underline{\underline{\begin{pmatrix} 83 & 133 & 106 & 83\\ 75 & 94 & 93 & 64\\ 56 & 89 & 125 & 86\\ 67 & 73 & 77 & 54 \end{pmatrix}}}$

Aufgaben Lösung

Aus ProgrammingWiki

Inhaltsverzeichnis

Lösungen zu den Übungsaufgaben

Binäre Suche

Multiplikation großer ganzer Zahlen nach KARATSUBA und OFMAN

Schnelle Matrixmultiplikation nach STRASSEN

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge