% 5. Uebungsblatt ALP3 WS 2003/04
\documentclass [11pt] {article}
\usepackage [reqno] {amsmath}
\usepackage[latin1]{inputenc}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage {ngerman}
\textwidth=16,1cm
\textheight=25,6cm
\hoffset = -17mm
\voffset = -33mm

\setcounter{page}{8}
\begin{document}

\begin{centering}
{\large \bf Algorithmen und Programmierung 3, WS 2003/2004 ---
7.~\"Ubungsblatt\par}
\bigskip
Abgabe bis Donnerstag, 8. Januar 2004
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{40}
\parskip=0pt
\item (7 Punkte)
Versuchen Sie, den Huffman-Algorithmus zur Konstruktion eines
optimalen Kodes auf ein ternäres Kodealphabet (ein Alphabet mit drei
Buchstaben) zu verallgemeinern.
Konstruieren Sie einen optimalen ternären Kode für $n=8$ Quellsymbole
mit relativen Häufigkeiten
$(p_1,\ldots,p_8) = (
\frac{2}{56},
\frac{3}{56},
\frac{4}{56},
\frac{6}{56},
\frac{7}{56},
\frac{10}{56},
\frac{11}{56},
\frac{13}{56}
)$.

\item (7 Punkte)
Eine st"uckweise konstante Funktionen  $f\colon (u,v]\to \mathbb{R}$ ist
durch eine zusammenh"angende
Folge von Intervallen mit entsprechenden Werten
$f(x)=a$ gegeben, z. B.
$$f(x)=
\begin{cases}
1,&\text{ f"ur $-1<x\le 0$}\\
-1,&\text{ f"ur $0<x\le2$}\\
6,&\text{ f"ur $2< x \le 4$}
\end{cases}
$$
\emph{Spezifizieren} Sie eine Datenstruktur
zur Darstellung solcher Funktionen.
Nehmen Sie % der Einfachheit halber
 an, dass alle Intervalle
halboffen sind, und zwar links offen und rechts abgeschlossen,
wie im obigen Beispiel.
Die Datenstruktur soll zumindest folgende Operationen erlauben:
\begin{enumerate}
\item
Berechnung des Wertes einer solche Funktion $f(x)$ an einer
gegebenen Stelle~$x$.
Falls $x$ nicht im Definitionsbereich liegt,
soll der Wert 0 zur"uckgegeben werden.
\item Addition und Multiplikation zweier st"uckweise
konstanter Funktionen.
Entscheiden Sie selbst, was der Definitionsbereich von $f+g$ beziehungsweise $fg$
sein soll.
\end{enumerate}


\item (6 Punkte)
Leiten Sie aus der algebraischen Spezifikation f\"ur Mengen
 \begin{eqnarray}
\textit{istenthalten}(x,\textit{leer}\/) &=& \textit{falsch} \\
\textit{istenthalten}(x,\textit{einf\"uge}(x,M)) &=& \textit{wahr} \\[-3pt]
\textit{istenthalten}(x,\textit{einf\"uge}(y,M)) &=&
\textit{istenthalten}(x,M), \qquad \textrm{f\"ur $x\ne y$}\\
\textit{istenthalten}(x,\textit{l\"osche}(x,M)) &=& \textit{falsch} \\[-3pt]
\textit{istenthalten}(x,\textit{l\"osche}(y,M)) &=&
\textit{istenthalten}(x,M), \qquad \textrm{f\"ur $x\ne y$}
  \end{eqnarray}
durch Umformungen folgende Identit"at her:
$$
\textit{istenthalten}(u,
\textit{einf\"uge}(x,
\textit{l\"osche}(x,
M))) =
\textit{istenthalten}(u,
\textit{einf\"uge}(x,
% \textit{l\"osche}(x,
M)).
$$
Geben Sie dabei in jedem Beweisschritt die Nummer der Gleichung an, die Sie
verwenden.


\item (0 Punkte)
Gegeben sei eine Funktion $f\colon
\{0,\ldots,n-1\}\to\{0,\ldots,n-1\}$,
die einen großen (aber endlichen) Bereich in sich selbst abbildet,
zum Beispiel
$$f(x) = x^3 + 2x^2 +7 \bmod 10^6.$$
Wir betrachten die Folge $a_0=0$, $a_{i+1}=f(a_i)$.
Da der Bereich endlich ist, muss die Folge Wiederholungen
enthalten.
Wie kann man in $O(n)$ Zeit mit \emph{konstantem Speicher} ein
doppeltes Element finden?
Wie kann man das kleinste $i$ und das kleinste $j$ finden, sodass
$a_i=a_{i+j}$ ist?%
\footnote{Diese Aufgabe dient nur zur Erbauung und hat mit dem
  Stoff der Vorlesung nicht direkt etwas zu tun.
Lösungshinweise (für alle, die nicht selbst daraufkommen wollen) finden Sie auf der Netzseite der Vorlesung.}

% Hinweis 1: Betrachten Sie die Folge der Paare
%(<it>a<sub>i<sub></it>,
%<it>a</it><sub>2<it>i</it><sub>)
% Hinweis 2: Oder betrachten Sie die Folge der Paare
%(<it>a</it><sub>k<sub>) f&uuml;r <it>k</it>=2<it><sup>i<sub></it>
%zusammen mit <it>a</it><sub>j<sub> f&uuml;r <it>j</it>&lt2<it><sup>i<sub></it>

\item (0 Punkte) Der \emph{Weihnachtsmann} ist mit seinem Rentierschlitten in
  die Mitte eines kreis\-för\-migen Sees mit Umfang 100\,\textit{m}
  gefallen. Am Rande des Sees befindes sich ein \emph{Grinch}, der nicht
  schwimmen, aber 4,5-mal so schnell laufen kann wie die Rentiere den
  Schlitten im Wasser ziehen k\"onnen. Auf dem Land ist der
  Rentierschlitten jedoch schneller als der Grinch. Kann der
  Weihnachtsmann die Rentiere so lenken, dass die Weihnachtsgeschenke
  nicht dem Grinch in die H\"ande fallen und er die Pakete noch
  rechtzeitig abliefern kann?  Wenn ja, welchen Mindestabstand vom
  Grinch kann der Weihnachtsmann erreichen, wenn er das rettende
  Land erreicht?  Der Einfachheit halber stelle man sich Grinch und
  Rentierschlitten jeweils punktf\"ormig vor.\footnote
{Mit etwas Kreativität kann man diese Aufgabe auch mit
    Hilfe eines Computers lösen.
%
  Die weihnachtliche Einkleidung dieses Rätsels habe ich teilweise von
  \texttt{http://www.fzt86.de/Adventskalender/} übernommen.}

\eject
\end{enumerate}
\end{document}
