% 11. Uebungsblatt ALP3 WS 1999/2000
\documentclass [11pt] {article}
\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\textwidth=15,8cm
\textheight=25,5cm
\hoffset = -22mm
\voffset = -27mm

\setcounter{page}{12}
\begin{document}
\flushbottom
\begin{centering}
{\large \bf Algorithmen
und Programmieren III, WS 1999/2000 ---
 11.~\"Ubungsblatt\par
}
\smallskip
Abgabe bis Donnerstag, 10. Februar 2000

\par \medskip
\end{centering}
\hrule
\smallskip

\begin{enumerate}
\setcounter{enumi}{53}

\item (6 Punkte) Triangulierungen eines konvexen $n$-Ecks;
bin\"are B\"aume mit $n-2$ Knoten. \vspace{-1ex}\hrule height 0pt
\begin{enumerate}
\itemsep=0,3\itemsep
\item (6 Punkte)
Schreiben Sie ein Programm, das alle m"oglichen Gradlisten der
Triangulierungen eines konvexen $n$-Ecks $P_n$ erzeugt und abz"ahlt.
(Dies ist die Umkehrung zu Aufgabe~27d.)
Dokumentieren Sie die Ausgabe f"ur $n=3,4,5,6,7,8$.
Bestimmen Sie f"ur $n=9$ nur die Anzahl.

Ein m"oglicher Zugang ist, aus den Gradlisten f"ur ($n-1$)-Ecke
die Gradlisten f"ur $n$-Ecke zu erzeugen.
Achten Sie darauf, dass Sie Gradlisten nicht mehrfach erzeugen.
Dabei kann es hilfreich sein, die Gradlisten in einen digitalen Suchbaum
(\emph{trie}) zu speichern.

\item (0 Punkte)
Man kann Triangulierungen, die durch Drehungen ineinander "ubergef"uhrt
werden, als "aquivalent betrachten. (Dies entspricht einer zyklischen Verschiebung
der Gradliste.)
Es soll nun aus jeder "Aquivalenzklasse nur ein Repr"asentant erzeugt werden.
(Bei $n=5$ gibt es also nur eine L"osung.)

\item (0 Punkte)
Die \emph{Gradfolge} ist die sortierte Gradliste.
So hat zum Beispiel
jede Triangulierung des $P_5$ die Gradfolge $(0,0,1,1,2)$.
Erzeugen Sie alle m"oglichen Gradfolgen der Triangulierungen
des $n$-Ecks.

\item ($\infty$ Punkte) Schreiben Sie ein effizientes Programm, das testet,
ob eine gegebene Folge $(b_1,\ldots,b_n)$ die
Gradfolge einer Triangulierung ist.

\end{enumerate}

\item (5 Punkte) Ein Iterator f"ur Mengen. \vspace{-0,5ex}
\begin{enumerate}
\item (3 Punkte)
Implementieren Sie den \emph{Iterator}, den Sie in Aufgabe~51 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/alp3/Menge.java}}
 ausgehen.
\item (2 Punkte)
Geben Sie die Abstraktionsfunktion an.
\item (5 Zusatzpunkte)
Beweisen Sie die Korrektheit Ihrer Implementierung.
\end{enumerate}

\item (0 Punkte)
In einem Baum sei $n_i$ die Anzahl der Knoten mit $i$~Kindern,
das hei"st, $n_0$ ist die Anzahl der Bl"atter, usw.
Die Gesamtzahl der Knoten ist $n=n_0+n_1+n_2+n_3+\cdots$.
Beweisen Sie, dass $n\le 2(n_0+n_1)-1$ ist.

\item
\begin{enumerate}
\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 (5 Punkte)
Wie kann man einen optimalen bin"aren Code
(Huffman-Code) in \emph{linearer} Zeit
konstruieren, wenn die H"aufigkeiten $p_i$
in \emph{sortierter} Reihenfolge gegeben sind?
\end{enumerate}

