\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{3}
\newcommand{\ABGABEDATUM}{bis zum 11. November 2016, 12 Uhr, in den
Briefkasten neben Raum 111}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik}\hfill WiSe 2016/17 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Boris Klemz

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Schnelle Matrizenmultiplikation} {10 Punkte}

Die Multiplikation zweier $n \times n$ Matrizen ist eine fundamentale
Operation, die nicht nur in numerischen Anwendungen st\"andig ben\"otigt
wird. In dieser Aufgabe werden wir eine Methode kennen lernen, die
\"ahnlich zu Karatsubas Algorithmus die Schulmethode mit Hilfe einer
magischen Rekursion verbessert.
\begin{enumerate}
  \item Erkl\"aren Sie in einem Satz, wie viele Additionen und 
     Multiplikationen asymptotisch n\"otig sind, um
     zwei $n \times n$ Matrizen mit dem Schulalgorithmus zu multiplizieren.

  \item
Volker Strassen hat einen Algorithmus zur
schnelleren Matrizenmultiplikation entwickelt. 
Er funktioniert wie folgt (der Einfachheit halber nehmen wir an,
dass $n$ eine Zweierpotenz ist).

Die Grundidee ist, dass $2\times 2$-Matrizen mit 7 statt 8 
Skalarmultiplikationen multipliziert werden k\"onnen: 

Gegeben seien zwei Matrizen 
$A:=\left(\begin{array}{cc} a & b \\ c& d \end{array}\right)$ und 
$B:=\left(\begin{array}{cc} e & g \\ f& h \end{array}\right)$. 

Ziel ist, das Produkt 
\[
\left(\begin{array}{cc} a & b \\ c& d \end{array}\right)\cdot
\left(\begin{array}{cc} e & g \\ f& h \end{array}\right) =
\left(\begin{array}{cc} r & s \\ t& u \end{array}\right)
\]
von $A$ und $B$, also $r$, $s$, $t$ und $u$, mit nur 7 Skalarmultiplikationen 
zu bestimmen. Dazu betrachtet man die sieben Produkte
\begin{align*}
P_1 &:=  a\cdot(g-h);\\
P_2 &:=  (a+b)\cdot h;\\
P_3 &:=  (c+d)\cdot e;\\
P_4 &:=  d\cdot(f-e); \\
P_5 &:=  (a+d)\cdot(e+h);\\
P_6 &:=  (b-d)\cdot(f+h); \text{ und}\\
P_7 &:=  (a-c)\cdot(e+g).
\end{align*}
Dann gilt
\begin{align*}
r & = P_5+P_4-P_2+P_6;\\
s & =  P_1+P_2;\\
t & =  P_3+P_4; \text{ und} \\
u & =  P_5+P_1-P_3-P_7.
\end{align*}
Analog kann man $n\times n$-Matrizen in vier $\frac{n}{2}\times\frac{n}{2}$-Matrizen 
unterteilen und die entsprechenden Untermatrizen berechnen. 
Strassens Algorithmus arbeitet also wie folgt:
\\[2ex]
\textbf{Eingabe}: Zwei $n\times n$-Matrizen $A$ und $B$.
\\
\textbf{Ausgabe}: Die Matrix $C:=A\cdot B$.
%\\
\begin{enumerate}
\item Teile $A$ und $B$ in $(n/2)\times (n/2)$-Matrizen, 
berechne mit Addition und Subtraktion die zu multiplizierenden Matrizen
(also alle Faktoren, die in den Produkten $P_1,\dots,P_7$ vorkommen).
\item F\"uhre 7 Multiplikationen von $(n/2)\times(n/2)$-Matrizen aus.
\item Berechne $C$ durch geeignete Additionen bzw.~Subtraktionen der Matrizen
\\ 
$P_1,\dots,P_7$.
\end{enumerate}
Begr\"unden Sie, warum der Algorithmus korrekt ist (Achtung: Matrizenmultiplikation
ist nicht kommutativ).

\item
Beschreiben Sie die Laufzeit von Strassens Algorithmus mit einer 
Rekursionsgleichung und l\"osen Sie diese.  
\end{enumerate}
%
\AUFGABE{Rekursionsgleichungen} {10 Punkte}

Geben Sie m{\"o}glichst gute asymptotische Schranken f{\"u}r 
die folgenden rekursiv definierten Funktionen $T(n)$ an; 
dabei ist $T(n) \in \Theta(1)$ f{\"u}r $n \le 2$.
\begin{enumerate}
  \item $T(n) = T(9n/10)+n$;
  \item $T(n) = T(n-a)+T(a)+n$, f{\"u}r ein festes $a \ge 1$ und 
      alle $n > a$. Es sei $T(n) = O(1)$ f\"ur $n \leq a$;
  \item $T(n) = T(\sqrt{n})+1$;
  \item $T(n) = 2T(n/4)+\sqrt{n}$;
  \item $T(n) = 7T(n/3)+n^{2}$;
  \item $T(n) = 2T(n/2)+n \log{} n$; und
  \item $T(n) = T(n-1)+1/n$.
%  \item $T(n) = \sqrt{n}T(\sqrt{n})+n$
\end{enumerate}
%

%\hskip12cm \emph{Bitte wenden}


\AUFGABE {Implementierung}{10 Punkte}

\begin{enumerate}
  \item Implementieren Sie Karatsubas Algorithmus sowie die Schulmethode 
     zur Multiplikation ganzer Zahlen in Java.
     Vergleichen Sie die beiden Algorithmen
     experimentell. Ab welcher Eingabegr\"o\ss{}e ist Karatsuba besser?
  \item (\emph{freiwillig, 5 Zusatzpunkte})
    Entwickeln Sie eine hybride Implementierung, die bei kleineren
    Zahlen von Karatsuba auf die Schulmethode umschaltet.
    Bestimmen
    Sie experimentell den g\"unstigsten Umschaltpunkt.
\end{enumerate}

\end{description}
\end{document}
