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

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

\flushbottom

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


\begin{enumerate}
\setcounter{enumi}{43}

\item (3 Punkte)
\begin{enumerate}
\item (3 Punkte)
Berechnen Sie die Verschiebefunktion des \emph{Fibonacci-Wortes}
$$aba ab aba aba ab aba ab aba aba ab aba aba ab .$$

\item (0 Punkte)
Berechnen Sie die Verschiebefunktion der \emph{Morse-Folge}
$$0110 1001 1001 0110  1001 0110 0110 1001
  1001 0110 0110 1001  0110 1001 1001 0110 .$$
\end{enumerate}

\item (0 Punkte)
Die verbesserte Verschiebefunktion zum Suchen von Zeichenketten
ist folgenderma"sen definiert:
$$
h[i] = 
% \begin{cases}
\max \ \{\,k\mid 1\le k<i,\ p_1\ldots p_{k-1} = p_{i-k+1}\ldots p_{i-1}
\textrm{ und } p_k \ne p_i \,\}
\cup \{0\}
% end{cases}
$$
\begin{enumerate}
\item % (0 Punkte)
Berechnen Sie die verbesserte Verschiebefunktion der
Muster aus der vorigen Aufgabe.
\item
Zeigen Sie, dass beim Suchen mit der verbesserten
Verschiebefunktion auf keinen Fall mehr Vergleiche der Form
$p_i=s_j$
durchgef"uhrt werden als mit der urspr"unglichen Verschiebefunktion
(ohne die Bedingung  "`$p_k \ne p_i $"').
Gilt dies auch, wenn man den Aufwand an Vergleichen beim Berechnen der
Verschiebefunktion mit ber"ucksichtigt?

Finden Sie ein Beispiel, bei dem tats"achlich weniger
Vergleiche notwendig sind.
\item
Schreiben Sie einen Algorithmus zum Berechnen der verbesserten
Verschiebefunktion.
\end{enumerate}

\item (5 Punkte)
Erweitern Sie den Knuth--Morris--Pratt-Algorithmus so,
dass er \emph{alle} Stellen bestimmt,
an denen das Muster im Text vorkommt.

\def\[{\{\mskip-6,2mu\{}
\def\]{\}\mskip-6,2mu\}}
\item (8 Punkte)
Eine \emph{Multimenge} 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\]$.
\begin{enumerate}
\item (4 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.

\end{enumerate}
\end{document}
