\documentstyle[12pt,A4,german]{article}
\begin{document}
\Large
\begin{center}
Drei {\em divide-and-conquer} Algorithmen
\end{center}

\section{{\sc Karatsuba}-Multiplikation von 
Polynomen
\newline
(und von ganzen Zahlen)}

Die Multiplikation zweier Polynome
\[
f(x) = \sum_{i=0}^{2n-1} f_i \, x^i~~,~~
g(x) = \sum_{j=0}^{2n-1} g_j \, x^j
\]
vom Grad $\deg f, \deg g < 2n$ wird zur"uckgef"uhrt auf
die drei Multiplikationen von Polynomen, deren Grad $< n$ ist:
\begin{eqnarray*}
f(x) &=& a(x) + x^n \, b(x) \\
g(x) &=& c(x) + x^n \, d(x) \\
f(x)g(x) &=&
a(x)c(x) + x^n 
\left( a(x)d(x)+b(x)c(x) \right) + 
x^{2n} b(x)d(x) \\
&=& 
u(x) + x^n \left(w(x) -u(x)-v(x) \right) + x^{2n} v(x) 
\end{eqnarray*}
wobei
\begin{eqnarray*}
u(x) &:=& a(x)c(x) \\
v(x) &:=& b(x)d(x) \\
w(x) &:=& (a(x)+b(x))(c(x)+d(x))
\end{eqnarray*}
F"ur die {\em rekursive} Anwendung dieser Idee 
im Maple-Programm {\em karatsuba} wird
angenommen, da"s $n$ eine Potenz von $2$
ist, d.h. $\deg f , \deg g < 2^m$. 
Der Parameter $m$ wird im rekursiven Programm mitgef"uhrt.
Startet man mit beliebigen input-Polynomen, so wird 
in {\em kara\_mult} das
kleinste $m$ bestimmt, soda"s diese Annahmen zutreffen.

Idee und Programm sind auf Multiplikation von ganzen Zahlen
zu "ubertragen.

\newpage

\begin{verbatim}
karatsuba := proc(f,g,x,m)
local a,b,c,d,u,v,w,deg;
if m=0 then RETURN(f*g) fi;
deg := 2^(m-1);
a := sum('coeff(f,x,i)*x^i','i'=0..deg-1);
b := sum('coeff(f,x,i+deg)*x^i','i'=0..deg-1);
c := sum('coeff(g,x,i)*x^i','i'=0..deg-1);
d := sum('coeff(g,x,i+deg)*x^i','i'=0..deg-1);
u := karatsuba(a,c,x,m-1);
v := karatsuba(b,d,x,m-1);
w := karatsuba(a+b,c+d,x,m-1);
RETURN(expand(u+(w-u-v)*x^deg+v*x^(2*deg)));
end;

kara_mult := proc(f,g,var)
local df,dg,bound;
df := degree(f,var);
dg := degree(g,var);
bound := ceil(simplify(log[2](max(df,dg)+1)));
karatsuba(f,g,var,bound);
end;
\end{verbatim}

