% 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}{5}
\begin{document}

\begin{centering}
{\large \bf Algorithmen
und Programmieren III, WS 1999/2000 ---
 5.~\"Ubungsblatt\par
}
\bigskip
Abgabe bis Dienstag, 7. Dezember 1999

\par \medskip
\end{centering}
\hrule
\medskip

\begin{enumerate}
\setcounter{enumi}{23}
\item (3 Punkte)
Schreiben Sie Funktionen vom Typ
\texttt{Int->T} in Haskell, die f\"ur gegebenes $n$
(a) einen m\"oglichst ausgeglichenen Baum, 
(b) einen nach links entarteten Baum,
(c) einen nach rechts entarteten Baum, beziehungsweise
(d) einen
entarteten Zickzackbaum mit $n$ Knoten erzeugen.
Bei (a) sollen die beiden Unterb\"aume jedes Knotens
m\"oglichst gleich viele Knoten enthalten.
Bei (b) hat kein Knoten ein rechtes Kind; der Baum besteht
aus einem einzigen Pfad, der immer nach links f\"uhrt,
und analog f\"ur~(c). Bei (d) gibt es ebenfalls auf jeder
Ebene nur einen Knoten, aber der Weg von der Wurzel zum einzigen Blatt
f\"uhrt abwechselnd nach links und nach rechts.
(Die Werte in den Knoten k\"onnen beliebig sein.)

\item (11 Punkte)
Laufzeitverhalten von Funktionen in Haskell.
Betrachten Sie folgende 2 Funktionen 
\texttt{sR1} und
\texttt{sR2}\footnote
{siehe 
\texttt{http://www.inf.fu-berlin.de/\char`\~rote/Lere/alp3/symmetrische%
Reihenfolge.hs}}
 zum Durchlaufen eines Baumes
in symmetrischer Reihenfolge und zur Ausgabe
aller Knoten in einer Liste:
$$
\hskip-3mm
\begin{minipage}[t]{0,46\textwidth}
\tt
\begin{tabbing}
sR1::\ T -> [Int]\\
sR1 Nil = []\\
sR1 (Baum l w r) =\\\qquad (sR1 l) ++ [w] ++ (sR1 r)\\[1ex]
len::\ T -> Int\\
len Nil = 0\\
len (Baum l \char`\_\ r) = 1+len l+len r
\end{tabbing}
\end{minipage}
\qquad
\begin{minipage}[t]{0,4\textwidth}
\tt
\begin{tabbing}
data T = Nil | Baum\char`\{l::T, wert::Int, r::T\char`\}\\
\qquad  deriving (Show,Eq)\\[1ex]
sR2::\ T -> [Int]\\
sR2 b = sR' b [] where\\
\quad\=\+
sR'::\ T -> [Int] -> [Int]\\
sR' Nil x = x\\
sR' (Baum l w r) x = sR' l (w:(sR' r x))
\end{tabbing}
\end{minipage}
$$
\begin{enumerate}
\item (0 Punkte)
Zeigen Sie, dass
\texttt{(sR' b x) ++ y $=$ sR' b (x++y)} ist.
\item (11 Punkte)
Vergleichen Sie die Laufzeit
von \texttt{sR1} und \texttt{sR2} f\"ur die B\"aume
(a)--(c) aus der vorigen Aufgabe, f\"ur jeweils
$n=2^i$ Knoten, $i=3,\ldots,11$.
Wenn man im HUGS-System \texttt{:set +s} eingibt,
wird nach jeder Eingabe die Anzahl der 
\emph{Reduktionen} (und auch die Anzahl der
verwendeten Speicherzellen) ausgegeben, die
man als Ma"s f\"ur die Laufzeit nehmen kann.
Um von der Erzeugung des Baumes und von der Zeit
f\"ur die Ausgabe der Liste abzusehen,
vergleichen Sie f\"ur jeden Baum \texttt{b} jeweils folgende
Eingaben:\\
(1) \texttt{len b}, als Ma"s f\"ur das einfachste Durchlaufen
des Baumes,\\
(2) \texttt{length (sR1 b)}, sowie\\
(3) \texttt{length (sR2 b)}.\\
Bilden sie jeweils die Differenz der Reduktionenzahl zwischen
(2) und (1), und zwischen (3) und (2).
Sch"atzen Sie sodann experimentell einen Wert f\"ur die Konstante $c$ unter
der Annahme, dass sich die gemessenen Laufzeitdifferenzen
nach der Formel
$c\cdot n$,
$c\cdot n\log_2 n$, beziehungsweise
$c\cdot n^2$ verhalten, sodass die Formel m\"oglichst gut mit
Ihren Daten \"ubereinstimmt.
Welche Formel halten Sie jeweils f\"ur die passende?
\item (Zusatzfrage, 3 Punkte)
Erkl\"aren Sie die Ergebnisse, die Sie erhalten haben.
\end{enumerate}

\item (7 Punkte)
Nehmen wir an, dass jeder Knoten eines Baumes auch einen
Zeiger zur Mutter hat:
$$\vcenter{\begin{tabbing}
\qquad\=\+
\texttt{class Baum2 extends Baum}\\
{\texttt{\char`\{} } \={\tt Baum2 m;}\\
\>$\cdots$
\end{tabbing}
}
$$
Der Mutterzeiger der Wurzel ist \texttt{null}.
Schreiben Sie ein nichtrekursives
Programm, das die Knoten des Baumes in symmetrischer
Reihenfolge ausgibt.
\item (9 Punkte)
Eine \emph{Triangulierung} eines konvexen $n$-Ecks $P_n$ ist eine
Zerlegung in $n-2$ Dreiecke durch $n-3$ nichtkreuzende
Diagonalen, die je zwei nichtbenarchbarte Ecken verbinden.
\begin{enumerate}
\item (0 Punkte)
Zeigen Sie, dass es 5 verschiedene Triangulierungen des F\"unfecks
$P_5$ gibt. (Die Ecken des $P_5$ sind nummeriert.)
Zeigen Sie, dass es 5 verschiedene bin\"are B\"aume mit 3 Knoten gibt.
% \item (0 Punkte)
Zeigen Sie, dass es genauso viele Triangulierungen des $P_n$ wie
bin\"are B\"aume mit $n-2$ Knoten gibt.
\item (4 Punkte)
Eine M\"oglichkeit, eine Triangulierung des $P_n$ anzugeben, ist die
\emph{Gradliste} $(a_1,\ldots,a_n)$, wobei $a_i$ die Anzahl
der Diagonalen ist, die in der $i$-ten Ecke zusammenkommen.
So hat zum Beispiel
jede Triangulierung des $P_5$ die Gradliste $(1,0,2,0,1)$,
bis auf zyklische Verschiebungen.

Zeigen Sie, dass es immer eine Ecke vom Grad $a_i=0$ geben muss.
(Was entspricht einer solchen Ecke geometrisch?
Was passiert, wenn man eine solche Ecke entfernt?)
\item (0 Punkte)
Zeigen Sie, dass eine Triangulierung durch ihre
Gradliste eindeutig bestimmt ist.
\item (5 Punkte) Schreiben Sie ein Programm, das testet,
ob eine gegeben Folge $(a_1,\ldots,a_n)$ die
Gradliste einer Triangulierung ist.
\end{enumerate}

\item (4 Punkte)  Zuf"allige Permutationen.
% \begin{enumerate}
% \item
% Wie kann man eine zuf"allige Permutation der
% Zahlen $1,\ldots,n$ erzeugen?
% \item 
Wie kann man eine gegebene Folge $a_1,\ldots,a_n$ von
Zahlen in eine zuf"allige Reihenfolge bringen?
% \end{enumerate}
Sch"atzen Sie die Laufzeit und den Speicherplatz Ihres Algorithmus ab.
Wie viele Zufallszahlen ben"otigen Sie?
(F"ur einen Linearzeitalgorithmus gibt es einen Zusatzpunkt.)

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

Bestimmen Sie 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$.

% Markieren Sie in Ihrem Programmausdruck alle Teile, die Sie
% unver"andert aus Aufgabe~\altenummer\ "ubernehmen konnten, mit einem
% gr"unen Strich am Rand.

\item (0 Punkte)
Verschmelzen. Addition st"uckweise linearer Funktionen.\\
Eine st"uckweise lineare Funktionen  $f\colon [u,v]\to \mathbb{R}$ ist
durch eine zusammenh"angende
Folge von Intervallen mit entsprechenden linearen St\"ucken
$f(x)=ax+b$ gegeben, zum Beispiel:
$$f(x)=
\begin{cases}
x+1,&\text{ f"ur $-1<x\le 0$}\\
-1,&\text{ f"ur $0<x<2$}\\
6-2x,&\text{ f"ur $2\le x \le 4$}
\end{cases}
$$
\begin{enumerate}
\item
"Uberlegen Sie sich eine Datenstruktur (Haskell-Datentyp/Java-Klasse)
zur Darstellung solcher Funktionen.
Schreiben Sie eine Funktion/Methode, die den Wert einer solche Funktion $f(x)$ an einer
gegebenen Stelle $x$ ausrechnet.
\item Schreiben Sie eine Funktion zur Addition zweier st"uckweise
linearer Funktionen.
Der Definitionsbereich von $f+g$ soll dabei der Durchschnitt
der Definitionsbereiche von $f$ und~$g$ sein.
\item % (0 Punkte)
Schreiben Sie eine Funktion/Methode zur Integration einer st"uckweise
\emph{konstanten} Funktion $f\colon [u,v]\to \mathbb{R}$.
Das hei"st, es soll die st"uckweise
lineare und stetige Stammfunktion $F$ von $f$ berechnet werden:
$$F\colon [u,v]\to \mathbb{R}, \qquad
F(x)=\int_u^x f(x)\,dx$$

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

