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

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

\begin{centering}
{\large \bf Algorithmen
und Programmieren III, WS 1999/2000 ---
 7.~\"Ubungsblatt\par
}
\bigskip
Abgabe: Aufgabe 37 bis Dienstag, 4. J\"anner,
Aufgaben 39--40 bis Dienstag, 11. J\"anner 2000.
\par \medskip
\end{centering}
\hrule
\medskip

\begin{enumerate}
\setcounter{enumi}{36}

\def \altenummer{18}
\item ($9$ Punkte)
"Andern Sie die Warteschlangensimulation aus Aufgabe \altenummer(a)
wie folgt.

Die mittlere Zeit zwischen zwei Kunden sinkt auf $1/\lambda=10\,$Sekunden,
daf\"ur gibt es nun 12~Kassen.
Bestimmen Sie zus\"atzlich
die durchschnittliche L"ange $\ell$ der Warteschlange
im Zeitraum zwischen 12:00 und 13:00 Uhr, sowie den Zeitpunkt $t$,
wann der letzte Kunde fertig ist.
F"uhren Sie 100 unabh"angige Simulationsl"aufe durch,
und bestimmen Sie dem maximalen, den minimalen, und den Mittelwert von~$\ell$
und~$t$.

Sie k\"onnen Ihre eigene L"osung
von Aufgabe \altenummer(a)  oder
die Musterl"osung \texttt{Simulation.java}\footnote
{siehe 
\texttt{http://www.inf.fu-berlin.de/\char`\~rote/Lere/alp3/Simulation%
.java}}
 modifizieren.
 Markieren Sie in Ihrem Programmausdruck alle Teile, die Sie
 unver"andert "ubernehmen konnten, mit einem
 gr"unen Strich am Rand.

\item (0 Punkte)
Modifizieren Sie das Programm \texttt{Simulation.java}\footnotemark[1]
wie folgt:
Die Klassen \texttt{Kassen} und \texttt{Kasse} sollen aus
der Klasse \texttt{Simulation} herausgenommen werden.
Die Methoden und Felder aus \texttt{Kassen} sollen durch
entsprechende statische Methoden und Felder der Klasse \texttt{Kasse}
ersetzt werden, sodass die Klasse \texttt{Kassen} "uberfl"ussig wird.

\item 
\noindent\hbox to \linewidth{\vtop{\hsize=\linewidth \noindent
\hangindent=-24mm \hangafter=-6
(10 Punkte) Der Computer \textsc{Sumo-0} verf"ugt "uber 10 Eingaberegister,
die von \texttt{E0} bis \texttt{E9} nummeriert sind,
sowie 26 Akkumulatoren, die
von \texttt{Va} bis \texttt{Vz} bezeichnet sind.
Ein Programm f"ur diesen Rechner ist in der Assemblersprache
\textsc{Sumatra} geschrieben und sieht zum Beispiel wie das
nebenstehende Programm aus.

\hangafter=-2
In jeder Zeile wird das Ergebnis einer zweistelligen
arithmetischen Operation der Variablen auf der
linken Seite zugewiesen.
Jede Variable darf h"ochstens \emph{einmal} auf der
linken Seite einer Zuweisung auftreten.
Als Operand einer arithmetischen Operation kann
entweder ein Eingaberegister \texttt{E$i$} oder Inhalt einer
Variablen \texttt{V$x$},
deren Wert in einer fr"uheren Zeile definiert wurde, auftreten.

}\llap {\vtop{% \hrule height 0pt \vskip -0,5\baselineskip
{\tt \let\\=\cr
\halign{#\hfil\cr
Vf=E0+E1\\
Vc=Vf-E2\\
Vu=Vf+Vf\\
Vv=Vu*Vc\\
Vk=Vf/E0\\
Vl=Vk+E9\\
$\ldots$\cr}
}}}}


Die Programmzeilen werden der Reihe nach ausgef"uhrt.
Schleifen und Verzweigungen sind unbekannt.

\begin{enumerate}
\item (10 Punkte) Schreiben Sie ein Programm, das ein g"ultiges
\textsc{Sumatra}-Programm einliest und
die Abh"angigkeit der Ergebnisse von den Operanden
als Graph abspeichert.

Das Programm soll folgende Fragen beantworten k"onnen:
Welche Variablen h"angen (m"oglicherweise%
\footnote{Dass zum Beispiel nach der
Anweisung \texttt{Vy=Vx-Vx} die Variable \texttt{Vy} in Wirklichkeit
nicht von \texttt{Vx} abh"angt,
brauchen Sie nicht zu ber"ucksichtigen.})
 vom Wert des Eingaberegisters \texttt{E$i$} ab?
Von welchen Eingaberegistern h"angt der Wert der
Variablen \texttt{V$x$} ab?
\item (0 Punkte) Bei gewissen Eingaben stellt
sich heraus, dass das Programm mit einem Laufzeitfehler abbricht,
weil durch 0 dividiert wurde.
Der \textsc{Sumatra}-Programmierer m\"ochte den Laufzeitfehler
dadurch vermeiden, dass er den Wert eines Eingaberegisters
ver"andert (und alle anderen Eingaberegister gleich l"asst).
Ihr Programm soll feststellen, welche Eingaberegister
"uberhaupt prinzipiell einen Einfluss auf das Auftreten einer
Division durch Null haben k\"onnen.
\end{enumerate}

\item (5 Punkte)
Dem primitiven Charakter der Sprache entsprechend,
werden die Zeilen eines \textsc{Sumatra}-Programmes
auf \emph{Lochkarten} gestanzt.
Nehmen wir an, dass der Stapel von Lochkarten eines Programmes
zu Boden gefallen ist und die Zeilen durcheinandergemischt
worden sind.
Wie kann man die Programmzeilen wieder in eine gute Reihenfolge
bringen?
(Sie brauchen kein lauf"|f\"ahiges
Programm f"ur diese Aufgabe zu schreiben.)
\end{enumerate}
\end{document}

