% 3. 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}{4}
\begin{document}

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


\begin{enumerate}
\setcounter{enumi}{19}
\parskip=0,1\parskip
\item (2 Punkte)
Beweisen Sie, dass man zum Finden eines Elementes in einer sortierten
Liste mit $n$ Elementen mindestens $\Omega(\log n)$ Vergleiche
benötigt.

\item
\begin{enumerate}
\item (3 Punkte) Schreiben Sie eine Schnittstelle (\texttt{interface}) oder eine abstrakte
Klasse \texttt{PWSchlange} f"ur eine Priorit"atswarteschlange, die mindestens
die beiden Methoden
\texttt{entferneMin} und \texttt{einf"ugen} enth"alt.
Die Priorit"atswarteschlange soll Objekte vom Typ \texttt{Comparable} verwalten.

\item (3 Punkte) Schreiben Sie eine Klasse \texttt{Halde}, die eine \texttt{PWSchlange}
implementiert beziehungsweise erweitert\rlap.%
\footnote{siehe das Programm aus der Vorlesung:\\
  \texttt{http://www.inf.fu-berlin.de/\char`\~rote/Lere/2003-04-WS/Algorithmen+Programmierung3/heapsort.java}}
\end{enumerate}

\item (12 Punkte) Simulation einer Warteschlange in Java.\\
%
In einer Unfallambulanz müssen sich die ankommenden Patienten zunächst
anmelden. Danach werden Sie in der Reihenfolge der Anmeldung von einer
der $n=2$ diensthabenden Ärztinnen befragt und untersucht.
Gegebenfalls wird ein Röntgenbild angefertigt, und anschließend werden
die Patienten behandelt.

Die Ankunft der Patienten ist ein Poisson-Prozess mit Rate $\lambda=2\,$h$^{-1}$.
Das hei"st, dass der Abstand von der Ankunft eines Patienten bis zur Ankunft
des n"achsten Patienten exponentialverteilt mit dem
Mittelwert $1/\lambda = 30$~Minuten ist.
Eine exponentialverteilte Zufallsvariable mit Mittelwert $\mu$
kann man mit der Formel {\tt -$\mu$*Math.log(Math.random())} erzeugen.
%
Die Zeit, die zur Anmeldung nötig ist, soll vernachlässigt werden.
Die Dauer der ersten Untersuchung ist gleichverteilt im
Intervall $[a\ldt b]$ mit $a=5\,$min und $b=20\,$min.
Eine solche gleichverteilte Zufallsvariable
kann man mit der Formel {\tt a+(b-a)*Math.random()} erzeugen.
%
Anschließend ist mit Wahrscheinlichkeit $p=0{,}15$
die Behandlung beendet, und der Patient wird entlassen.
%  Mit Wahrscheinlichkeit $1-p=0{,}85$
Andernfalls
 wird der Patient zum Röntgen geschickt.
%
Die Patienten werden dort in der
Reihenfolge ihrer Ankunft an der Röntgenstation drangenommen.
Die Zeit zur Erstellung eines Röntgenbildes ist gleichverteilt im
Intervall $[a\ldt b]$ mit $a=5\,$min und $b=10\,$min (unabhängig von
der Dauer der Untersuchung). Die anschließende Behandlung ist wieder
eine unabhängige Zufallsvariable im Intervall $[a\ldt b]$ mit $a=10\,$min und $b=30\,$min.


Untersuchen Sie nun folgende Varianten:
\begin{enumerate}

\item
Jeder neue Patient wird
  der ersten freiwerdenden Ärztin zugeteilt.
  Nach dem Fertigstellen des Röntgenbildes muss der Patient von
  derselben Ärztin behandelt werden.
 Wenn eine Ärztin frei wird, nimmt sie als nächstes bevorzugt einen
 Patienten an, der von der Röntgenabteilung zurückkommt.

\item Wie oben, aber die Patienten, die vom Röntgen zurückkommen,
  reihen sich in dieselbe Schlange ein wie die neuen Patienten.

% \item (freiwillige Zusatzaufgabe, 1 Punkt.) Es gibt eine getrennte Schlange
% f"ur jede Kasse.
% Neu ankommende Kunden stellen sich bei der k"urzesten Schlange an.
% Wenn mehrere Schlangen die gleiche L"ange haben, dann wird
% die "`erste"' Schlange (mit der kleinsten Nummer) gew"ahlt.


\end{enumerate}
Simulieren Sie diese Schlange von 7:00 bis 11:00 Uhr eines Tages.
(Um 11:00 Uhr wird die Ambulanz geschlossen; es werden keine
 weiteren Patienten mehr angenommen, aber alle Patienten, die
sich schon angemeldet haben,
werden noch behandelt.)

Bestimmen Sie f"ur jede Variante die durchschnittliche Wartezeit eines Patienten,
die maximale Wartezeit, und die Gesamtzeit, wie lange die
Ärztinnen nichts zu tun hatten (von 7:00 Uhr bis zur Behandlung des
jeweils letzten Patienten). % unklar!
F"uhren Sie je drei unabh"angige Simulationsl"aufe durch.
% Ende der Behandlung
% frühere Öffnung des Wartezimmers


Schreiben Sie Ihr Programm so, dass es m"oglichst
leicht zu "andern oder zu erweitern
ist (zum Beispiel f"ur unterschiedliche Werte von $\lambda$, $p$ und $n$).
Verwenden Sie ein Objekt vom Typ \texttt{PWSchlange}
aus der vorigen Aufgabe zur Verwaltung der n"achsten Ereignisse.

Stellen Sie die Hierarchie aller Klassen und Schnittstellen,
die Sie definiert haben, dar.


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