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

\newcommand{\ZETTELNUMMER}{4}
\newcommand{\ABGABEDATUM}{bis zum 18. 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{Varianten der Vorlesungsbeispiele} {10 Punkte}

\begin{enumerate}
 \item
    Betrachten Sie die Variante des Einkaufsproblems, bei dem von
    jedem Artikel beliebig viele Exemplare zur Verf\"ugung stehen.
    Das hei\ss{}t, wir haben Artikel $1$ bis $n$ gegeben und jeder
    Artikel hat einen Preis $p_i$ und einen Wert $w_i$. Wir haben ein
    Budget $B$ und m\"ochten eine \emph{Multimenge} von Artikeln
    finden, die unser Budget beachtet und den Wert maximiert. 

    Zeigen Sie, wie man auch diese Variante des Einkaufsproblems 
    in Zeit $O(nB)$ l\"osen kann.
 \item 
   In der Vorlesung haben Sie gesehen, wie das Rundreiseproblem
   mit Hilfe von dynamischem Programmieren gel\"ost werden kann. Arbeiten
   Sie die Details des Algorithmus aus und geben Sie Pseudocode an, um
   eine optimale Tour zu berechnen.
\end{enumerate}

\AUFGABE {Matrizenkettenmultiplikation}{10 Punkte}

F\"ur eine gegebene Folge $M_1$, $M_2$, $\ldots$, $M_n$  von
$n$ Matrizen ist das \emph{Matrizenkettenprodukt} 
$M_1 \cdot M_2 \cdot \cdots \cdot M_n$ zu berechnen.
Die Matrizen haben dabei verschiedene Dimensionen.
$M_1$ ist eine $p_1 \times p_2$ Matrix, $M_2$ ist eine $p_2 \times p_3$
Matrix, usw. 

Um eine $a \times b$ Matrix mit einer $b \times c$ Matrix 
(naiv) zu multiplizieren, ben\"otigen wir bekanntlich $acb$ 
Multiplikationen und $ac(b-1)$ Additionen, also
insgesamt $ac(2b-1)$ elementare Operationen.
Daraus folgt, dass es einen Unterschied macht, wie
man das Matrizenprodukt klammert, also in welcher
Reihenfolge man die Matrizen multipliziert.

Sei beispielsweise $M_1$ eine $100 \times 200$ Matrix, $M_2$ eine
$200 \times 10$ Matrix und $M_3$ eine $10 \times 1$ Matrix. Dann
haben wir zwei M\"oglichkeiten, die Multiplikation durchzuf\"uhren:
$(M_1 M_2) M_3$ oder $M_1(M_2 M_3)$. Im ersten Fall ben\"otigen
wir zun\"achst $100 \cdot 10 \cdot (400-1) = 399.000$ Operationen, um 
die $100 \times 10$ Matrix $M_1 M_2$ zu berechnen, und dann 
$100 \cdot 1 \cdot (20-1) = 1.900$ Operationen, um das Ergebnis zu erhalten.
Insgesamt ergibt das $400.900$ Operationen. Im zweiten Fall brauchen wir
erst $200 \cdot 1 \cdot (20-1) = 3.800$ Operationen f\"ur die
$200 \times 1$ Matrix $M_2 M_3$ und dann
$100 \times 1 \times (400-1) = 39.900$ Operationen f\"ur das Ergebnis.
Insgesamt sind es hier $43.700$ Operationen. Die zweite Klammerung
ist also fast zehnmal so schnell wie die erste. Ziel dieser Aufgabe
ist es, eine optimale Klammerung f\"ur eine Matrizenkettenmultiplikation
zu bestimmen.

\begin{enumerate}
  \item Bezeichne mit P$[i,j]$ die Kosten f\"ur eine optimale Klammerung
     des Matrizenkettenprodukts 
     $M_i \cdot \cdots \cdot M_j$ ($1 \leq i \leq j \leq n$).
     Unser Ziel ist, P$[1,n]$ zu berechnen. Finden Sie eine
     geeignete Rekursionsgleichung f\"ur P$[i,j]$.
  \item Benutzen Sie Ihre Rekursion, um Pseudocode f\"ur einen
     Algorithmus anzugeben, welcher die optimalen Kosten P$[1,n]$
     bestimmt. Analysieren Sie Laufzeit und Platzbedarf.
  \item Erweitern Sie Ihren Algorithmus so, dass er auch eine
    optimale Klammerung ausgibt.
  \item (\emph{freiwillig, 5 Zusatzpunkte}) Implementieren Sie ein
     Programm, das eine optimale Klammerung f\"ur eine 
     gegebene Matrizenkettenmultiplikation bestimmt und die 
     Multiplikation durchf\"uhrt. Vergleichen Sie Ihr Programm
     mit einer naiven Implementierung, welche die Matrizen von
     links nach rechts multipliziert.
\end{enumerate}

\AUFGABE {Versteckte Markov-Modelle}{10 Punkte}


\begin{enumerate}
\item
  Betrachten Sie das folgende versteckte Markov-Modell.

  \begin{itemize}
    \item Zust\"ande: $Q = \{q, r, s\}$.
    \item Alphabet: $\Sigma = \{a, b\}$.
    \item  Anfangsverteilung: $\{q : 0.1$, $r: 0.4$, $s: 0.5\}$.
    \item Ausgabeverteilung f\"ur $q$: $\{a: 0.2$, $b: 0.8\}$.
    \item Ausgabeverteilung f\"ur $r$: $\{a: 0.7$, $b: 0.3\}$.
    \item Ausgabeverteilung f\"ur $s$: $\{a: 0.5$, $b: 0.5\}$.
    \item \"Ubergangsverteilung f\"ur $q$: $\{q: 0.8$, $r: 0.1$, $s : 0.1\}$.
    \item \"Ubergangsverteilung f\"ur $r$: $\{q: 0.3$, $r: 0.3$, $s : 0.4\}$.
    \item \"Ubergangsverteilung f\"ur $s$: $\{q: 0.2$, $r: 0.4$, $s : 0.4\}$.
  \end{itemize}
  Benutzen Sie den Viterbi-Algorithmus, um die wahrscheinlichste
  Erkl\"arung f\"ur die Ausgabefolge \emph{abba} zu ermitteln.
\item
  Bei einer Implementierung des Viterbi-Algorithmus rechnet man oft
  mit den Werten $\log p_i$ statt den Wahrscheinlichkeiten 
  $p_i$. Erkl\"aren Sie, warum das eine gute Idee ist.
\item 
  Eine Anwendung von versteckten Markov-Modellen ist die
  Fehlerkorrektur. Wir wollen uns an einem Beispiel 
  \"uberlegen, wie dies prinzipiell funktionieren kann.

  Angenommen, wir m\"ochten einen
  deutschsprachigen Text \"uber dem Alphabet 
  $\{a, b, c,\ldots, z, '\,\,'\}$ \"uber eine gest\"orte Leitung
  \"ubermitteln ($'\,\,'$ stellt das Leerzeichen dar, 
  der Einfachheit halber werden Satzzeichen ignoriert).
  Wir wissen, dass die Leitung ungef\"ahr 10 Prozent der \"ubertragenen 
  Zeichen zuf\"allig
  \"andert. Trotzdem m\"ochten wir aus der empfangenen Nachricht
  einen m\"oglichst korrekten Text rekonstruieren.

  Beschreiben Sie, wie man diese Situation mit Hilfe eines 
  versteckten Markov-Modells modellieren kann. Was sind die Zust\"ande?
  Wie k\"onnte man die zugrunde liegenden Verteilungen sinnvoll ermitteln?
  Welche Annahmen werden in dem Modell gemacht? Inwiefern treffen diese
  Annahmen in der Wirklichkeit zu?
\end{enumerate}



\end{description}
\end{document}
