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

\newcommand{\ZETTELNUMMER}{13}
\newcommand{\ABGABEDATUM}{am 2. Februar 2016 bis 12 Uhr in die
Tutorenf\"acher}

\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}}
\newcommand{\B}{\mathbb{B}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}



\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{Informatik A}\hfill WiSe 2015/16 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\noindent
Dies ist das letzte Aufgabenblatt.

\vskip 0.5cm

\begin{description}

\AUFGABE{Kodierung allgemein}{10 Punkte}

\begin{enumerate}
\item
Welche der folgenden Bin\"arcodes sind eindeutig 
dekodierbar? Welche sind pr\"afixfrei? Warum?
\[
C_1 = \{0110, 010, 0 \},\quad C_2 = \{010, 00, 001, 01\},\quad
C_3 = \{1, 001, 0100, 011\}.
\]
\item 
Konstruieren Sie f\"ur die folgenden Kodewortl\"angen einen 
bin\"aren pr\"afixfreien Kode und zeichnen Sie den zugeh\"origen
Kodebaum.
\[
n_1 = 1,\, n_2 = 2,\, n_3 = 3,\, n_4 = n_5 = 5,\,
n_6 = n_7= n_8 = 6,\, n_9 = 7.
\]
\item
Richtig oder falsch? Begr\"unden Sie Ihre Antwort genau.

Enth\"alt ein optimaler pr\"afixfreier Kode f\"ur
eine Folge von Zeichen mit gegebenen H\"aufigkeiten
ein Kodewort der L\"ange $k \geq 1$, so gibt es im Kode
auch ein Kodewort f\"ur jede L\"ange $l$ mit 
$1 \leq l \leq k$.
\end{enumerate}

\AUFGABE{Implementierung der Huffman-Kodierung}{10 Punkte}

Auf der Website finden Sie ein Haskell-Skript
\texttt{huffman\_u.hs}, welches eine
partielle Implementierung der Huffman-Kodierung
enth\"alt. Vervollst\"andigen Sie es,
so dass sich ein lauff\"ahiges Programm ergibt.


\AUFGABE{Fano-Kodierung}{10 Punkte}

Die Fano-Kodierung ist ein pr\"afixfreier Kode,
welcher dem Huffman-Kode sehr \"ahnlich ist.
Der Kodierungsalgorithmus besteht aus folgenden Schritten:
\begin{enumerate}
\item 
Die Zeichen werden bez\"uglich
ihrer H\"aufigkeit im Text aufsteigend sortiert.
\item 
Unter Beibehaltung dieser Ordnung wird die sortierte 
Liste in Pr\"afix und Suffix geteilt, so dass beide Teile 
m\"oglichst die gleiche Gesamtwahrscheinlichkeit haben. 
Alle Zeichen im Pr\"afix beginnen in der Codierung mit $0$, alle 
im Suffix mit $1$.
\item 
Wiederhole Schritt (b) rekursiv auf den beiden 
Teillisten, bis diese Gr\"o\ss{}e $1$ haben.
\end{enumerate}

Finden Sie f\"ur  einen Text mit den Zeichen 
a, b, c, d und e und zugeh\"origen
Wahrscheinlichkeiten $0.40, 0.19, 0.19, 0.12, 0.10$ 
sowohl die Fano- als auch die Huffman-Kodierung.
Bestimmen Sie auch die zugh\"origen mittleren Kodewortl\"angen.
Was zeigt das Ergebnis?

\end{description}

\noindent
Geben Sie immer alle Signaturen an und machen Sie geeignete Testl\"aufe.
Versehen Sie Ihr Skript mit geeigneten Kommentaren.


\end{document}