Komplexit"atsanalyse (f"ur $n = 2^m$): 
\[
t(n) := 
\left\{\parbox{12cm}{Anzahl der Additionen und Multiplikationen
im Koeffizientenbereich bei input-Grad $< n$}\right.
\]
\bigskip
\[
t(2n) = 3 \cdot t(n) + \Theta(n)~~,~~t(1) = \Theta(1)
\]
\bigskip
\[
\Rightarrow  \fbox{
$t(n) \in \Theta(n^{\log_2 3})$}
\]

\newpage

\section{Sortieren durch Verschmelzen: {\em mergesort}}

\bigskip
\bigskip
Die Idee von {\em mergesort} ist einfach: ist eine Liste
$A[1..n]$ der L"ange $n$ zu sortieren, so zerlegt man
diese in Teillisten $B := A[1..\lfloor n/2 \rfloor]$
und $C := A[\lfloor n/2 \rfloor+1 .. n]$, sortiert die beiden
separat (durch {\em rekursive} Anwendung eben dieser Idee)
und produziert durch ``Verschmelzen'' ({\em merging}) beider Listen
das Resultat. Das {\em merging} ist ein einfacher Vorgang,
bei dem aus den aktuellen Resten der beiden sortierten Teillisten
das jeweils kleinste Element durch einen Vergleich gefunden,
entfernt und in die Resultatsliste geschrieben wird. 
Das Maple-Programm {\em merge} ist der "Ubersichtlichkeit wegen
rekursiv geschrieben.
\bigskip
\begin{verbatim}

merge := proc(A:list(integer),B:list(integer))
local a,b;
a := nops(A);
b := nops(B);
if a=0 then RETURN(B) fi;
if b=0 then RETURN(A) fi;
if op(1,A) <= op(1,B) then
RETURN([op(1,A),op(merge([op(2..a,A)],B))])
else
RETURN([op(1,B),op(merge(A,[op(2..b,B)]))])
fi;
end;
\end{verbatim}

\newpage

\begin{verbatim}
mergesort := proc(A:list(integer))
local B,C,length,half;
length := nops(A);
half := floor(length/2);
if length < 2 then RETURN(A) else
B := [op(1..half,A)];
C := [op(half+1..length,A)];
RETURN(merge(mergesort(B),mergesort(C)));
fi;
end;

\end{verbatim}

\framebox{\parbox{15cm}{
{\em mergesort} reduziert das Sortierproblem f"ur eine Liste
der L"ange $n$ auf zwei Sortierprobleme (etwa) halber
Gr"o"se und linearen Zusatzaufwand f"ur Verschmelzen
und overhead}}

\vskip1cm

Komplexit"atsanalyse (f"ur $n = 2^m$):
\[
t(2n) := 
\left\{\parbox{12cm}{Anzahl der Vergleichsoperationen
+ overhead f"ur Listen der L"ange $ n$}\right.
\]
\bigskip
\[
t(2n) = 2 \cdot t(n) + \Theta(n) ~~,~~t(1) = \Theta(1)
\]
\bigskip
\[
\Rightarrow  \fbox{
$t(n) \in \Theta(n \, {\log_2 n})$}
\]
 

\newpage
\section{{\sc Strassen}s Matrix-Multiplikation}

Ausgangspunkt: die Multiplikation von zwei
$(2 \times 2)$-Matrizen ("uber irgendeinem (!) Ring)
l"a"st sich mit 7 Multiplikationen 
im Koeffizientenbereich ausf"uhren
---
statt mit 8 Multiplikationen nach ``Schulmethode'':
\begin{eqnarray*}
\pmatrix{
a_{11} & a_{12} \cr
a_{21} & a_{22} }
\pmatrix{
b_{11} & b_{12} \cr
b_{21} & b_{22} }
&=&
\pmatrix{
a_{11} b_{11} + a_{12} b_{21} &
a_{11} b_{12} + a_{12} b_{22} \cr
a_{21} b_{11} + a_{22} b_{21} &
a_{21} b_{12} + a_{22} b_{22}} \\
&=&
\pmatrix{
d_{11} & d_{12} \cr
d_{21} & d_{22}}
\end{eqnarray*}
Man berechnet zun"achst 7 Produkte
\begin{eqnarray*}
c_1 &=& (a_{12} - a_{22}) (b_{21} + b_{22}) \\
c_2 &=& (a_{11} + a_{22}) (b_{11} + b_{22}) \\
c_3 &=& (a_{11} - a_{21}) (b_{11} + b_{12}) \\
c_4 &=& (a_{11} + a_{12}) \,b_{22} \\
c_5 &=& a_{11} \,(b_{12} - b_{22}) \\
c_6 &=& a_{22} \,(b_{21} - b_{11}) \\
c_7 &=& (a_{21} + a_{22})\, b_{11}
\end{eqnarray*}
und danach die $d_{11} , \ldots , d_{22}$ durch
\[
\begin{array}{ll}
d_{11} = c_1+c_2-c_4+c_6 &
d_{12} = c_4 + c_5 \\
d_{21} = c_6 + c_7 &
d_{22} = c_2 - c_3 + c_5 - c_7
\end{array}
\]

Der Witz der (rekursiven) Angelegenheit: die 
Koeffizienten $a_{ij}, b_{i,j}, \ldots$ k"onnen selbst wieder
Matrizen sein, d.h. 

\bigskip
\noindent
\framebox{\parbox{15cm}{Reduktion einer Matrixmultiplikation
f"ur zwei $(2n \times 2n)$-Matrizen auf 7 Matrixmultiplikationen
von $(n \times n)$-Matrizen, dazu 18 Additionen/Subtraktionen
von $(n \times n)$-Matrizen}}

\newpage

\begin{verbatim}
strassen := proc(A:matrix,B:matrix,m)
local dim,A11,A12,A21,A22,
          B11,B12,B21,B22,
          C1,C2,C3,C4,C5,C6,C7,
          D11,D12,D21,D22;
if m=0 then RETURN(evalm(A&*B)) fi;
dim := 2^(m-1);
A11 := submatrix(A,1..dim,1..dim);
A12 := submatrix(A,1..dim,dim+1..2*dim);
A21 := submatrix(A,dim+1..2*dim,1..dim);
A22 := submatrix(A,dim+1..2*dim,dim+1..2*dim);
B11 := submatrix(B,1..dim,1..dim);
B12 := submatrix(B,1..dim,dim+1..2*dim);
B21 := submatrix(B,dim+1..2*dim,1..dim);
B22 := submatrix(B,dim+1..2*dim,dim+1..2*dim);
C1 := strassen(evalm(A12-A22),evalm(B21+B22),m-1);
C2 := strassen(evalm(A11+A22),evalm(B11+B22),m-1);
C3 := strassen(evalm(A11-A21),evalm(B11+B12),m-1);
C4 := strassen(evalm(A11+A12),B22,m-1);
C5 := strassen(A11,evalm(B12-B22),m-1);
C6 := strassen(A22,evalm(B21-B11),m-1);
C7 := strassen(evalm(A21+A22),B11,m-1);
D11 := evalm(C1+C2-C4+C6);
D12 := evalm(C4+C5);
D21 := evalm(C6+C7);
D22 := evalm(C2-C3+C5-C7);
RETURN(stack(concat(D11,D12),concat(D21,D22)));
end;
\end{verbatim}
\newpage
Komplexit"atsanalyse (f"ur $n = 2^m$):
\[
t(n) := 
\left\{\parbox{12cm}{Anzahl der arithmetischen
Operationen im Koeffizientenbereich
f"ur die Multiplikation von zwei $(n \times n)$-Matrizen}\right.
\]
\bigskip
\[
t(2n) = 7 \cdot t(n) + 18 \cdot n^2 ~~,~~t(1) = 1
\]
\bigskip
\[
\Rightarrow  \fbox{
$t(n) \in \Theta(n^{\log_2 7})$
}
\]
\bigskip

Beachte: $\log_2 7 = 2.81 \ldots$ !

Siehe Kapitel 31.2 in {\sc Cormen/Leiserson/Rivest} f"ur
einen Rekonstruktionsversuch der {\sc Strassen}schen Idee.

\end{document}