1.1 --- a/exzerpt.tex Tue Feb 22 18:58:21 2011 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,250 +0,0 @@
1.4 -\documentclass[a4paper,11pt,twoside]{article}
1.5 -
1.6 -\usepackage[ngerman]{babel}
1.7 -\usepackage[T1]{fontenc}
1.8 -\usepackage[latin1]{inputenc}
1.9 -\usepackage[colorlinks=true,linkcolor=black]{hyperref}
1.10 -
1.11 -\usepackage{vaucanson-g}
1.12 -\usepackage{hyperref}
1.13 -\usepackage{hypcap}
1.14 -\usepackage{fancyhdr}
1.15 -\usepackage{graphicx}
1.16 -\usepackage{lastpage}
1.17 -\usepackage[cm]{fullpage}
1.18 -\usepackage{amsthm, amsmath, amsfonts}
1.19 -\usepackage{float}
1.20 -\usepackage{paralist}
1.21 -\usepackage{listings}
1.22 -\usepackage{color}
1.23 -\usepackage{bookmark}
1.24 -
1.25 -% Festlegung Art der Zitierung - Havardmethode: Abkuerzung Autor + Jahr
1.26 -\bibliographystyle{alphadin}
1.27 -
1.28 -\title{\underline{Exzerpt Algorithmentheorie WS10/11}}
1.29 -\author{Markus Lindenmann}
1.30 -\date{\today{} }
1.31 -
1.32 -\begin{document}
1.33 - \maketitle
1.34 -
1.35 - \tableofcontents
1.36 - \newpage
1.37 -
1.38 - \section{Einleitung}\label{sec:intro}
1.39 - Dozent: Matthias Westermann\\
1.40 - Website: \url{http://lak.informatik.uni-freiburg.de}\\
1.41 - Klausur: 09.03.2011\\
1.42 - Hilfsmittel: Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt
1.43 - \subsection{Themen:}
1.44 - \begin{itemize}
1.45 - \item[$\bullet$] Divide and Conquer
1.46 - \item[$\bullet$] Greedy Prinzip
1.47 - \item[$\bullet$] Dynamische Programmierung
1.48 - \item[$\bullet$] Randomisierung
1.49 - \item[$\bullet$] Amortisierte Analyse
1.50 - \end{itemize}
1.51 - \subsection{Problem-/Anwendungsbereiche:}
1.52 - \begin{itemize}
1.53 - \item[$\bullet$] Geometrische Algorithmen
1.54 - \item[$\bullet$] Algebraische Algorithmen
1.55 - \item[$\bullet$] Graphenalgorithmen
1.56 - \item[$\bullet$] Datenstrukturen
1.57 - \item[$\bullet$] Internet-Algorithmen
1.58 - \item[$\bullet$] ptimierungs-Verfahren
1.59 - \item[$\bullet$] Zeichenkettenverarbeitung
1.60 - \end{itemize}
1.61 - \subsection{Literatur:}
1.62 - \bibliography{literatur}
1.63 - \nocite{*}
1.64 -
1.65 - \newpage
1.66 - \section{Divide and Conquer}\label{sec:div&conq}
1.67 - \begin{itemize}
1.68 - \item[$\bullet$] Quicksort
1.69 - \item[$\bullet$] Formulierung und Analyse des Prinzips
1.70 - \item[$\bullet$] Geometrisches Devide and Conquer
1.71 - \begin{itemize}
1.72 - \item[-] Closest-Pair
1.73 - \item[-] Segmentschnitt
1.74 - \end{itemize}
1.75 - \end{itemize}
1.76 -
1.77 - \subsection{Formulierung des Divide and Conquer Prinzips}
1.78 - D\&C Verfahren zur Lösung eines Problems der Größe $n$
1.79 - \begin{itemize}
1.80 - \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
1.81 - \item[2.] Conquer\\Löse die $k$ Teilprobleme auf dieselbe Art (rekursiv)
1.82 - \item[3.] Merge\\Füge die berechneten Teillösungen zu einer Gesamtlösung zusammen
1.83 - \end{itemize}
1.84 -
1.85 - \subsection{Quicksort}
1.86 - 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.
1.87 -
1.88 - \subsubsection{Analyse}
1.89 - $T(n)$ - maximale Anzahl von Schritten, um ein Problem der Größe $n$ zu lösen.
1.90 - \[T(n)=\begin{cases}n\neq c&a \\ n>c&T(n_1+\ldots+T(n_k)+\text{Divide- und Mergeaufwand}\end{cases}\]
1.91 - Best Case: $k=2, n_1=n_2=\frac{n}{2}$\\
1.92 - Divide- und Mergeaufwand: $DM(n)$\\
1.93 - $T(1)=a$\\
1.94 - $T(n)=2T(\frac{n}{2})+DM(n)$
1.95 -
1.96 - \subsection{Nächste Paare}
1.97 - Eingabe: $n$ Punkte in Ebene\\
1.98 - Ausgabe: Punkt-Paar $q,r$ mit geringstem Abstand\\
1.99 - Abstand: $d(q,r)$ bechreibt Abstand zwischen Punkten $q$ und $r$
1.100 - \subsubsection{Algorithmus}
1.101 - \begin{itemize}
1.102 - \item[$\bullet$] sortiere Punktmenge nach x-Koordinate
1.103 - \item[$\bullet$] Teile Punktmenge in der Mitte L in die Mengen Q und R
1.104 - \item[$\bullet$] Löse rekursiv auf Q und R
1.105 - \item[$\bullet$] Sortiere Punkte nach y-Koordinate
1.106 - \item[$\bullet$] Teste alle Paare, deren Abstand in der Sortierung kleiner als 16 ist (siehe unten)
1.107 - \item[$\bullet$] Füge zusammen
1.108 - \end{itemize}
1.109 -
1.110 - $\delta=$ Minimum der Teillösungen\\
1.111 - 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.\\
1.112 - \textbf{Problem:} alle Punkte können innerhalb der $\delta$-Zone liegen\\
1.113 - \textbf{Lösung:}\begin{itemize}
1.114 - \item[$\bullet$] Sortiere Punkte in $\delta$ Zone nach $y$-Abstand
1.115 - \item[$\bullet$] Liegen in dieser Sortierung mehr als $c$ Punkte zwischen $q$ und $r$, dann kann $(q,r)$ nicht nächstes Paar sein
1.116 - \end{itemize}
1.117 -
1.118 - Dies kann für $c=15$ bewiesen werden (vgl. Abbildung \ref{cl_pair}):
1.119 - \begin{itemize}
1.120 - \item[$\bullet$] Seien min. 15 Punkte zwischen $q$ und $r$
1.121 - \item[$\bullet$] Dann sind mindestens 3 Reihen Quadrate zwischen $q,r$, weil in jedem Quadrat höchstens ein Punkt ist.
1.122 - \item[$\rightarrow$] Dann muss $d(q,r)$ mindestens $\frac{3}{2}\delta > \delta$ sein.
1.123 - \end{itemize}
1.124 -
1.125 - \begin{figure}[H]
1.126 - \centering
1.127 - \includegraphics[scale=0.5]{img/cl_pair}
1.128 - \caption{Nächste Paare: Prüf Distanz}
1.129 - \label{cl_pair}
1.130 - \end{figure}
1.131 -
1.132 - \subsubsection{Analyse}
1.133 - \[T(n)=\begin{cases}n\leq3&a \\ n>3&2T(\frac{n}{2})+an\end{cases}\]
1.134 - \[T(n)\leq an \log n \]
1.135 -
1.136 - \subsection{Segmentschnitt}
1.137 - Eingabe: Menge S bestehend aus vertikalen Segmenten und Endpunkten vn horizontalen Segmenten\\
1.138 - Ausgabe: Alle Schnittpunkte von vertikalen Segmenten mit horizontalen Segmenten, von denen mindesens ein Endpunkt in S ist
1.139 -
1.140 - \subsubsection{Algorithmus}
1.141 - \textbf{Divide \& Conquer:}\\Fallunterscheidung
1.142 - \begin{itemize}
1.143 - \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.
1.144 - \item[2.] else: S enthält keine Schnitte
1.145 - \end{itemize}
1.146 -
1.147 - \textbf{Merge}\\
1.148 - Bilde L(S), R(S) und V(S) (Definition am Beispiel $i=1,2$ berechnet: $S=S_1\cup S_2$):
1.149 - \begin{itemize}
1.150 - \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))$
1.151 - \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))$
1.152 - \item[$\bullet$] V(S): y-Intervalle der vertikalen Segmente in S\\$=V(S_1)\cup V(S_2)$
1.153 - \end{itemize}
1.154 - L,R sortiert nach steigender y-Koordinate\\
1.155 - V sortiert nach steigendem unteren Endpunkt\\
1.156 - \medskip
1.157 -
1.158 - \textbf{Basisfälle}\\
1.159 - S enthält nur ein Element s. Fallunterscheidung:
1.160 - \begin{itemize}
1.161 - \item[1.] $s=(x,y)$ ist ein linker Endpunkt:\\$L(S)=\{y\},\qquad R(S)=\emptyset,\qquad V(S)=\emptyset$
1.162 - \item[2.] $s=(x,y)$ ist ein rechter Endpunkt:\\$L(S)=\emptyset,\qquad R(S)=\{y\},\qquad V(S)=\emptyset$
1.163 - \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]\}$
1.164 - \end{itemize}
1.165 -
1.166 - \subsubsection{Analyse}
1.167 - Eingabe wird Anfangs sortiert und in Array gespeichert
1.168 - \[T(n)=2T(\frac{n}{2}+an+\text{Größe der Ausgabe}\]
1.169 - \[T(1)=O(1)\]
1.170 - \[O(n \log n + k \mid k=\#Schnittpunkte\]
1.171 -
1.172 - \subsection{Polynomprodukt und Fast Fourier-Transformation}
1.173 -
1.174 -
1.175 - \newpage
1.176 - \section{Randomisierung}
1.177 - \subsection{Hashing}
1.178 -
1.179 - \newpage
1.180 - \section{Amortisierte Analyse}
1.181 - \subsection{Binomial Heaps}
1.182 - \subsection{Fibonacci Heaps}
1.183 - \subsection{Union Find}
1.184 -
1.185 - \newpage
1.186 - \section{Greedy}
1.187 - \subsection{Kürzeste (billigste) Wege}
1.188 -
1.189 - \newpage
1.190 - \section{Bin Packing}
1.191 - \textbf{Problembeschreibung:}\\
1.192 - 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.
1.193 - \subsection{Online Verfahren}
1.194 - 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.\\
1.195 - Kein Online Bin Packing Verfahren kann stets eine optimale Lösung finden!\\
1.196 - \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.\\
1.197 - \textbf{Beweis} Annahme: Online Bin Packing Algorithmus benötigt stets weniger als $\frac{4}{3}OPT$ Bins.\\
1.198 - 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.
1.199 -
1.200 - \subsubsection{Next Fit (NF)}
1.201 - 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.\\
1.202 - \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$.\\
1.203 - \textbf{Beweis}\\
1.204 - (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!\\
1.205 - (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)\\
1.206 - Laufzeit für Inputfolgen der Länge $n$: NF $O(n)$
1.207 - \subsubsection{First-Fit (FF)}
1.208 - Packe nächstes Objekt in die erste Kiste, in die es noch hineinpasst, wenn es eine solche Kiste gibt, sonst in eine neue Kiste.\\
1.209 - \textbf{Beobachtung}: Zu jedem Zeitpunkt kann es höchstens eine Kiste geben, die weniger als halb voll ist. ($\implies FF(I) \leq 2OPT(I)$)\\
1.210 - \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)$.\\
1.211 - \textbf{Beweis}\\
1.212 - (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.\\
1.213 - Laufzeit für Inputfolgen der Länge $n$: FF $O(n^2) \rightarrow O(n \log n)$
1.214 - \subsubsection{Best-Fit (BF)}
1.215 - Verpacke das nächste Objekt in diejenige Kiste, in die es am besten passt (d.h. den geringsten Platz ungenutzt lässt).
1.216 - Verhalten von BF ähnlich zu FF.
1.217 - Laufzeit für Inputfolgen der Länge $n$: BF $O(n^2) \rightarrow O(n \log n)$
1.218 - \subsection{Offline Verfahren}
1.219 - \underline{NP-schwieriges Problem! Entscheidungsproblem ist NP-vollständig!}\\
1.220 - Zunächst wird die Anzahl $n$ und alle $n$ Objekte vorgegeben. Dann beginnt die Verpackung.\\
1.221 - $n$ und $s_1, ..., s_n$ sind gegeben, bevor die Verpackung beginnt!\\
1.222 - $\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!\\
1.223 - Idee für Offline Approximationsalgorithmen: Sortiere die Objekte zunächst nach abnhemender Größe und verpacke größere Objekte zuerst!
1.224 - \subsubsection{First Fit Decreasing (FFD oder FFNI)}
1.225 - \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}$.\\
1.226 - \textbf{Beweis}: \$\$\$TODO:Elsässer hat das in seiner VL gemacht - aber hässlich lang\$\$\$\\
1.227 - \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$.\\
1.228 - \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?\$\$\$\\
1.229 - \textbf{Satz}: Für alle Inputfolgen I gilt $FFD(I)\leq(4 OPT(I)+\frac{1}{3})$.\\
1.230 - \textbf{Satz}:
1.231 - \begin{itemize}
1.232 - \item[1.] Für alle Inputfolgen $I$ gilt: $FFD(I)\leq \frac{11}{9} OPT(I)+4$
1.233 - \item[2.] Es gibt Inputfolgen $I$ mit: $FFD(I)=\frac{11}{9}OPT(I)$.
1.234 - \end{itemize}
1.235 - \textbf{Beweis}: \$\$\$TODO\$\$\$
1.236 - \subsubsection{Best Fit Decreasing (BFD)}
1.237 - Nicht im Script???
1.238 -
1.239 - \newpage
1.240 - \section{Dynamische Programmierung}
1.241 -
1.242 -
1.243 - \newpage
1.244 - \begin{appendix}
1.245 - \section{Landau-Symbole}
1.246 - \begin{figure}[H]
1.247 - \centering
1.248 - \includegraphics[scale=0.45]{img/landau_sym}
1.249 - \caption{Definition der Landau Symbole}
1.250 - \label{fig:landau_sym}
1.251 - \end{figure}
1.252 - \end{appendix}
1.253 -\end{document}