% 3. Uebungsblatt ALP3 WS 1999/2000
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\textwidth=16,1cm
\textheight=25cm
\hoffset = -17mm
\voffset = -20mm
\newcommand{\ldt}{\mathrel{.\,.}}

\setcounter{page}{3}
\begin{document}

\begin{centering}
{\large \bf Algorithmen und Programmieren 3, WS 1999/2000 ---
 3.~\"Ubungsblatt\par }
\bigskip
Abgabe bis Dienstag, 16. November 1999
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{16}

\item (7 Punkte)
\begin{enumerate}
\item 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 Schreiben Sie eine Klasse \texttt{Halde}, die eine \texttt{PWSchlange}
implementiert beziehungsweise erweitert\rlap.%
\footnote{siehe die Programme aus der Vorlesung,
\texttt{http://www.inf.fu-berlin.de/\char`\~rote/Lere/alp3/heapsort.java}}
\end{enumerate}

\item (13 Punkte)
Simulieren Sie eine einfache Warteschlange in Java.

In einem Supermarkt mit $n=3$ Kassen
stellen sich ankommende Kunden bei einer der Kassen an, bis sie an
dieser Kasse bedient werden.

Die Ankunft der Kunden ist ein Poisson-Prozess mit Rate $\lambda=1{},5\,$min$^{-1}$.
Das hei"st, dass der Abstand von der Ankunft eines Kunden bis zur Ankunft
des n"achsten Kunden exponentialverteilt mit dem
Mittelwert $1/\lambda = 40$~Sekunden ist.
Eine exponentialverteilte Zufallsvariable mit Mittelwert $\mu$
kann man mit der Formel {\tt -$\mu$*Math.log(Math.random())} erzeugen.

Die Zeit zur Bedienung eines Kunden an der Kasse ist gleichverteilt im
Intervall $[a\ldt b]$ mit $a=10\,$sec und $b=200\,$sec.
Eine solche gleichverteilte Zufallsvariable
kann man mit der Formel {\tt a+(b-a)*Math.random()} erzeugen.

Untersuchen Sie nun folgende F"alle:
\begin{enumerate}

\item Es gibt eine gemeinsame Schlange f"ur alle Kassen.

\item Es gibt eine getrennte Schlange f"ur jede Kasse.
Neu ankommende Kunden stellen sich bei einer zuf"alligen Kasse an,
(auch wenn eine andere Kasse frei w"are),
und bleiben dort stehen, bis sie bedient werden.

\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 9:00 bis 19:00 Uhr eines Tages.
(Um 19:00 Uhr wird der Eingang geschlossen; es stellen
sich keine weiteren Kunden mehr an, aber alle Kunden, die
sich schon angestellt haben,
werden noch bedient.)
Bestimmen Sie f"ur jede Variante die durchschnittliche Wartezeit eines Kunden,
die maximale Wartezeit, und die Gesamtzeit, wie lange die
Kassiererinnen nichts zu tun hatten.
F"uhren Sie je drei unabh"angige Simulationsl"aufe durch.

Schreiben Sie Ihr Programm so, dass es m"oglichst
leicht zu "andern oder zu erweitern
ist (zum Beispiel f"ur unterschiedliche Werte von $\lambda$ 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.


\end{enumerate}
\end{document}
