% 12. 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,5cm
\hoffset = -17mm
\voffset = -30mm

\setcounter{page}{13}
\begin{document}

\parskip=0,1\parskip

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


\begin{enumerate}
\setcounter{enumi}{69}
\parskip=0,1\parskip
\item (7 Punkte) Ein Iterator f"ur Mengen. \vspace{-0,5ex}
\begin{enumerate}
\item (4 Punkte)
Implementieren Sie den \emph{Iterator}, den Sie in Aufgabe~52 spezifiziert haben.
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 (3 Punkte)
Geben Sie die Abstraktionsfunktion an.
\item (5 Zusatzpunkte)
Beweisen Sie die Korrektheit Ihrer Implementierung.
\end{enumerate}

\item (3 Punkte) 
Gegeben sei ein vollst"andiger%
\footnote{Ein Graph ist \emph{vollst"andig}, wenn zwischen
allen Paaren von Knoten eine Kante verl"auft.}
Graph $G=(V,E)$, dessen Knoten $V$ Punkte in der Ebene sind,
und wo die Kantenl"angen den (Euklidischen) Abst"anden zwischen den
Punkten entsprechen.
Beweisen Sie:
\vspace{-0,7ex}\hrule height 0pt
\begin{enumerate}
\itemsep=0,3\itemsep
\item (3 Punkte)
In einem k"urzesten spannenden Baum
k"onnen sich nie zwei Kanten kreuzen.
\item (5 Zusatzpunkte)
In einem k"urzesten-Wege-Baum (mit einem beliebigen Startknoten)
k"onnen sich nie zwei Kanten kreuzen.
\end{enumerate}
\vspace{-0,1ex}\hrule height 0pt
Bleiben diese Aussagen auch g"ultig, wenn der Graph nicht vollst"andig ist?


\item (0 Punkte) Für zwei Wörter $x$ und $y$ der Länge $n$ ist $x$ eine
\emph{zyklische} Verschiebung von $y$, wenn man $x=ab$ und $y=ba$ für
zwei Wörter $a$ und $b$ schreiben kann.
Wie kann man in linearer Zeit feststellen, ob $x$ eine 
{zyklische} Verschiebung von $y$ ist?
(Man kann diese Frage auf das Teilwortproblem zurückführen.)

\item (5 Punkte)
Wie kann man den Algorithmus von Knuth, Morris und Pratt so
  erweitern, dass er \emph{alle} Vorkommen eines Musters $x$ in einem
  Text $w$ findet? (Man benötigt eventuell den Wert $h_{m+1}$ der
  Verschiebefunktion, für $m=|x|$.)

\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 Aufgabe 68.
\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 (0 Punkte)
Wie kann man aus der Verschiebefunktion des Wortes $xw\$$ berechnen,
ob $x$ ein Teilwort von $y$ ist? (Hier ist \$ irgendein Buchstabe.)

\item (0 Punkte)
Welche Bedeutung hat die Fl"achenformel
$\frac12 \cdot \left| \sum_i (x_iy_{i+1}-y_ix_{i+1}) \right| $,
wenn die Folge der Punkte $(x_i;y_i)$ gar kein Polygon beschreibt,
weil sich zum Beispiel Kanten kreuzen?

\item
\begin{enumerate}
\item (5 Punkte)
Berechnen Sie die Fl"ache des F"unfecks\footnote
{\tt{http://www.inf.fu-berlin.de/\char`\~rote/Lere/2003-04-WS/Algorithmen+Programmierung3/%
5eck}} mit den Ecken
$( -1{,}3; 10000{,}12)$,
$( -0{,}253; 10000{,}47)$,
$( 0{,}69; 10000{,}33)$,
$(1{,}529; 10002{,}12)$,
$( -0{,}783; 10001{,}05)$
mit der Formel aus der vorigen Aufgabe.
Berechnen Sie auch den Fl"acheninhalt des um den Vektor $(0;-10000)$
verschobenen F"unfecks.
Welches Ergebnis halten Sie f"ur das genauere?
Begr"unden Sie Ihre Antwort.
\item (0 Punkte)
Was passiert, wenn man das F"unfeck um den Vektor $(10000;-10000)$
verschiebt? Wie erkl"aren Sie diese Ergebnisse?
\end{enumerate}


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

