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

\newcommand{\ZETTELNUMMER}{2}
\newcommand{\ABGABEDATUM}{am 29. April 2014 vor der Vorlesung in die
Mitarbeiterschachteln}

\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 \hfill SoSe 2014

\smallskip
\noindent
\large
\textbf{Ausgewählte Themen der Algorithmik: Datenstrukturen}\\[0.5ex]
\normalsize
Wolfgang Mulzer, Claudia Dieckmann, Yannik Stein
\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}
\AUFGABE{Move-To-Root-Heuristik}{10 Punkte}

Eine plausible Alternative zu Splay-B\"aumen besteht darin,
die Operation $\texttt{splay}(x)$ durch eine Operation
$\texttt{moveToRoot}(x)$ zu ersetzen, welche den Knoten
$x$ durch wiederholte Links- bzw.~Rechtsrotationen an
die Wurzel bef\"ordert. Der resultierende Algorithmus
wird als \emph{MTR-Heuristik} bezeichnet.

Wie unterscheidet sich die MTR-Heuristik von Splay-B\"aumen?
Zeigen Sie durch eine explizite Konstruktion, dass die MTR-Heuristik im worst-case 
amortisierte Laufzeit $\Omega(n)$ aufweisen kann. Dabei ist
$n$ die Anzahl der Elemente im Suchbaum.

\AUFGABE{Analyse von Splayb\"aumen}{10 Punkte}

\begin{enumerate}
  \item Beweisen Sie: Seien $a, b > 0$ und $c \geq a+b$. Dann ist
    \[
      \log a + \log b \leq 2 \log c - 2.
    \]
  \item Nehmen Sie an, ein Splaybaum enth\"alt die Elemente $1, \dots, n$ und
    bearbeitet eine Folge $A = a_1, \dots, a_m$ von $m$ Suchanfragen, mit $a_i \in \{1 \dots, n\}$.
    Beweisen Sie den \emph{Satz vom statischen Finger}: Sei $f \in \{1, \dots, n\}$ fest.
    Dann ist die Gesamtzeitlaufzeit f\"ur die Folge $A$ 
    \[
      O(n \log n + m + \sum_{i=1}^{m}\log (|a_j - f| + 1)).
    \]
    Interpretieren Sie den Satz.

    \emph{Hinweis}: Verwenden Sie das Access-Lemma mit $w(x) = (|x - f| + 1)^{-2}$.
\end{enumerate}

\AUFGABE{Statische Optimalit\"at---Untere Schranke}{10 Punkte}

Sei $\Sigma$ ein Alphabet und sei $C: \Sigma \rightarrow \{0, 1\}^+$ ein
pr\"afixfreier Code f\"ur $\Sigma$ (d.h., kein Codewort ist Pr\"afix eines
anderen Codeworts in $\Sigma$).
Sei $X$ eine Zufallsvariable mit Werten aus $\Sigma$.
Der \emph{Codierungssatz von Shannon} besagt unter anderem, dass 
\[
  \text{E}[|C(X)|] \geq H(X)
\]
ist, wobei 
\[
  H(X) = \sum_{\sigma \in \Sigma} \Pr[X = \sigma] \log \frac{1}{\Pr[X = \sigma]}
\]
die (bin\"are) \emph{Entropie} von $X$ bezeichnet.

Benutzen Sie den Codierungssatz von Shannon, um die folgende Aussage zu beweisen:
Sei $T$ ein fester bin\"arer Suchbaum, der die Elemente $\{1, \dots n\}$ enth\"alt,
und sei $A = a_1, \dots, a_m$ eine Folge von $m$ Suchanfragen, die jedes Element mindestens
einmal enth\"alt. Sei $q_i$ die Anzahl der Anfragen an das Element $i$.
Dann ist die Gesamtlaufzeit f\"ur $A$ mindestens
\[
  \Omega\left(m + \sum_{i = 1}^n q_i \log \frac{m}{q_i}\right).
\]
\end{description}
\end{document}
