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

\setcounter{page}{4}
\begin{document}

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


\begin{enumerate}
\setcounter{enumi}{18}

\item (0 Punkte)
Definieren Sie die arithmetischen Operationen f"ur die
ganzen Zahlen, die um die Werte $\pm\infty$ und \emph{undefiniert}
erweitert wurden. Es sollten die erwarteten Rechenregeln gelten,
zum Beispiel $a + (-\infty) = {-\infty}$, $a/(+\infty)=0$, f"ur $a\in\mathbb{Z}$,
$(+\infty) + (-\infty) = \textit{undef}$, usw.
%
Verwenden Sie dazu einen algebraischen Typ, der etwa so aussehen k"onnte:
$$\vbox{\hbox{\texttt{data Int' = Normal Int}}
\hbox{
\qquad \texttt{| PlusUnendlich | MinusUnendlich | Undefiniert deriving ....}}}
$$

\item (7 Punkte) Definieren Sie in Haskell einen algebraischen Datentyp \texttt{Menge a}
f"ur Mengen von Elementen
des Typs \texttt{a}, die wahlweise durch Aufz"ahlen der Elemente
oder durch Angabe einer charakteristischen Eigenschaft definiert
werden k"onnen.
(Sie k"onne sich dabei an der vorigen Aufgabe orientieren.)
Schreiben Sie folgende Funktionen:
\begin{tabbing} \qquad\=\+
{\tt mengeausListe} \qquad \= {\tt :: [a] -> Menge a}
\hskip 2cm \= {\tt --} $\{x_1,x_2,\ldots,x_n\}$ \\
{\tt mengef"urdiegilt} \>{\tt :: (a -> Bool) -> Menge a}
\> {\tt --} $\{\,x \mid f(x)\,\}$ \\
{\tt mengeDurchschnitt} \>{\tt :: Menge a -> Menge a -> Menge a }\\
{\tt mengeVereinigung} \> {\tt :: Menge a -> Menge a -> Menge a }\\
{\tt mengeElementvon} \>{\tt :: a -> Menge a -> Bool }\>
   {\tt --} $x\in M$
\end{tabbing}

\item (0 Punkte)
Zwei B"aume hei"sen \emph{isomorph}, wenn sie dieselbe Struktur 
(unabh"angig von den Knotenbeschriftungen) haben. Definieren Sie ein
Funktion\\
\qquad\texttt{isomorph :: Tree a -> Tree b -> Bool}\\
zum Testen, ob zwei B"aume isomorph sind.

\item (0 Punkte)
Ein \emph{vollst"andiger} bin"arer Baum der H"ohe $h$ ist
ein Baum, bei dem jeder Knoten mit Tiefe ${}\le h-2$ genau zwei Kinder hat.
% und bei dem jedes Blatt entweder Tiefe $h$ oder $h-1$ hat.
\begin{enumerate}
\item Zeichnen Sie vollst"andige bin"are B"aume
mit 12 und mit 15 Knoten.
\item Wieviele Knoten kann ein vollst"andiger bin"arer Baum
der H"ohe $h$ (mindestens und h"ochstens) haben?
\item Welche H"ohe kann ein vollst"andiger bin"arer Baum
mit $n$ Knoten haben?

\end{enumerate}

\item (15 Punkte)
Das \emph{Ungleichgewicht} eines Knotens $x$ in einem bin"aren Baum
ist definiert als
$$|H(l(x))-H(r(x))|,$$
wobei $l(x)$ und $r(x)$ der linke und der rechte Teilbaum von $x$ ist
und $H(b)$ die H"ohe eines Baumes $b$ ist.
Das {Ungleichgewicht} eines \emph{bin"aren Baumes} ist das maximale
{Ungleichgewicht} aller Knoten des Baumes.

\begin{enumerate}
\item (3 Punkte) Schreiben Sie ein Programm in Haskell, das das
Ungleichgewicht eines Baumes berechnet.
\item (7 Punkte) Erweitern Sie die Java-Klasse \texttt{Baum} aus der
Vorlesung, sodass man das Ungleichgewicht des Baumes
(mit einer neuen Methode \texttt{getUngleichgewicht})
jederzeit ablesen kann, ohne es neu zu berechnen.
(Hinweis: In der neuen Klasse sollte jeder Knoten
ein Feld mit seinem Ungleichgewicht enthalten, und m"oglicherweise noch
andere Felder. Gegebenenfalls m"ussen Sie die Methoden
\texttt {einf"ugen} und
\texttt {entfernen} ab"andern.)
\item (1 Punkt)
Wie viele Knoten kann ein bin"arer Baum der H"ohe $h$ haben, dessen
Ungleichgewicht 0 ist?
\item (4 Punkte)
Ein \emph{AVL-Baum} ist ein bin"arer Baum, dessen
Ungleichgewicht h"ochstens~1 ist (nach Adel$'$son-Velski und Landis).
Wie viele Knoten kann ein AVL-Baum der H"ohe~$h$ (mindestens und h"ochstens) haben, f"ur $h\le 7$?
\item (freiwillige Zusatzfrage, 3 Punkte)
Welche H"ohe kann ein AVL-Baum mit $n$ Knoten (mindestens und h"ochstens) haben?
\end{enumerate}
\end{enumerate}
\eject
\end{document}

