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 ==
<language>Scheme</language>
<language>Scheme</language>
===Binäre Suche===
Die Korrigierte Datei der Binären Suche:
<document>Simabrzo_Richtig-bin-suche.zip</document>

Übung 2 der Binären suche:
Der Quellcode einer Binären Suche:
<code>
(define bin-suche
  (lambda (ls wert)
    (call-with-values
     (lambda ()(teilliste2 ls))
     (lambda (lls rls)
       (cond
         [(null? rls) "Element nicht enthalten."]
         [(= wert (car rls)) "Element enthalten."]
         [(< wert (car rls))
          (if (null? lls)
              "Element nicht enthalten."
              (bin-suche lls wert))]
         [else
          (if (null? (cdr rls))
              "Element enthalten."
              (bin-suche ls wert))])))))

(define teilliste2
  (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)))))

(define mergesort
  (lambda (ls)
    (if (or (null? ls)(null? (cdr ls)))
        ls
        (call-with-values
         (lambda () (teilliste2 ls))
         (lambda (ls1 ls2)
           (verbinden
            (mergesort ls1)
            (mergesort ls)))))))

(define verbinden
  (lambda (lls rls)
    (cond
      [(null? lls) rls]
      [(null? rls) lls]
      [else
       (let ((x (car lls))(y (car rls)))
         (if (< x y)
             (cons x (verbinden (cdr lls) rls))
             (cons y (verbinden lls (cdr rls)))))])))

</code>

<eval>
(define d '(1 8 10 21 23 29 41 59 81 90 234 3333))

(bin-suche d 90)
</eval>

===Multiplikation großer ganzer Zahlen nach KARATSUBA und OFMAN===
*<math>3812 \cdot 3264</math>

<math>a=3802\Rightarrow a_1=38 \textrm{ und }a_0=12\\
b=3264\Rightarrow b_1=32 \textrm{ und }b_0=64</math>

Damit berechnet man <math>r</math>, <math>s</math>und <math>t</math>:

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

*<math>837147 \cdot 479253</math>

<math>a=837147\Rightarrow a_1=837 \textrm{ und }a_0=147\\
b=479253\Rightarrow b_1=479 \textrm{ und }b_0=253</math>

Damit berechnet man <math>r</math>, <math>s</math>und <math>t</math>:

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

*<math>34 \cdot 56</math>

<math>a=34\Rightarrow a_1=3 \textrm{ und }a_0=6\\
b=56\Rightarrow b_1=5 \textrm{ und }b_0=6</math>

Damit berechnet man <math>r</math>, <math>s</math>und <math>t</math>:

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

===Schnelle Matrixmultiplikation nach STRASSEN===
Gegeben sind die zwei Matrizen <math>A</math> und <math>B</math> mit:

<math>
A=\begin{pmatrix}
3 & 4 & 8 & 9\\
1 & 5 & 9 & 2\\
5 & 7 & 4 & 3\\
2 & 3 & 8 & 1
\end{pmatrix}</math> und 
<math>B=\begin{pmatrix}
3 & 2 & 8 & 6\\
1 & 4 & 9 & 5\\
7 & 6 & 4 & 3\\
2 & 9 & 2 & 3
\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 & 4\\1 & 5\end{bmatrix}\text{, } A_{1,2}=\begin{bmatrix}8 & 7\\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}
</math>

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


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


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


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

Durch Zusammensetzen der Teilmatrizen zur Ergebnismatrix <math>C</math> ergibt sich das Ergebnis der Rechnung:

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