% 11. 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}{12}
\begin{document}

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


\begin{enumerate}
\setcounter{enumi}{61}
%\parskip=0,1\parskip
\item (0 Punkte)
Wie kann man auf einfache Art überprüfen, ob ein Graph, der mit Adjazenzlisten
gespeichert ist, ein \emph{einfacher Graph} ist (keine mehrfachen
Kanten enthält)?
Versuchen Sie, mit $O(m+n)$ Zeit und mit möglichst wenig % $O(n)$ 
zusätzlichem Speicher
auszukommen.


\item  (0 Punkte)
Wenden die den Algorithms von Dijkstra zur Bestimmung der kürzesten
Wege im folgenden gerichteten Graphen an:
$V=\{1,2,\ldots,6\}$,
der Graph ist vollständig, das heißt, von jedem Knoten gibt es eine Kante zu
jedem anderen Knoten, und die Kantenlängen sind
$c_{ij}=3^{j-i}$ für $i<j$ und $c_{ij}=i-j$ für $i>j$.
Der Startknoten ist der Knoten 2.

\item (6 Punkte)
Konstruieren Sie einen Graphen, der auch Kanten mit negativer Länge
enthält, und bei dem der Algorithmus von Dijkstra die kürzesten Wege
nicht richtig bestimmt.
Der Graph soll keine Kreise negativer Länge enthalten.

\item (0 Punkte)
Denken Sie sich einen gierigen Algorithmus aus, der versucht, in einem
Graphen einen kurzen Weg von einem Startknoten $s$ zu einem Zielknoten
$t$ zu finden.
Welche Problem können dabei auftreten?

\item (9 Punkte) Betrachten Sie die Variante einer Halde, bei der
jeder innere Knoten $d\ge 2$ Kinder hat. (Für $d=2$ ergeben sich die
gewöhnlichen Halden aus der Vorlesung.)
Wie verändert sich die Laufzeit für die Methoden \texttt{zugroß} beziehungsweise
 \texttt{zuklein} in Abhängigkeit von~$d$?
Wie wirkt sich das auf die Operationen \emph{einfügen},
\emph{entferneMin} und \emph{verkleinereSchlüssel} aus?

Wenn man eine solche "`$d$-Halde"' für den Algorithmus von Dijkstra
verwendet,
wie muss man dann $d$ in Abhängigkeit von $m$ und $n$ wählen, dass man
die optimale asymptotische Laufzeit erhält? Welche Laufzeit ergibt sich dann für das
kürzeste-Wege-Problem?
Was ergibt sich in den Extremfällen $m=\Theta(n)$ und  $m=\Theta(n^2)$?

\item (0 Punkte) Zeigen Sie, dass der folgende \emph{Algorithmus von Prim} einen
  kürzesten Spannbaum findet:
  \begin{tabbing}
\qquad \=\+
    $G := \{s\}; \ \textit{Abstand\/}[s] := 0;$\\
    $N := V-\{s\};$\\
    \textbf{while} $G \ne \emptyset$ \textbf{do}\\
\qquad \=\+entferne einen Knoten $v$ mit kleinstem $\textit{Abstand\/}[v]$ aus
    $G$;\\
    füge $v$ in $B$ ein;\\
    \textbf{für alle} Kanten $(v,w)\in E$, die von $v$ ausgehen, \textbf{do}\\
\qquad \=\+\textbf{if} $w\in N \mathbin{\textbf{or}} (w\in G 
\mathbin{\textbf{and}} \textit{Abstand\/}[w] > c_{vw}$)\\
\textbf{then} \ \=\+$G := G \cup \{w\}; \ N := N-\{w\};$\\
$\textit{Abstand\/}[w] := c_{vw};$\\
$\textit{Vorgänger\/}[w] := v;$
  \end{tabbing}
Was ist der Unterschied dieses Algorithms zum Algorithmus von Dijkstra
für kürzeste Wege?


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

\item (5 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}
(0 Punkte) Wie gehen die beiden Folgen weiter?

% \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  (freiwillige Zusatzaufgabe, 0 Punkte)
Wie kann man $n$ Brüche, deren Zähler und Nenner zwischen $1$ und $n$
liegen,
in linearer Zeit sortieren?



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