\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 (3 Punkte)
Berechnen Sie die Fl"ache des F"unfecks\footnote
{\tt{http://www.inf.fu-berlin.de/\char`\~rote/Lere/alp3/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?
(Berg"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}

\goodbreak % \itemsep=0,5\itemsep

\item (0 Punkte) Verbesserung des Streckenschnittproblems.
\vspace{-1ex}\hrule height 0pt
\begin{enumerate}
\itemsep=0,3\itemsep
\item Erl"autern Sie, wie man den in der Vorlesung besprochenen
plane-sweep-Algorithmus zum Ausgeben aller $k$ Schnittpunkte von $n$ Strecken
so verbessern kann, dass er nur $O(n)$ Speicher ben"otigt.
(Man muss dazu aus der Ereigniswarteschlange auch zwischendurch Ereignisse
l"oschen.)
\item Wie muss man den Algorithmus modifizieren, dass er auch bei
mehrfachen Schnitten (mehr als zwei Strecken gehen durch einen Punkt)
funktioniert?
\item Erl"autern Sie, welche zus"atzlichen entarteten F"alle
au"ser den eben erw"ahnten Mehrfachschnitten auftreten k"onnen.

\end{enumerate}

\item (0 Punkte) Triangulierung eines ebenen Polygons.\\
Triangulierungen eines konvexen $n$-Ecks sind in Aufgabe~27 definiert
worden.
Triangulierungen eines beliebigen%
\footnote{Wir betrachten nur \emph{einfache} Polygone; das sind solche,
deren Rand eine einzelne geschlossene Kurve ohne Selbst"uberschneidungen
(eine Jordan-Kurve) ist.}
(auch nicht-konvexen) $n$-Ecks sind
genauso definiert.
Eine \emph{Trapezoidierung} eines $n$-Ecks ist eine Zerlegung
der Polygons in Dreiecke und Trapezoide,\footnote
{Ein Trapezoid ist ein Viereck mit zwei parallelen Seiten.}
die dadurch entsteht, dass man von jedem Knoten eine vertikale
Strecke so weit nach oben und nach unten zieht, bis sie eine andere
Polygonseite trifft. Die entstandenen Strecken, die au"serhalb des Polygons liegen,
werden gel"oscht.
\vspace{-1ex}\hrule height 0pt
\begin{enumerate}
\itemsep=0,3\itemsep
\item Zeigen Sie, dass auf diese Art wirklich eine Trapezoidierung entsteht.
\item Entwerfen Sie einen Algorithmus zur Bestimmung einer Trapezoidierung.
(Sie k"on"-nen zum Beispiel dem plane-sweep-Muster folgen.)
\item (5 Zusatzpunkte) Beweisen Sie, dass jedes Polygon trianguliert werden kann.
\item (5 Zusatzpunkte, alternativ zu (c)) Wie kann man aus einer Trapezoidierung eine Triangulierung gewinnen?
\end{enumerate}


\item (4 Punkte)
Bestimmen Sie einen k"urzesten spannenden Baum im vollst"andigen%
%\footnotemark[\value{footnote}]
% \protect\footnotemark[\protect\value{footnote}]
\footnotemark\addtocounter{footnote}{-1}  %[3]
Graphen mit den
Knoten $V=\{5,6,\ldots,15\}$,
wo die L"ange der Kante zwischen den Knoten $i$ und~$j$ gleich das
kleinste gemeinsame Vielfache von $i$ und~$j$ ist.
Ist die L"osung eindeutig?

\item (0 Punkte) Zeigen Sie, dass der folgende Algorithmus einen
 k"urzesten spannenden Baum $T$ in einem zusammenh"angenden
 Graphen $(V,E)$ 
 mit Kantengewichten $w_{ij}$ berechnet:\vspace{-1ex}
 \begin{tabbing}
 \qquad\qquad\=\+ $T := \emptyset$; $S:=V$;
 $u := \textrm {irgendein Knoten aus $V$}$; \\
 $d_u := 0$; $d_v := \infty$ f"ur alle Knoten $v\ne u$, $v \in V$; \\
 \textbf{while} $S\ne\emptyset$ \textbf{do} \\
 \qquad\=\+
   w"ahle ein $i\in S$ mit kleinstem Wert $d_i$;\\
   \textbf{if} $i\ne u$ \textbf{then} $T := T \cup \{(i,f_i)\}$;
   \textbf{end if};\\
   \textbf{f"ur alle} Kanten $(i,j)$, die von $i$ ausgehen \textbf{do}\\
 \qquad\=\+
   \textbf{if} $w_{ij}<d_j$ \textbf{then} $d_j := w_{ij}$; $f_j := i$;
   \textbf{end if};\-\\
   \textbf{end f"ur};\-\\
   \textbf{end while};
\end{tabbing}\vspace{-1ex}
 Worin unterscheidet sich dieser Algorithmus (der "ubrigens auch von
 E. W. Dijkstra stammt) vom Dijkstra-Algorithmus f"ur k"urzeste Wege?
 
 
 
\item (0 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,8ex}\hrule height 0pt
\begin{enumerate}
\itemsep=0,3\itemsep
\item
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,8ex}\hrule height 0pt
Bleiben diese Aussagen auch g"ultig, wenn der Graph nicht vollst"andig ist?

\end{enumerate}
\end{document}

