% 10. Uebungsblatt ALP3 WS 1999/2000
\documentclass [11pt] {article}
\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\textwidth=16cm
\textheight=26,9cm
\hoffset = -23mm
\voffset = -35mm

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

\begin{centering}
{\large \bf Algorithmen
und Programmieren III, WS 1999/2000 ---
 10.~\"Ubungsblatt\par
}
\bigskip
Abgabe bis Dienstag, 1. Feber 2000.
\par \medskip
\end{centering}
\hrule
\medskip

\begin{enumerate}
\setcounter{enumi}{48}

\item (12 Punkte)
Betrachten Sie die folgende Haskell-Funktion:

{\tt \def\_{\char`\_{}}\advance \leftskip by 2em
istTeil (x:xs) (y:ys)
 = ( (x==y) \&\& istTeil xs ys)  ) || istTeil (x:xs) ys
 \\
istTeil [] \_ = True
\\
istTeil (\_:\_) [] = False
}
\begin{enumerate}
\item (5 Punkte) Geben Sie (formal oder umgangssprachlich, aber pr"azise)
an, was die Funktion \texttt{istTeil} berechnet.
\item (0 Punkte) Bestimmen Sie experimentell oder durch Analyse die Laufzeit der Funktion
in Abh"angigkeit von der L"ange der Argumente.
F"ur welche Argumente dauert die Berechnung der Funktion am l"angsten?
\item (0 Punkte) Untersuchen Sie die vorige Frage auch f"ur die Variante,
wo die beiden Teile der Disjunktion (\texttt{||}) in der ersten Zeile
vertauscht sind.

\item (3 Punkte)
Beweisen Sie die folgenden logischen Implikationen:
\begin{eqnarray*}
\texttt{istTeil xs ys} &\implies& \texttt{istTeil xs (y:ys)}\\[-3pt]
\texttt{istTeil (x:xs) ys} &\implies& \texttt{istTeil xs ys}
\end{eqnarray*}
% Hinweis: 
(F\"ur die zweite Aussage k\"onnen Sie unter anderem Induktion nach
der L\"ange der Liste im zweiten Argument verwenden.)

\item (4 Punkte) 
Die folgende Variante der
ersten Zeile f"uhrt auf eine "aquivalente Funktion:

{\tt \qquad
istTeil (x:xs) (y:ys)\\
{\null  }\qquad\qquad | x==y \ = istTeil xs ys\\
\null\qquad\qquad | x/=y \ = istTeil (x:xs) ys
}

Erkl\"aren Sie diesen Sachverhalt (in Worten), und beweisen Sie
ihn formal. (Die Aussagen aus der vorigen Aufgabe k\"onnten dabei
hilfreich sein.)
% Sie d\"urfen diese Aussagen aber nur verwenden, wenn
% Sie sie bewiesen haben.)

\item(0 Punkte) 
Untersuchen Sie diese letzte Variante auf ihre Effizienz.

\end{enumerate}


\def \altenummer{39}
\item 
(7 Punkte) Der Computer \textsc{Sumo-1} 
ist eine verbesserte Variante von \textsc{Sumo-0} aus Aufgabe~\altenummer.
Die wichtigste Neuerung ist, dass
eine Variable auch \emph{mehrmals} auf der
linken Seite einer Zuweisung auftreten kann.
Weiters gibt es eine Druck-Anweisung \texttt{P$x$},
die den Inhalt der Variablen \texttt{V$x$} ausdruckt
und das Programm beendet.

Die Programmierung in \textsc{Sumatra} soll durch einen Plausibilit"atstest
% f"ur \textsc{Sumatra}-Programme 
unterst"utzt
werden.
Dazu sollen Anweisungen, die das gedruckte
Endergebnis nicht beeinflussen k"onnen,
 identifiziert werden.
 Schreiben Sie ein Programm f"ur diese Aufgabe.


\item (5 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)
Leiten Sie aus der algebraischen Spezifikation f\"ur Mengen
 \begin{eqnarray*}
\textit{istenthalten}(x,\textit{leer}\/) &=& \textit{falsch} \\
\textit{istenthalten}(x,\textit{einf\"uge}(x,M)) &=& \textit{wahr} \\[-3pt]
\textit{istenthalten}(x,\textit{einf\"uge}(y,M)) &=&
\textit{istenthalten}(x,M), \qquad \textrm{f\"ur $x\ne y$}\\
\textit{istenthalten}(x,\textit{l\"osche}(x,M)) &=& \textit{falsch} \\[-3pt]
\textit{istenthalten}(x,\textit{l\"osche}(y,M)) &=&
\textit{istenthalten}(x,M), \qquad \textrm{f\"ur $x\ne y$}
  \end{eqnarray*}
(mit den Signaturen von \textit{einf\"uge}, 
\textit{l\"osche}, \textit{leer}, und
\textit{istenthalten} wie in der Vorlesung)
durch Umformungen
folgende Identit"at her:
F\"ur $x\ne y$ gilt
$$
\textit{istenthalten}(u,\textit{l\"osche}(x,
\textit{einf\"uge}(y,M))) =
\textit{istenthalten}(u,
\textit{einf\"uge}(y,
\textit{l\"osche}(x,
M))).
$$

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


\end{enumerate}


\end{document}

