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

\setcounter{page}{9}
\begin{document}

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


\begin{enumerate}
\setcounter{enumi}{45}
\parskip=0,5\parskip
\item (0 Punkte) Beweisen Sie folgende Gleichungen für Listen
  \texttt{x} und \texttt{y} durch strukturelle Rekursion
aus den unten angegebenen Definitionen.
 \begin{eqnarray}
\texttt{x ++ [ ]} &=& \texttt{x} \\
\texttt{length (x ++ y)} &=& \texttt{(length x) + (length y)}\\
\texttt{length (reverse x)} &=& \texttt{(length x)}\\
\texttt{reverse (x ++ y)} &=&
 \texttt{(reverse y) ++ (reverse x)}\\
\texttt{reverse (reverse x)} &=& \texttt{x}
 \end{eqnarray}
\texttt{%
\begin{minipage}[t]{0,50\textwidth}
[ ] ++ yl = yl\\
(x : xr) ++ yl = x :(xr ++ yl)\smallskip\\
%\end{minipage}
%\begin{minipage}[t]{0,33\textwidth}
reverse [ ] = [ ]\\
reverse (x : xr) = (reverse xr) ++ [x]
\end{minipage}
\begin{minipage}[t]{0,50\textwidth}
length [ ] = 0\\
length (x : xr) = 1 + (length xr)
\end{minipage}
}

\item (0 Punkte)
Beweisen Sie (zum Beispiel durch strukturelle Induktion), dass
jeder vollständig balancierten
 ternäre Baum der Höhe $h$ genau $(3^{h+1}-1)/2$ Knoten enthält.
(Jeder innere Knoten hat genau 3 Kinder, und alle Blätter befinden
sich auf Tiefe~$h$.)

\item (0 Punkte)
Ein binärer Suchbaum soll Einträge speichern, die außer dem Schlüssel $x_i$
noch ein "`Gewicht"' $w_i$ enthalten.
 Die Algorithmen zum Suchen, Einf"ugen und
L"oschen in bin"aren Suchb"aumen sollen so erweitert werden,
dass man jederzeit zu
 zwei Werten $a$ und $b$
das Gesamtgewicht aller Einträge finden kann,
 deren Schlüssel
 $x_i$
 im Intervall $a< x_i\le b$ liegt.
%
Die %benötigte
 Laufzeit für alle Operationen soll höchstens proportional zur
H"ohe des Baumes sein.

Beschreiben Sie die Felder, die in den Knoten enthalten sind
(zusammen mit einer Erklärung der Bedeutung, sofern sie nicht offensichtlich ist),
und schreiben Sie ein
Programmstück (Methoden in Java oder Funktionen in
Haskell)
für die oben beschriebene {Intervallabfrage} und
zum Einfügen eines neuen Elementes.

\item (8 Punkte) Spezifizieren Sie den abstrakten Datentyp einer
Priorit"atswarteschlange, die mindestens
die Operationen
\texttt{entferneMin}, \texttt{einf"ugen} und \texttt{istLeer} enth"alt.
Die Prioritätswarteschlange soll \emph{Einträge} $(x_i,a_i)$ enthalten,
die einen \emph{Schlüssel} $x_i$ (eine Zahl) und einen \emph{Wert}
$a_i$
enthalten.
(Entscheiden Sie, wie sie mit gleichen Schlüsseln umgehen wollen.)


\item (12 Punkte) 
Modifizieren Sie das Programm zur Warteschlangensimulation  aus
Aufgabe~22 vom 3.~Übungsblatt, Variante (a) folgendermaßen:
%
Die Ankunftsrate der Patienten ist $\lambda=5/\mathrm{h}$, und es gibt
$n=3$ Ärztinnen.
%
Es gibt eine zusätzliche Kategorie von \emph{Notfallpatienten}
mit Ankunftsrate $\lambda=0{,}5/\mathrm{h}$.
Bei Ankunft eines Notfallpatienten unterbrechen alle $n$ Ärztinnen
ihre augenblickliche Tätigkeit und beschäftigen sich für einen
Zeitraum, der gleichverteilt im
Intervall $[a\ldt b]$ mit $a=30\,$min und $b=40\,$min ist,
mit dem neuen Patienten.
Danach wird der Notfallpatient zu einer anderen Abteilung geschickt
und verlässt das hier untersuchte System, und die Ärztinnen fahren mit
der vorher unterbrochenen Tätigkeit fort.
%
Ein neuer Notfallpatient, der während der Behandlung eines
Notfallspatienten eintrifft, kommt dran, wenn diese Behandlung
abgeschlossen ist.

\item (0 Punkte) Bestimmen des doppelten Elementes.%
\footnote{Diese Aufgabe dient zur Entspannung und hat mit dem
  Stoff der Vorlesung nichts zu tun. Wenn Sie das Rätsel aus einer
  anderen Quelle bereits kennen, dann würde mich sehr interessieren,
  woher.}
\\In einem Array $a_0,a_1,\ldots,a_n$ sind ganzzahlige Werte
zwischen 1 und $n$ gespeichert.
Daraus folgt, dass es mindestens eine Zahl geben muss, die doppelt vorkommt.
Schreiben Sie ein Programm, das eine dieser Zahlen bestimmt.
Das Programm soll lineare Laufzeit haben, auf das Array $a$ nur \emph{lesend}
zugreifen, und nur konstanten zusätzlichen Speicher benötigen.

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