% 10. 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=25,03cm
\hoffset = -17mm
\voffset = -30mm

\setcounter{page}{11}
\begin{document}

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


\begin{enumerate}
\setcounter{enumi}{56}
\parskip=0,3\parskip

\def\[{\{\mskip-6,2mu\{}
\def\]{\}\mskip-6,2mu\}}
\item (0 Punkte)
Eine \emph{Multimenge} (engl.\ \emph{multiset} oder \emph{bag}) ist etwas "Ahnliches wie eine Menge,
au"ser dass Elemente auch mehrfach vorkommen d"urfen.
Die Reihenfolge spielt keine Rolle.
Zum Beispiel ist $\[a,b\] \ne \[a,a,b\] = \[a,b,a\] \ne \[a,a,a,b\]$,
für $a\ne b$.
\begin{enumerate}
\item %(0 Punkte)
Schreiben Sie eine Spezifikation f"ur einen abstrakten Datentyp
von Multimengen "uber der Grundmenge der ganzen Zahlen (\texttt{int}),
die folgende Operationen unterst"utzt:
Erzeugen einer leeren Multimenge;
Einf"ugen und Streichen eines Elementes
(dabei wird die Vielfachheit jeweils um~1 erh"oht beziehungsweise
erniedrigt);
Feststellen der Vielfachkeit eines Elementes.
\item %(4 Punkte)
Geben Sie eine konkrete Darstellung (etwa als Java-Klasse
\texttt{Multimenge}) an.
Beschreiben Sie die Abstraktionsfunktion,
sowie die Invarianten, die die g"ultigen Darstellungen
charakterisieren.
Geben Sie auch die Vorbedingungen f"ur alle Operatiomen an.
(Sie d"urfen dabei vern"unftige Einschr"ankungen f"ur die
verf"ugbaren Operationen machen.)
\item %(0 Punkte)
Implementieren Sie die Operationen.
Sie k"on"-nen von der in der Vorlesung besprochenen
Implementierung f"ur Mengen mit bis zu 100~Elementen\footnote
{\tt{http://www.inf.fu-berlin.de/\char`\~rote/Lere/2003-04-WS/Algorithmen+Programmierung3/%
Menge.java}}
 ausgehen.
\item %(0 Punkte)
Beweisen Sie die Korrektheit Ihrer Implementierung.
\end{enumerate}

% \item (0 Punkte)
% Konstruieren Sie einen optimalen bin"aren Code-Baum 
% (Huffman-Baum)
% f"ur $n=15$ Knoten
% mit den H"aufigkeiten $p_i=1/i$, $(i=1,\ldots,15)$.

\item (11 Punkte)
Betrachten wir die Knoten $v$ eines Graphen in der Reihenfolge,
wie der rekursive Aufruf $T(v)$ bei der Tiefensuche \emph{beendet} wird.
Das heißt, wir fügen \emph{am Ende} des Programms $T(v)$ folgende
Zeile ein:
%\begin{quote}
$$  \hbox{\texttt{num2++; T2Nummer[v] := num2; }}
$$%\end{quote}
\begin{enumerate}
\item (4 Punkte) Beweisen Sie:
Wenn es eine Kante $(u,v)$ mit T2Nummer$[v]>{}$T2Nummer$[u]$ gibt,
dann enthält der Graph einen Kreis.
\item (4 Punkte)
Wie kann man diesen Kreis bestimmen? Schreiben Sie ein Programmstück
für diese Aufgabe.
\item (3 Punkte)
Verwenden Sie die Tatsache aus Aufgabe (a), um aus der T2Nummerierung eines
kreisfreien Graphen eine topologische Sortierung zu berechnen,
sofern bei der Tiefensuche alle Knoten besucht werden.
Beschreiben Sie den Algorithmus in Worten.
\end{enumerate}


\item (0 Punkte)
Bei der Tiefensuche werden möglicherweise nicht alle Knoten des
Graphen besucht.
%
Was muss man tun, damit das Verfahren der vorigen Aufgabe immer funktioniert?

\item (0 Punkte)
Zeigen Sie, wie man Tiefensuche ohne Rekursion sehr einfach mit einem
Stapel für noch zu bearbeitende \emph{Kanten} implementieren kann.

% \item (0 Punkte)
% Eine Zeichenkette $p_1p_2\ldots p_m$ hei"st
% \emph{periodisch} mit Periode $k$, ($1\le k \le m$) wenn
% $p_i=p_{i+k}$ f"ur $1\le i<i+k\le m$ ist,
% mit anderen Worten, wenn
% $$p_1\ldots p_{m-k} = p_{k+1}\ldots p_m$$
% ist. (F"ur $k=m$ ist die Folge unperiodisch.)
% Bestimmen Sie die Periode
% f"ur das Muster
% $ababcababcabab$.

\item (9 Punkte)
Betrachten Sie das folgende einfache Haskell-Programm:

{\tt \def\_{\char`\_{}}\advance \leftskip by 7mm
camba [ ] \_ = True
\\
camba \_ [ ] = False
\\
camba (x:xs) (y:ys) = (x==y) \&\& camba xs ys
\\
klungo [ ] \_ = True
\\
klungo \_ [ ] = False
\\
klungo xs (y:ys) = camba xs (y:ys) || klungo xs ys

}

\begin{enumerate}

\item (1 Punkt)
Beschreiben Sie in Worten,
was diese beiden Funktionen berechnen.

\item (4 Punkte)
Spezifizieren Sie die beiden Funktionen mathematisch (modellierend).

\item (4 Punkte)
Wie viele Vergleiche der Form \texttt{x==y} werden bei den
folgenden Eingaben durchgef"uhrt?

{\tt \originalTeX \advance \leftskip by 7mm
klungo "aaaab" "aaaaaaaaaa"

klungo "abababc" "bababababa"

}

\end{enumerate}


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