1 \documentclass[a4paper,11pt,twoside]{article}
3 \usepackage[ngerman]{babel}
4 \usepackage[T1]{fontenc}
5 \usepackage[latin1]{inputenc}
6 \usepackage[colorlinks=true,linkcolor=black]{hyperref}
8 \usepackage{vaucanson-g}
14 \usepackage[cm]{fullpage}
15 \usepackage{amsthm, amsmath, amsfonts}
22 % Festlegung Art der Zitierung - Havardmethode: Abkuerzung Autor + Jahr
23 \bibliographystyle{alphadin}
25 \title{\underline{Exzerpt Algorithmentheorie WS10/11}}
26 \author{Markus Lindenmann}
35 \section{Einleitung}\label{sec:intro}
36 Dozent: Matthias Westermann\\
37 Website: \url{http://lak.informatik.uni-freiburg.de}\\
39 Hilfsmittel: Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt
42 \item[$\bullet$] Divide and Conquer
43 \item[$\bullet$] Greedy Prinzip
44 \item[$\bullet$] Dynamische Programmierung
45 \item[$\bullet$] Randomisierung
46 \item[$\bullet$] Amortisierte Analyse
48 \subsection{Problem-/Anwendungsbereiche:}
50 \item[$\bullet$] Geometrische Algorithmen
51 \item[$\bullet$] Algebraische Algorithmen
52 \item[$\bullet$] Graphenalgorithmen
53 \item[$\bullet$] Datenstrukturen
54 \item[$\bullet$] Internet-Algorithmen
55 \item[$\bullet$] ptimierungs-Verfahren
56 \item[$\bullet$] Zeichenkettenverarbeitung
58 \subsection{Literatur:}
59 \bibliography{literatur}
63 \section{Divide and Conquer}\label{sec:div&conq}
65 \item[$\bullet$] Quicksort
66 \item[$\bullet$] Formulierung und Analyse des Prinzips
67 \item[$\bullet$] Geometrisches Devide and Conquer
70 \item[-] Segmentschnitt
74 \subsection{Formulierung des Divide and Conquer Prinzips}
75 D\&C Verfahren zur Lösung eines Problems der Größe $n$
77 \item[1.] Divide\\$n>2$: Teile das Problem in $k$ Teilprobleme der Größe $n_1,\ldots n_k$ ($k\geq2$)\\$n\leq c:$ Löse das Problem direkt
78 \item[2.] Conquer\\Löse die $k$ Teilprobleme auf dieselbe Art (rekursiv)
79 \item[3.] Merge\\Füge die berechneten Teillösungen zu einer Gesamtlösung zusammen
82 \subsection{Quicksort}
83 Wähle beliebiges Pivot Element $v$ und sortiere alle Elemente aus der Menge, die größer sind als $v$ rechts von $v$ ein, die anderen links. Verfahre im selben Muster mit den neuen Teilmengen links und rechts des Pivot Elements. Wenn die zu sortierende Folge $F$ nur ein Element beinhaltet, gebe $F$ zurück.
85 \subsubsection{Analyse}
86 $T(n)$ - maximale Anzahl von Schritten, um ein Problem der Größe $n$ zu lösen.
87 \[T(n)=\begin{cases}n\neq c&a \\ n>c&T(n_1+\ldots+T(n_k)+\text{Divide- und Mergeaufwand}\end{cases}\]
88 Best Case: $k=2, n_1=n_2=\frac{n}{2}$\\
89 Divide- und Mergeaufwand: $DM(n)$\\
91 $T(n)=2T(\frac{n}{2})+DM(n)$
93 \subsection{Nächste Paare}
94 Eingabe: $n$ Punkte in Ebene\\
95 Ausgabe: Punkt-Paar $q,r$ mit geringstem Abstand\\
96 Abstand: $d(q,r)$ bechreibt Abstand zwischen Punkten $q$ und $r$
97 \subsubsection{Algorithmus}
99 \item[$\bullet$] sortiere Punktmenge nach x-Koordinate
100 \item[$\bullet$] Teile Punktmenge in der Mitte L in die Mengen Q und R
101 \item[$\bullet$] Löse rekursiv auf Q und R
102 \item[$\bullet$] Sortiere Punkte nach y-Koordinate
103 \item[$\bullet$] Teste alle Paare, deren Abstand in der Sortierung kleiner als 16 ist (siehe unten)
104 \item[$\bullet$] Füge zusammen
107 $\delta=$ Minimum der Teillösungen\\
108 Gibt es $q\in Q$ und $r\in R$ mit $d(q,r)<\delta$, dann sind sowohl $q$ als auch $r$ höchstens $\delta$ von $L$ (Mitte) entfernt.\\
109 \textbf{Problem:} alle Punkte können innerhalb der $\delta$-Zone liegen\\
110 \textbf{Lösung:}\begin{itemize}
111 \item[$\bullet$] Sortiere Punkte in $\delta$ Zone nach $y$-Abstand
112 \item[$\bullet$] Liegen in dieser Sortierung mehr als $c$ Punkte zwischen $q$ und $r$, dann kann $(q,r)$ nicht nächstes Paar sein
115 Dies kann für $c=15$ bewiesen werden (vgl. Abbildung \ref{cl_pair}):
117 \item[$\bullet$] Seien min. 15 Punkte zwischen $q$ und $r$
118 \item[$\bullet$] Dann sind mindestens 3 Reihen Quadrate zwischen $q,r$, weil in jedem Quadrat höchstens ein Punkt ist.
119 \item[$\rightarrow$] Dann muss $d(q,r)$ mindestens $\frac{3}{2}\delta > \delta$ sein.
124 \includegraphics[scale=0.5]{img/cl_pair}
125 \caption{Nächste Paare: Prüf Distanz}
129 \subsubsection{Analyse}
130 \[T(n)=\begin{cases}n\leq3&a \\ n>3&2T(\frac{n}{2})+an\end{cases}\]
131 \[T(n)\leq an \log n \]
133 \subsection{Segmentschnitt}
134 Eingabe: Menge S bestehend aus vertikalen Segmenten und Endpunkten vn horizontalen Segmenten\\
135 Ausgabe: Alle Schnittpunkte von vertikalen Segmenten mit horizontalen Segmenten, von denen mindesens ein Endpunkt in S ist
137 \subsubsection{Algorithmus}
138 \textbf{Divide \& Conquer:}\\Fallunterscheidung
140 \item[1.] $\left| S\right| > 1$:\\ Teile S mittels einer vertikalen Gerade G in 2 gleichgroße Mengen $S_1$ (links von G) und $S_2$ (rechts von G). Führe rekursiv auf beiden Hälften aus.
141 \item[2.] else: S enthält keine Schnitte
145 Bilde L(S), R(S) und V(S) (Definition am Beispiel $i=1,2$ berechnet: $S=S_1\cup S_2$):
147 \item[$\bullet$] L(S): y-Koordinate aller linken Endpunkte in S, deren rechter Partner nicht in S\\$=L(S_2)\cup(L(S_1)-R(S_2))$
148 \item[$\bullet$] R(S): y-Koordinate aller rechten Endpunkte in S, deren linker Partner nicht in S\\$=R(S_1)\cup(R(S_2)-L(S_1))$
149 \item[$\bullet$] V(S): y-Intervalle der vertikalen Segmente in S\\$=V(S_1)\cup V(S_2)$
151 L,R sortiert nach steigender y-Koordinate\\
152 V sortiert nach steigendem unteren Endpunkt\\
155 \textbf{Basisfälle}\\
156 S enthält nur ein Element s. Fallunterscheidung:
158 \item[1.] $s=(x,y)$ ist ein linker Endpunkt:\\$L(S)=\{y\},\qquad R(S)=\emptyset,\qquad V(S)=\emptyset$
159 \item[2.] $s=(x,y)$ ist ein rechter Endpunkt:\\$L(S)=\emptyset,\qquad R(S)=\{y\},\qquad V(S)=\emptyset$
160 \item[3.] $s=(x,y_1,y_2)$ ist ein vertikales Segment:\\$L(S)=\emptyset,\qquad R(S)=\emptyset,\qquad V(S)=\{[y_1,y_2]\}$
163 \subsubsection{Analyse}
164 Eingabe wird Anfangs sortiert und in Array gespeichert
165 \[T(n)=2T(\frac{n}{2}+an+\text{Größe der Ausgabe}\]
167 \[O(n \log n + k \mid k=\#Schnittpunkte\]
169 \subsection{Polynomprodukt und Fast Fourier-Transformation}
173 \section{Randomisierung}
177 \section{Amortisierte Analyse}
178 \subsection{Binomial Heaps}
179 \subsection{Fibonacci Heaps}
180 \subsection{Union Find}
184 \subsection{Kürzeste (billigste) Wege}
187 \section{Bin Packing}
188 \textbf{Problembeschreibung:}\\
189 Man hat $n$ Objekte verschiedener Größe mit $0<s_i\leq1\mid 1\leq i\leq n$. Gesucht ist die kleinst mögliche Anzahl an Kisten (Bins) der Größe 1, mit der alle Objekte verpackt werden können.
190 \subsection{Online Verfahren}
191 Jedes (ankommende) Objekt muss verpackt sein, bevor das nächste Objekt betrachtet wird. Ein Objekt verbleibt in derjenigen Kiste, in die es zuerst gepackt wird.\\
192 Kein Online Bin Packing Verfahren kann stets eine optimale Lösung finden!\\
193 \textbf{Satz 1}: Es gibt Eingaben, die jeden Online Bin Packing Algorithmus zwingen, wenigstens $\frac{4}{3} OPT$ Bins zu verwenden, wobei $OPT$ die minimal mögliche Binzahl ist.\\
194 \textbf{Beweis} Annahme: Online Bin Packing Algorithmus benötigt stets weniger als $\frac{4}{3}OPT$ Bins.\\
195 Es wird eine Eingabe mit $2m$ Objekten angenommen. Die ersten $m$ sind um $\epsilon$ kleiner als $\frac{1}{2}$, die zweiten $m$ um $\epsilon$ größer. Die optimale Lösung sind $m$ Kisten, da immer ein großes mit einem kleinen Paket kombiniert werden kann. Nun teilt man die Analyse in zwei Zeitpunkte: nach $m$ Objekten und nach $2m$ Objekten. Laut Annahme gilt nach nach $m$ Objekten, dass die Anzahl der Bins $b$ nur maximal $\frac{4}{3} OPT$ groß sein darf. Mit $OPT=\frac{m}{2}$ gilt somit: $b=\frac{4}{3}\cdot\frac{m}{2}=\frac{2}{3}m$. Sei $b=b_1+b_2\mid b_1=\#$Bins mit einem Objekt, $b_2=\#$Bins mit zwei Objekten, so folgt $b_1+2b_2=m\implies b_1=m-2b_2\implies b=b_1+b_2=m-b_2$. Nach $2m$ Objekten ist $OPT=m$, wie zuvor beschrieben. $b_1$ Bins können zu diesem Zeitpunkt mit Objekten des zweiten Bereichs gefüllt werden, für die verbleibenden muss man neue Bins öffnen. Die Anzahl der neu zu öffnenden beträgt damit genau $b_2\implies \#$Bins $\geq b+m-b_1=m+b_2$. Die Annahme besagt $m+b_2\leq\#$Bins $<\frac{4}{3}m \wedge b_2<\frac{m}{3}$. Dies ist nur möglich, wenn $b=m-b_2>\frac{2}{3}m$ - Dies führt zu einem \underline{Widerspruch}, da $b$ zum Zeitpunkt 1, nach $m$ Objekten $<\frac{2}{3}m$ sein muss.
197 \subsubsection{Next Fit (NF)}
198 Verpacke das nächste Objekt in dieselbe Kiste wie das vorherige, wenn es dort noch hineinpasst, sonst öffne eine neue Kiste und verpacke es dort.\\
199 \textbf{Satz 2}: (a) Für alle Inputfolgen $I$ gilt: $NF(I)\leq2OPT(I)$. (b) Es gibt Inputfolgen I mit $NF(I)\geq2OPT(I)-2$.\\
201 (a) Betrachte zwei beliebige aufeinanderfolgende Kisten $B_{2k-1}, B_{2k}$. Man weiß, dass die beinhalteten Objekte eine Summengröße $>1$ haben, sonst wären selbige in einer Kiste. Daraus folgt, man kann nicht mehr als die doppelte Anzahl an Kisten als beim Optimum erreichen!\\
202 (b) Inputfolge: $0.5, \frac{2}{n}, 0.5, \frac{2}{n}, 0.5, \frac{2}{n}, \ldots 0.5, \frac{2}{n}$.\\Next-Fit liefert nun immer Bins gefüllt mit $0.5 + \frac{2}{n}$. Darausfolgt $NF(I)=\frac{n}{2}$ und $OPT=\frac{n}{4}+1$ (weil $\frac{n}{2}$ mal 0.5er Objekte in $=\frac{n}{4}$ Kisten passen und $\frac{n}{2}$ $\frac{2}{n}$er Objekte in eine Kiste passen)\\
203 Laufzeit für Inputfolgen der Länge $n$: NF $O(n)$
204 \subsubsection{First-Fit (FF)}
205 Packe nächstes Objekt in die erste Kiste, in die es noch hineinpasst, wenn es eine solche Kiste gibt, sonst in eine neue Kiste.\\
206 \textbf{Beobachtung}: Zu jedem Zeitpunkt kann es höchstens eine Kiste geben, die weniger als halb voll ist. ($\implies FF(I) \leq 2OPT(I)$)\\
207 \textbf{Satz 3}: (a) Für alle Inputfolgen $I$ gilt $FF(I)\leq \lceil\frac{17}{10} OPT(I)\rceil$. (b) Es gibt Inputfolgen $I$ mit $FF(I)\geq\frac{17}{10}(OPT(I)-1)$. (b') Es gibt Inputfolgen $I$ mit $FF(I)=\frac{10}{6}OPT(I)$.\\
209 (b') Inputfolge der Länge $3\cdot6m$. Dabei je $6m$ Objekte der Größen $\frac{1}{7}+\epsilon, \frac{1}{3}+\epsilon, \frac{1}{2}+\epsilon$, welche in gegebener Reihenfolge in Gruppen eingegeben werden. FF liefert hierbei $m$ Kisten gefüllt mit den Objekten der Größe $\frac{1}{7}+\epsilon$ (jeweils 6 pro Kiste) gefolgt von $\frac{6m}{2}=3m$ Kisten gefüllt mit Objekten der Größe $\frac{1}{3}+\epsilon$ (jeweils 2 pro Kiste) und schlussendlich $6m$ Kisten mit je einem Objekt der Größe $\frac{1}{2}+\epsilon$. Das macht in der Summe $10m$ Kisten. Die optimale Lösung packt je ein Objekt jeder Größe in eine Kiste und benötigt somit nur $6m$ Kisten.\\
210 Laufzeit für Inputfolgen der Länge $n$: FF $O(n^2) \rightarrow O(n \log n)$
211 \subsubsection{Best-Fit (BF)}
212 Verpacke das nächste Objekt in diejenige Kiste, in die es am besten passt (d.h. den geringsten Platz ungenutzt lässt).
213 Verhalten von BF ähnlich zu FF.
214 Laufzeit für Inputfolgen der Länge $n$: BF $O(n^2) \rightarrow O(n \log n)$
215 \subsection{Offline Verfahren}
216 \underline{NP-schwieriges Problem! Entscheidungsproblem ist NP-vollständig!}\\
217 Zunächst wird die Anzahl $n$ und alle $n$ Objekte vorgegeben. Dann beginnt die Verpackung.\\
218 $n$ und $s_1, ..., s_n$ sind gegeben, bevor die Verpackung beginnt!\\
219 $\rightarrow$ \underline{Optimale Verpackung} kann durch erschöpfende Suche bestimmt werden. ABER: Benötigt exponentielle Zeit! Daher Approximimationsalgorithmen, die schneller sind aber dafür unter Umständen nicht optimal!\\
220 Idee für Offline Approximationsalgorithmen: Sortiere die Objekte zunächst nach abnhemender Größe und verpacke größere Objekte zuerst!
221 \subsubsection{First Fit Decreasing (FFD oder FFNI)}
222 \textbf{Lemma 1}: Sei $I$ eine Folge von $n$ Objekten mit Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann haben alle von FFD in den Bins $B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackten Objekte eine Größe von höchstens $\frac{1}{3}$.\\
223 \textbf{Beweis}: \$\$\$TODO:Elsässer hat das in seiner VL gemacht - aber hässlich lang\$\$\$\\
224 \textbf{Lemma 2}: Sei $I$ eine Folge von $n$ Objekten mit Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann ist die Anzahl der Objekte, die FFD in die Kisten $B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackt, höchstens $m-1$.\\
225 \textbf{Beweis}: Annahme: Es gibt mehr als $m-1$ Objekte. $x_1,\ldots,x_m$ in $I$, die FFD in extra Kisten verpacken. Dies führt zu einem Widerspruch. \$\$\$TODO:Warum?\$\$\$\\
226 \textbf{Satz}: Für alle Inputfolgen I gilt $FFD(I)\leq(4 OPT(I)+\frac{1}{3})$.\\
229 \item[1.] Für alle Inputfolgen $I$ gilt: $FFD(I)\leq \frac{11}{9} OPT(I)+4$
230 \item[2.] Es gibt Inputfolgen $I$ mit: $FFD(I)=\frac{11}{9}OPT(I)$.
232 \textbf{Beweis}: \$\$\$TODO\$\$\$
233 \subsubsection{Best Fit Decreasing (BFD)}
237 \section{Dynamische Programmierung}
242 \section{Landau-Symbole}
245 \includegraphics[scale=0.45]{img/landau_sym}
246 \caption{Definition der Landau Symbole}
247 \label{fig:landau_sym}