1 \documentclass[a4paper,11pt,twoside]{article}
3 \usepackage[ngerman]{babel} \usepackage[T1]{fontenc}
4 \usepackage[latin1]{inputenc}
5 \usepackage[colorlinks=true,linkcolor=black]{hyperref}
7 \usepackage{vaucanson-g}
13 \usepackage[cm]{fullpage}
14 \usepackage{amsthm, amsmath, amsfonts}
21 \bibliographystyle{alphadin}
23 \title{\underline{Exzerpt Algorithmentheorie WS10/11}}
24 \author{Markus Lindenmann}
30 \tableofcontents \newpage
32 \section{Einleitung}\label{sec:intro}
33 Dozent: Matthias Westermann\\
34 Website: \url{http://lak.informatik.uni-freiburg.de}\\
36 Hilfsmittel: Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt
39 \item[$\bullet$] Divide and Conquer
40 \item[$\bullet$] Greedy Prinzip
41 \item[$\bullet$] Dynamische Programmierung
42 \item[$\bullet$] Randomisierung
43 \item[$\bullet$] Amortisierte Analyse
45 \subsection{Problem-/Anwendungsbereiche:}
47 \item[$\bullet$] Geometrische Algorithmen
48 \item[$\bullet$] Algebraische Algorithmen
49 \item[$\bullet$] Graphenalgorithmen
50 \item[$\bullet$] Datenstrukturen
51 \item[$\bullet$] Internet-Algorithmen
52 \item[$\bullet$] Optimierungs-Verfahren
53 \item[$\bullet$] Zeichenkettenverarbeitung
55 \subsection{Literatur:}
56 \bibliography{literatur}
60 \section{Divide and Conquer}\label{sec:div&conq}
62 \item[$\bullet$] Quicksort
63 \item[$\bullet$] Formulierung und Analyse des Prinzips
64 \item[$\bullet$] Geometrisches Devide and Conquer
67 \item[-] Segmentschnitt
71 \subsection{Formulierung des Divide and Conquer Prinzips}
72 D\&C Verfahren zur Lösung eines Problems der Größe $n$
74 \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
75 \item[2.] Conquer\\Löse die $k$ Teilprobleme auf dieselbe Art (rekursiv)
76 \item[3.] Merge\\Füge die berechneten Teillösungen zu einer Gesamtlösung zusammen
79 \subsection{Quicksort}\label{ch:qs}
80 Wähle beliebiges Pivot Element $v$ (meist das letzte Element in der
81 Input-Folge!) und sortiere alle Elemente aus der Menge, die größer sind als $v$
82 rechts von $v$ ein, die anderen links. Verfahre im selben Muster mit den neuen
83 Teilmengen links und rechts des Pivot Elements. Wenn die zu sortierende Folge
84 $F$ nur ein Element beinhaltet, gebe $F$ zurück.
85 \subsubsection{Algorithmus}
86 \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus Quicksort,
87 captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
88 basicstyle=\footnotesize]{./code/quicksort.code}
90 \subsubsection{Analyse}
91 $T(n)$ - maximale Anzahl von Schritten, um ein Problem der Größe $n$ zu lösen.
92 \[T(n)=\begin{cases}n\neq c&a \\ n>c&T(n_1+\ldots+T(n_k)+\text{Divide- und Mergeaufwand}\end{cases}\]
93 Best Case: $k=2, n_1=n_2=\frac{n}{2}$\\
94 Divide- und Mergeaufwand: $DM(n)$\\
96 $T(n)=2T(\frac{n}{2})+DM(n)$
98 \subsection{Nächste Paare}
99 Eingabe: $n$ Punkte in Ebene\\
100 Ausgabe: Punkt-Paar $q,r$ mit geringstem Abstand\\
101 Abstand: $d(q,r)$ bechreibt Abstand zwischen Punkten $q$ und $r$
102 \subsubsection{Algorithmus}
104 \item[$\bullet$] sortiere Punktmenge nach x-Koordinate
105 \item[$\bullet$] Teile Punktmenge in der Mitte L in die Mengen Q und R
106 \item[$\bullet$] Löse rekursiv auf Q und R
107 \item[$\bullet$] Sortiere Punkte nach y-Koordinate
108 \item[$\bullet$] Teste alle Paare, deren Abstand in der
109 Sortierung kleiner als 16 ist (siehe unten)
110 \item[$\bullet$] Füge zusammen
113 $\delta=$ Minimum der Teillösungen\\
114 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.\\
115 \textbf{Problem:} alle Punkte können innerhalb der $\delta$-Zone liegen\\
116 \textbf{Lösung:}\begin{itemize}
117 \item[$\bullet$] Sortiere Punkte in $\delta$ Zone nach $y$-Abstand
118 \item[$\bullet$] Liegen in dieser Sortierung mehr als $c$ Punkte zwischen $q$ und $r$, dann kann $(q,r)$ nicht nächstes Paar sein
121 Dies kann für $c=15$ bewiesen werden (vgl. Abbildung \ref{cl_pair}):
123 \item[$\bullet$] Seien min. 15 Punkte zwischen $q$ und $r$
124 \item[$\bullet$] Dann sind mindestens 3 Reihen Quadrate zwischen $q,r$, weil in jedem Quadrat höchstens ein Punkt ist.
125 \item[$\rightarrow$] Dann muss $d(q,r)$ mindestens $\frac{3}{2}\delta > \delta$ sein.
130 \includegraphics[scale=0.5]{img/cl_pair}
131 \caption{Nächste Paare: Prüf Distanz}
135 \subsubsection{Analyse}
136 \[T(n)=\begin{cases}n\leq3&a \\ n>3&2T(\frac{n}{2})+an\end{cases}\]
137 \[T(n)\leq an \log n \]
139 \subsection{Segmentschnitt}
140 Eingabe: Menge S bestehend aus vertikalen Segmenten und Endpunkten vn horizontalen Segmenten\\
141 Ausgabe: Alle Schnittpunkte von vertikalen Segmenten mit horizontalen Segmenten, von denen mindesens ein Endpunkt in S ist
143 \subsubsection{Algorithmus}
144 \textbf{Divide \& Conquer:}\\Fallunterscheidung
146 \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.
147 \item[2.] else: S enthält keine Schnitte
151 Bilde L(S), R(S) und V(S) (Definition am Beispiel $i=1,2$ berechnet: $S=S_1\cup S_2$):
153 \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))$
154 \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))$
155 \item[$\bullet$] V(S): y-Intervalle der vertikalen Segmente in S\\$=V(S_1)\cup V(S_2)$
157 L,R sortiert nach steigender y-Koordinate\\
158 V sortiert nach steigendem unteren Endpunkt\\
161 \textbf{Basisfälle}\\
162 S enthält nur ein Element s. Fallunterscheidung:
164 \item[1.] $s=(x,y)$ ist ein linker Endpunkt:\\$L(S)=\{y\},\qquad R(S)=\emptyset,\qquad V(S)=\emptyset$
165 \item[2.] $s=(x,y)$ ist ein rechter Endpunkt:\\$L(S)=\emptyset,\qquad R(S)=\{y\},\qquad V(S)=\emptyset$
166 \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]\}$
169 \subsubsection{Analyse}
170 Eingabe wird Anfangs sortiert und in Array gespeichert
171 \[T(n)=2T(\frac{n}{2}+an+\text{Größe der Ausgabe}\]
173 \[O(n \log n + k \mid k=\#Schnittpunkte\]
175 \subsection{Polynomprodukt und Fast Fourier-Transformation (TODO)}
179 \section{Randomisierung}
181 \item Klassen von randomisierten Algorithmen
183 \item \textbf{Las Vegas}: \underline{immer} Korrekt, erwartete Laufzeit
184 (randomisierter Qicksort)
185 \item \textbf{Monte Carlo}: \underline{wahrscheinlich} (MC:mostly correct)
186 Korrekt, garantierte Laufzeit (randomisierter Primzahltest)
188 \item Randomisierter Quicksort
189 \item Randomisierter Primzahltest
192 \subsection{Randomisierter Quicksort}
193 Refer to \ref{ch:qs} for basic description of the algorithm.\\
194 Problem von Quicksort: bisher nimmt Quicksort immer das letzte Element in der
195 Folge $\implies$ Worst-Case: sortierte Folge als Eingabe ($\Theta(n^2)$).
196 Ziel: keine quadratische Laufzeit.\\
197 Lösung: randomisierte Auswahl des Pivotelements an Stelle $i$. Anschließend
198 tauschen von Position $i$ und $r$ (mit $r$=rechte Grenze des zu sortierenden
200 \subsubsection{Analyse}
201 \textbf{Analyse 1: erwartete Laufzeit}\\
202 Mit Wahrscheinlichkeit $\frac{1}{n}$ wird das $i$-kleinste Element $S_i$
203 gewählt wobei $n$ zu sortierenden Elemente vorhanden sind. Abhängig von der
204 Wahl von $S_i$ ergeben sich Teilprobleme der Größe $i-1$ und $n-i$. Damit
205 ergibt sich für die Laufzeit $T(n)$.
206 \[T(n)=\frac{1}{n}(T(0)+T(n-1))+\frac{1}{n}(T(1)+T(n-2))+\ldots+\frac{1}{n}(T(k-1)+T(n-k))+\ldots+\]
207 \[\frac{1}{n}(T(n-1)+T(0))+\Theta(n))\mid
208 \Theta(n)\text{ für partition}\]
209 \[=\frac{1}{n}\sum_{k=1}^n(T(k-1)+T(n-k))+\Theta(n)\]
210 \[\frac{2}{n}\sum_{k=1}^nT(k-1)+\Theta(n)\]
212 \textbf{Analys 2: Erwartete Anzahl der Vergleiche}\\
215 1&\text{falls }S_i\text{ mit }S_j\text{ verglichen wird}\\
218 \[E\left[\sum_{i=1}^n\sum_{j>1}x_{ij}\right]=\sum_{i=1}^n\sum_{j>1}E[x_{ij}]\]
219 $p_{ij} =$ Wahrscheinlichkeit $S_i$ wird mit $S_j$ verglichen
220 \[E[x_{ij}=1\cdot p_{ij}+0\cdot(1-p_{ij}=p_{ij}\]
221 \subsection{Randomisierter Primzahltest (TODO)}
222 %TODO schnelle exponentiation
223 \subsection{RSA (TODO)}
226 \subsection{Treaps (TODO)}
227 %TODO haben wir nicht so im detail gemacht wie Elsässer!
228 \subsection{Hashing (TODO)}
232 \section{Amortisierte Analyse (TODO)}
234 \subsection{Binomial Heaps (TODO)}
236 \subsection{Fibonacci Heaps (TODO)}
238 \subsection{Union Find (TODO)}
243 Momentan beste Teillösung wählen. Die Summe dieser optimalen Teillösung ergibt
244 die gesamt Lösung. Möglicher Zustand der Gesamtlösung:
246 \item Wir erhalten die optimale Gesamtlösung.
247 \item Wir erhalten eine Lösung, die zwar nicht immer optimal ist, aber vom
248 Optimum stets nur wenig abweicht.
249 \item Die berechnete Lösung kann beliebig schlecht werden.
251 \underline{Beispiele:}
253 \item Münzwechselproblem\\\textbf{Ziel:} Bezahlung eines Betrages in möglichst
254 wenig Münzen und Banknoten.\\\textbf{Lösung (Greedy):} Wähle die maximale
255 Anzahl von Banknoten und Münzen mit jeweils größtmöglichem Wert, bis der
256 gewünschte Betrag erreicht ist. (Dies führt nur für bestimmte Werte der
257 Zahlungsmittel zur optimalen Gesamtlösung!)
258 \item Handlungsreisenden-Problem (Traveling Sales Man Problem,
259 TSP)\\\textbf{Ziel:} Finden der billigsten Rundreise, diealle Orte genau
260 einmal besucht.\\\textbf{Lösung (Greedy):} Gehe immer den günstigsten Weg vom
261 aktuellen Knoten zu einem noch nicht besuchten Knoten. Wenn alle besucht
262 wurden, kehre zum Anfang zurück. (Mit Greedy keine optimale Gesamtlösung!)
263 \item Aktivitäten Auswahlproblem\\\textbf{Ziel:} möglichst viele Anfragen
264 erfüllen. (Muss nicht bedeuten, dass die Ressource optimal
265 genutzt wird!)\\\textbf{Lösung (Greedy):} Nimm die Anfrage, die am frühesten
266 fertig ist. (optimale Gesamtlösung!)\\\textbf{Analyse:} $\Theta(n)$
269 \subsection{Kürzeste (billigste) Wege}
270 Pfad $P=$ Folge von Knoten.
271 Kosten eines Pfades:\[c(P)=\sum_{i=0}^{P.length-1}c(v_i,v_{i+1}\]
272 Entfernung von $v$ nach $w$ sind die Kosten des
273 günstigsten Pfades:\[dist(v,w)=inf{c(P)\mid P\text{= Weg von v nach
275 Kosten eines unerreichbaren Knoten sind definiert als $\infty$. Kosten eines
276 Pfades in einem negativen Zyklus: $-\infty$. Es können also nur Graphen ohne
277 negative Zyklen sinnvoll betrachtet werden!
278 \subsubsection{Single Source Shortest Paths}
279 Kürzeste/Günstigste Pfade von einem Knoten $s$ zu allen anderen Knoten. Hierfür
280 nutzt man die Dreiecksungleichung über $dist(u,v)\mid (u,v)\in E$ und $s\in V$:
281 \[dist(s,v)\leq dist(s,u)+dist(u,v)\]
282 \textbf{Greedy-Ansatz}
284 \item Überschätze die dist-Funktion \[dist(s,v)=\begin{cases}0&\text{ falls }
285 v=s\\\infty&\text{ falls }v\neq s\end{cases}\]
286 \item Solange eine Kante $e=(u,v)$ existiert mit
287 $dist(s,v)>dist(s,u)+c(u,v)$ setze $dist(s,v)=dist(s,u)+c(u,v)$
289 Durch die Überschätzung kann die Dreicksungleichung nur noch für Knoten $s$ und
290 seine direkten Nachfolger verletzt werden!\\Alle folgenden Verfahren basieren
291 auf diesem Prinzip!\\
292 %Elsässer führt einige Lemmas ein und beweist sie - diese beziehen sich auf den
293 % ersten optimimierten Algorithmus und diesen erachte ich in Relation zu
294 % Dijkstra als irrelevant!
295 \textbf{Effiziente Implementierungen}
296 Diese sind im Allgemeinen nicht bekannt, jedoch für wichtige Spezialfälle.
298 \item Nicht-negative Netzwerke: \underline{Dijkstra}
299 \item Netzwerke ohne negative Zyklen: \underline{Bellman-Ford}
300 \item Azyklische Netzwerke
303 \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
304 Dijkstra, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
305 basicstyle=\footnotesize]{./code/dijkstra.code}
309 \includegraphics[scale=0.6]{img/dijkstraExT}
310 \caption{Tree for Dijkstra Example}
315 \begin{tabular}{|c c c c c c c|c|}
317 \multicolumn{7}{|c|}{DIST[v]} & \\
319 s & a & b & c & d & e & f & U\\\hline\hline
320 0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & s,a,b,c,d,e,f\\
321 0* & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & a,b,c,d,e,f\\
322 0* & 6 & 7 & 5* & $\infty$ & $\infty$ & $\infty$ & a,b,d,e,f\\
323 0* & 6* & 7 & 5* & $\infty$ & $\infty$ & 14 & b,d,e,f\\
324 0* & 6* & 7* & 5* & 9 & 10 & 14 & d,e,f\\
325 0* & 6* & 7* & 5* & 9* & 10 & 11 & e,f\\
326 0* & 6* & 7* & 5* & 9* & 10* & 11 & f\\
327 0* & 6* & 7* & 5* & 9* & 10* & 11* & $\emptyset$\\\hline
329 \caption{Dijkstra Example}\label{tab:dijEx}
332 \[O(n\cdot(T_{insert}+T_{Empty}+T_{DeleteMin})+m\cdot T_{DecreaseKey}+m+n)\]
333 Implementierung mit Fibonaci-Heaps:\\
335 $T_{DeleteMin}:O(\log n)$ (amortisiert)\\
336 $T_{DecreaseKey}:O(1)$ (amortisiert)
338 \underline{Bellman-Ford}
339 \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
340 Belman-Ford, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
341 basicstyle=\footnotesize]{./code/BelmanFord.code}
342 \underline{Azyklische Netzwerke}
343 \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus für
344 Azyklische Netzwerke, captionpos=b, numbers=left, numberstyle=\tiny,
345 numbersep=5pt, basicstyle=\footnotesize]{./code/AzyklischeNetzwerke.code}
346 \subsection{Spannbäume minimalen Gewichts}
347 Ungerichteter Graph $G=(V,E)$, Kostenfunktion $c:E\rightarrow R$.\\Sei
348 $T\subseteq E$ ein Baum (zusammenhängender azyklischer Teilgraph) Kosten von T:
349 $c(T)=\sum_{(u,v)\in T}c(u,v)$.\\Ein minimaler Spannbaum ist ein Baum
350 $T\subseteq E$, der alle Knoten in $V$ verbindet minimale Kosten hat.
351 \subsubsection{Das Wachsen von min. Spannbäumen}
352 \textbf{Invariante:} Verwalte Menge $A\subseteq E$, die Teilmenge eines
353 minimalen Spannbaums ist.\\
354 \textbf{Definition:} Eine Kante $(u,v)\in E\backslash A$ ist sicher für $A$, wenn
355 $A\cup {(u,v)}$ Teilmenge eines minimalen Spannbaums ist.
356 \lstinputlisting[language=Java,label=lst:TTlookup,caption=Greedy Algorithmus für
357 Spannbäume, captionpos=b, numbers=left, numberstyle=\tiny,
358 numbersep=5pt, basicstyle=\footnotesize]{./code/spannbaeumeGreedy.code}
359 \subsubsection{Schnitte}
360 Ein Schnitt $(S,V\backslash S)$ ist eine Partition von $V$. Eine Kante $(u,v)$
361 schneidet $(S,V\backslash S)$, wenn ein Endpunkt in $S$ und der andere in
362 $V\backslash S$ liegt.\\Ein Schnitt "`respektiert $A$"', wenn keine Kante aus
363 $A$ den Schnitt schneidet.\\Eine Kante heißt minimal bzgl. eines Schnitts, wenn
364 sie den Schnitt schneidet und unter allen solchen Kanten minimale Kosten hat.
365 \subsubsection{Sichere Kanten}
366 \textbf{Satz:} Sei $A$ Teilmenge eines minimalen Spannbaums $T$ und
367 $(S,V\backslash S)$ ein Schnitt, der $A$ respektiert. Ist $(u,v)$ eine minimale
368 Kante bzgl. $(S,V\S)$, dann ist $(u,v)$ sicher für $A$.\\
369 \textbf{Beweis}: \begin{itemize}
370 \item[1. Fall] $(u,v)\in T$ : ok
371 \item[2. Fall] $(u,v)\not\in T$ : Wir konstruieren minimalen Spannbaum $T'$
372 mit $(u,v)\in T'$ und $A\subseteq T'$.
374 \subsubsection{Der Graph $G_A$}
377 \item ist ein \underline{Wald}, d.h. eine Menge von Bäumen
378 \item anfangs, wenn $A=\emptyset$, ist jeder Baum ein einzelner Knoten
379 \item eine sichere Kante verbindet verschiedene Bäume
381 \textbf{Korollar:} Sei $B$ ein Baum in $G_A=(V,A)$. Ist $(u,v)$ eine Kante
382 minimaler Kosten, die $B$ und einen anderen Baum in $G_A$ verbindet, dann ist
383 $(u,v)$ sicher für A.
384 \subsubsection{Algorithmus von Kruskal}
385 Wähle stets eine Kante minimaler Kosten, die zwei Bäume $B_1$ und $B_2$ in $G_A$
387 \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
388 Kruskal, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
389 basicstyle=\footnotesize]{./code/spannbaeumeKruskal.code}
390 Laufzeit: $O(m\alpha(n)+m+m\log n)$
391 \subsubsection{Algorithmus von Prim}
392 $A$ ist immer ein einziger Baum. Starte mit einem beliebigen Wurzelknoten $w$.
393 Füge in jedem Schritt eine minimale Kante hinzu, die einen Knoten in $A$ mit
394 einem Knoten in $V\backslash A$ verbindet.
395 \textbf{Implementierung}\\$Q$: Prioritätenwarteschlange, die alle Knoten $v\in
396 V\backslash A$ enthält.\\Schlüssel von $v$: minimale Kosten einer Kante, die $v$
397 mit einem Knoten aus $A$ verbindet.\\Für einen Knoten $v$ ist $p[v]$ der
398 Elter-Knoten von $v$ in dem Baum.\[A={(v,p[v]):v\in V-{w}-Q}\]
399 \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
400 Prim, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
401 basicstyle=\footnotesize]{./code/spannbaeumePrim.code}
402 Laufzeit: $O(n\log n+m)$
405 \section{Bin Packing}
406 \textbf{Problembeschreibung:}\\
407 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.
408 \subsection{Online Verfahren}
409 Jedes (ankommende) Objekt muss verpackt sein, bevor das nächste
410 Objekt betrachtet wird. Ein Objekt verbleibt in derjenigen Kiste,
411 in die es zuerst gepackt wird.\\ Kein Online Bin Packing Verfahren
412 kann stets eine optimale Lösung finden!\\ \textbf{Satz 1}: Es gibt
413 Eingaben, die jeden Online Bin Packing Algorithmus zwingen,
414 wenigstens $\frac{4}{3} OPT$ Bins zu verwenden, wobei $OPT$ die
415 minimal mögliche Binzahl ist.\\ \textbf{Beweis} Annahme: Online Bin
416 Packing Algorithmus benötigt stets weniger als $\frac{4}{3}OPT$
417 Bins.\\ Es wird eine Eingabe mit $2m$ Objekten angenommen. Die
418 ersten $m$ sind um $\epsilon$ kleiner als $\frac{1}{2}$, die
419 zweiten $m$ um $\epsilon$ größer. Die optimale Lösung sind $m$
420 Kisten, da immer ein großes mit einem kleinen Paket kombiniert
421 werden kann. Nun teilt man die Analyse in zwei Zeitpunkte: nach $m$
422 Objekten und nach $2m$ Objekten. Laut Annahme gilt nach nach $m$
423 Objekten, dass die Anzahl der Bins $b$ nur maximal $\frac{4}{3}
424 OPT$ groß sein darf. Mit $OPT=\frac{m}{2}$ gilt somit:
425 $b=\frac{4}{3}\cdot\frac{m}{2}=\frac{2}{3}m$. Sei $b=b_1+b_2\mid
426 b_1=\#$Bins mit einem Objekt, $b_2=\#$Bins mit zwei Objekten, so
427 folgt $b_1+2b_2=m\implies b_1=m-2b_2\implies b=b_1+b_2=m-b_2$. Nach
428 $2m$ Objekten ist $OPT=m$, wie zuvor beschrieben. $b_1$ Bins können
429 zu diesem Zeitpunkt mit Objekten des zweiten Bereichs gefüllt
430 werden, für die verbleibenden muss man neue Bins öffnen. Die Anzahl
431 der neu zu öffnenden beträgt damit genau $b_2\implies \#$Bins $\geq
432 b+m-b_1=m+b_2$. Die Annahme besagt $m+b_2\leq\#$Bins $<\frac{4}{3}m
433 \wedge b_2<\frac{m}{3}$. Dies ist nur möglich, wenn
434 $b=m-b_2>\frac{2}{3}m$ - Dies führt zu einem
435 \underline{Widerspruch}, da $b$ zum Zeitpunkt 1, nach $m$ Objekten
436 $<\frac{2}{3}m$ sein muss.
438 \subsubsection{Next Fit (NF)}
439 Verpacke das nächste Objekt in dieselbe Kiste wie das
440 vorherige, wenn es dort noch hineinpasst, sonst öffne eine neue
441 Kiste und verpacke es dort.\\ \textbf{Satz 2}: (a) Für alle
442 Inputfolgen $I$ gilt: $NF(I)\leq2OPT(I)$. (b) Es gibt
443 Inputfolgen I mit $NF(I)\geq2OPT(I)-2$.\\ \textbf{Beweis}\\ (a)
444 Betrachte zwei beliebige aufeinanderfolgende Kisten $B_{2k-1},
445 B_{2k}$. Man weiß, dass die beinhalteten Objekte eine
446 Summengröße $>1$ haben, sonst wären selbige in einer Kiste.
447 Daraus folgt, man kann nicht mehr als die doppelte Anzahl an
448 Kisten als beim Optimum erreichen!\\ (b) Inputfolge: $0.5,
449 \frac{2}{n}, 0.5, \frac{2}{n}, 0.5, \frac{2}{n}, \ldots 0.5,
450 \frac{2}{n}$.\\Next-Fit liefert nun immer Bins gefüllt mit $0.5
451 + \frac{2}{n}$. Darausfolgt $NF(I)=\frac{n}{2}$ und
452 $OPT=\frac{n}{4}+1$ (weil $\frac{n}{2}$ mal 0.5er Objekte in
453 $=\frac{n}{4}$ Kisten passen und $\frac{n}{2}$ $\frac{2}{n}$er
454 Objekte in eine Kiste passen)\\ Laufzeit für Inputfolgen der
456 \subsubsection{First-Fit (FF)}
457 Packe nächstes Objekt in die erste Kiste, in die es noch
458 hineinpasst, wenn es eine solche Kiste gibt, sonst in eine neue
459 Kiste.\\ \textbf{Beobachtung}: Zu jedem Zeitpunkt kann es
460 höchstens eine Kiste geben, die weniger als halb voll ist.
461 ($\implies FF(I) \leq 2OPT(I)$)\\ \textbf{Satz 3}: (a) Für alle
462 Inputfolgen $I$ gilt $FF(I)\leq \lceil\frac{17}{10}
463 OPT(I)\rceil$. (b) Es gibt Inputfolgen $I$ mit
464 $FF(I)\geq\frac{17}{10}(OPT(I)-1)$. (b') Es gibt Inputfolgen
465 $I$ mit $FF(I)=\frac{10}{6}OPT(I)$.\\ \textbf{Beweis}\\ (b')
466 Inputfolge der Länge $3\cdot6m$. Dabei je $6m$ Objekte der
467 Größen $\frac{1}{7}+\epsilon, \frac{1}{3}+\epsilon,
468 \frac{1}{2}+\epsilon$, welche in gegebener Reihenfolge in
469 Gruppen eingegeben werden. FF liefert hierbei $m$ Kisten
470 gefüllt mit den Objekten der Größe $\frac{1}{7}+\epsilon$
471 (jeweils 6 pro Kiste) gefolgt von $\frac{6m}{2}=3m$ Kisten
472 gefüllt mit Objekten der Größe $\frac{1}{3}+\epsilon$ (jeweils
473 2 pro Kiste) und schlussendlich $6m$ Kisten mit je einem Objekt
474 der Größe $\frac{1}{2}+\epsilon$. Das macht in der Summe $10m$
475 Kisten. Die optimale Lösung packt je ein Objekt jeder Größe in
476 eine Kiste und benötigt somit nur $6m$ Kisten.\\ Laufzeit für
477 Inputfolgen der Länge $n$: FF $O(n^2) \rightarrow O(n \log n)$
478 \subsubsection{Best-Fit (BF)}
479 Verpacke das nächste Objekt in diejenige Kiste, in die es am
480 besten passt (d.h. den geringsten Platz ungenutzt lässt).
481 Verhalten von BF ähnlich zu FF. Laufzeit für Inputfolgen der
482 Länge $n$: BF $O(n^2) \rightarrow O(n \log n)$
483 \subsection{Offline Verfahren}
484 \underline{NP-schwieriges Problem! Entscheidungsproblem ist NP-vollständig!}\\
485 Zunächst wird die Anzahl $n$ und alle $n$ Objekte vorgegeben. Dann
486 beginnt die Verpackung.\\ $n$ und $s_1, ..., s_n$ sind gegeben,
487 bevor die Verpackung beginnt!\\ $\rightarrow$ \underline{Optimale
488 Verpackung} kann durch erschöpfende Suche bestimmt werden. ABER:
489 Benötigt exponentielle Zeit! Daher Approximimationsalgorithmen, die
490 schneller sind aber dafür unter Umständen nicht optimal!\\
491 Idee für Offline Approximationsalgorithmen: Sortiere die Objekte
492 zunächst nach abnhemender Größe und verpacke größere Objekte zuerst!
493 \subsubsection{First Fit Decreasing (FFD oder FFNI)}
494 \textbf{Lemma 1}: Sei $I$ eine Folge von $n$ Objekten mit
495 Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann
496 haben alle von FFD in den Bins
497 $B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackten Objekte eine
498 Größe von höchstens $\frac{1}{3}$.
500 %TODO:Elsässer hat das in seiner VL gemacht - aber hässlich lang
501 \textbf{Lemma 2}: Sei $I$ eine Folge von $n$ Objekten mit
502 Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann
503 ist die Anzahl der Objekte, die FFD in die Kisten
504 $B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackt, höchstens
505 $m-1$.\\ \textbf{Beweis}: Annahme: Es gibt mehr als $m-1$
506 Objekte. $x_1,\ldots,x_m$ in $I$, die FFD in extra Kisten
507 verpacken. Dies führt zu einem Widerspruch.
509 \textbf{Satz}: Für alle Inputfolgen I
510 gilt $FFD(I)\leq(4 OPT(I)+\frac{1}{3})$.\\ \textbf{Satz}:
512 \item[1.] Für alle Inputfolgen $I$ gilt: $FFD(I)\leq \frac{11}{9} OPT(I)+4$
513 \item[2.] Es gibt Inputfolgen $I$ mit: $FFD(I)=\frac{11}{9}OPT(I)$.
515 \textbf{Beweis}: %TODO
516 \subsubsection{Best Fit Decreasing (BFD)}
517 %TODO Nicht im Script???
520 \section{Dynamische Programmierung}
521 \textbf{Idee:} Speichern von zwischen Ergebnissen, welche sonst mehrfach
522 berechnet werden müssten.\\
525 \item Rekursive Beschreibung des Problems P
526 \item Bestimmung einer Menge T, die alle Teilprobleme von P enthält, auf die
527 bei der Lösung von P zugegriffen wird.
528 \item Bestimmung einer Reihenfolge $T_0,\ldots T_k$ der Probleme in T, so dass
529 bei der Lösung von $T_i$ nur auf Probleme $T_j$ mit $j<i$ zurückgegriffen
531 \item Sukzessive Berechnung und Speicherung von Lösungen für $T_0,\ldots T_k$.
533 Wird im Script anhand der Fibonacci Zahlen demonstriert aber ist trivial \ldots
534 \subsection{Matrixkettenprodukt (TODO)}
536 \subsection{Optimale Suchbäume (TODO)}
538 \subsection{Editierdistanz}
539 Berechne für zwei gegebene Zeichenfolgen $A$ und $B$ möglichst effizient die
540 Editier-Distanz $D(A,B)$ und eine minimale Folge von Editieroperationen, die
541 $A$ in $B$ überführt.\\
542 \textbf{Editieroperationen:}
544 \item Ersetzen eines Zeichens von $A$ durch ein Zeichen von $B$
545 \item Löschen eines Zeichens von $A$
546 \item Einfügen eines Zeichens von $B$
548 \textbf{Einheitskostenmodell:}
549 \[c(a,b)=\begin{cases}1 & \text{falls } a\neq b\\0 & \text{falls } a=b\end{cases}\]
550 $a=\epsilon, b=\epsilon$ möglich Dreiecksungleichung soll für $c$ im
552 \[c(a,c)\leq c(a,b)+c(b,c)\]
553 $\rightarrow$ ein Buchstabe wird höchstens einmal
555 Rekursionsgleichung, falls $m,n\geq 1$
556 \[D_{m,n}=min\left.\begin{cases}D_{m-1,n-1}+c(a_m,b_n)\\D_{m-1,n}+1\\D_{m,n-1}+1\end{cases}\right\}\]
558 \[D_{0,0}=D(\epsilon,\epsilon)=0\]
559 \[D_{0,j}=D(\epsilon,B_j)=j\]
560 \[D_{i,0}=D(A_i,\epsilon)=i\]
561 \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus zur
562 Editierdistanz, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
563 basicstyle=\footnotesize]{./code/editierdistanz.code}
564 \textbf{Spurgraph:}\\
565 Übersicht über alle möglichen Spuren zur Transformation von $A$ in $B$,
566 gerichtete Kanten von Knoten $(i,j)$ zu $(i+1,j)$, $(i,j+1)$ und $(i+1,j+1)$.
567 Gewichtung der Kanten entspricht den Editierkosten. Kosten nehmen entlang eines
568 optimalen Weges monoton zu. Jeder Weg mit monotin wachsenden Kosten von der
569 linken oberen Ecke zur rechten unteren Ecke entspricht einer optimalen Spur. Zur
570 Berechnung der Spur der minimalen Editieroperationen (es gibt mehrere
571 Lösungen), kann folgender Algorithmus verwendet werden:
572 \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus zum Spurgraphen, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\footnotesize]{./code/spurgraph.code}
574 \section{Suche in Texten}
575 \underline{Gegeben:} Text T $t_1t_2t_3\ldots t_n\in\Sigma^n$ und
576 rin Muster P $p_1p_2p_3\ldots p_m\in\Sigma^m$\\
577 \underline{Gesucht:} Ein oder alle Vorkommen des Musters im Text, d.h.
578 Verschiebungen $i$ mit $0\leq i\leq n-m$.\\
579 \textbf{Naives Verfahren:} iteriere über den Text und suche das Muster. Aufwand:
580 $m\cdot(n-m+1)$ Vergleiche $\implies \Omega(n\cdot m)$
581 \textbf{Verfahren nach Knuth-Morris-Pratt (KMP):}
582 Präffix=Suffix Verfahren. Daraus resultiert eine Shiftmöglichkeit des Musters
583 über den Text. Der Shift geschieht um $next[j]$=Länge des längsten Präfix von
584 $P$, das echtes Suffix von $P_{1\ldots j}$ ist, wobei $j=$Position des letzten
586 \underline{Erstellung des $next[j]$ arrays über P.}\\
590 \begin{tabular}{c|c|c|c|c|c|c|c|c|c}
591 1&2&3&4&5&6&7&8&9&10\\\hline
592 0&1&0&1&1&0&1&0&1&1\\\hline
601 \caption{next[j] Beispiel}
604 $\rightarrow next[j]=[0,0,1,2,0,1,2,3,4,5]$\\
605 \underline{Algorithmus:}
606 \lstinputlisting[language=Java,label=lst:TTlookup,caption=KMP Algorithmus,
607 captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\footnotesize]{./code/kmp.code}
609 inkrement $j$ = inkrement $i$ und dekrement $j$ = inkrement $j$!
610 $\rightarrow O(n)$ hinzu kommt noch die Berechnung des next-arrays mit $O(m)$.\\
611 KMP kann also mit $O(n+m)$ berechnet werden. (i.e. Untere Schranke
616 \section{Landau-Symbole}
619 \includegraphics[scale=0.45]{img/landau_sym}
620 \caption{Definition der Landau Symbole}
621 \label{fig:landau_sym}