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

\setcounter{page}{10}
\begin{document}

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


\begin{enumerate}
\setcounter{enumi}{51}
\parskip=0,5\parskip

\item (6 Punkte)
Erweitern Sie die Spezifikation f\"ur den abstrakten Datentype
\emph{Menge} (von ganzen Zahlen)
aus der Vorlesung
mit den Operationen Einf\"ugen, Entfernen, Elementtest, und
Erstellen einer leeren Menge um
das Erstellen eines \emph{Iterators} mit den Operationen
\emph{next} und \emph{hasNext} (wie im Java-Interface \texttt{Iterator}).
Spezifizieren Sie diese Operationen formal.


\item (0 Punkte)
Erweitern Sie die algebraische Spezifikation von
Mengenoperationen aus Aufgabe 43
um die Funktionen \textit{Vereinigung} und \textit{Durchschnitt}
(von je zwei Mengen).


\item (0 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}


\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.
% \item %(0 Punkte)
% Beweisen Sie die Korrektheit Ihrer Implementierung.
% \end{enumerate}

\item (0 Punkte)
Schreiben Sie eine Spezifikation f"ur \emph{Intervallarithmetik}.\\
Intervallarithmetik liefert verl"assliche Ergebnisse,
selbst wenn die Eingabedaten mit Mess"-fehlern behaftet sind
und zwischendurch Rechenfehler auftreten.
Statt mit Zahlen rechnet man mit Intervallen $[a,b]$, die
durch die arithmetischen Grundoperationen, $+$, $-$, $\times$ und $:$
miteinander verkn"upft und miteinander verglichen werden k"onnen
(durch $<$, $>$, $\le$, usw.)
Das Ergebnis ist wieder eine Intervall.

% \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 (14 Punkte)
Graphenalgorithmen in der k"unstlichen Intelligenz.  % \\
Die folgende Aufgabe findet sich in einer Sammlung von Rechenaufgaben
mit dem Titel \emph{Propositiones ad acuendos juvenes} (Aufgaben 
zur Sch"arfung des Geistes der Jugend),
die wahrscheinlich
um das Jahr 800 am Hof Karls des Gro"sen entstanden ist
und Alkuin von York zugeschrieben wird:

%\begin{quote}
Die Aufgabe vom Wolf, der Ziege und dem Kohlkopf.
Ein Mann musste einen Wolf, eine Ziege und einen
Kohlkopf "uber einen Fluss "ubersetzen;
er konnte aber nur ein Boot auftreiben, das 
gerade zwei von ihnen tragen konnte.
Wie konnte er alles unversehrt hin"uberbringen?%
\footnote{PROPOSITIO DE LUPO ET CAPRA ET FASCICULO CAULI.
Homo quidam debebat ultra fluvium transferre 
lupum et capram et fasciculum cauli, 
et non potuit aliam navem invenire, 
nisi quae duos tantum ex ipsis ferre valebat. 
Praeceptum itaque ei fuerat, ut omnia haec ultra 
omnino illaesa transferret. 
Dicat, qui potest, quomodo eos illaesos ultra transferre potuit.
SOLUTIO.
Simili namque tenore ducerem prius capram et dimitterem 
foris lupum et caulum. 
Tum deinde venirem lupumque ultra transferrem, 
lupoque foras misso rursus capram navi receptam ultra reducerem, 
capraque foras missa caulum transveherem ultra, 
atque iterum remigassem, capramque assumptam ultra duxissem. 
Sicque faciente facta erit remigatio salubris absque voragine lacerationis.
}
%\end{quote}
\begin{enumerate}
\item
Modellieren Sie diese Aufgabe durch einen Graphen.
Die \emph{Knoten} sollen den m"oglichen Zust"anden
des "`Systems"' Mann--Ziege--Wolf--Kohlkopf--Boot--Fluss
entsprechen, und die \emph{Kanten} den erlaubten "Uberg"angen:
Zum Beispiel w"urde der Wolf die Ziege oder die Ziege den Kohlkopf
fressen, wenn sie ohne Aufsichtig gelassen w"urden;
der Mann, der das Boot rudert, kann nur einen Gegenstand oder
ein Tier zus"atzlich mitnehmen.
%
Eine \emph{L"osung} soll einem \emph{Weg} in diesem Graphen entsprechen.
\item
Schreiben Sie ein Programm, das diesen Graphen erstellt.
Wie viele Knoten und wie viele Kanten hat der Graph?
% \item
Schreiben Sie eine Programm, das mit Breitensuche einen Weg in diesem
Graphen findet, der einer L"osung des Problems entspricht.
\item (0 Punkte)
Ist die L"osung eindeutig?
Wie kann man feststellen, ob es in einem Graphen nur einen einzigen Weg von $s$ nach 
$t$ gibt?
\end{enumerate}

\end{enumerate}
\end{document}
