lindenmannm@0: \documentclass[a4paper,11pt,twoside]{article} lindenmannm@0: lindenmannm@0: \usepackage[ngerman]{babel} lindenmannm@0: \usepackage[T1]{fontenc} lindenmannm@0: \usepackage[latin1]{inputenc} lindenmannm@0: \usepackage[colorlinks=true,linkcolor=black]{hyperref} lindenmannm@0: lindenmannm@0: \usepackage{vaucanson-g} lindenmannm@0: \usepackage{hyperref} lindenmannm@0: \usepackage{hypcap} lindenmannm@0: \usepackage{fancyhdr} lindenmannm@0: \usepackage{graphicx} lindenmannm@0: \usepackage{lastpage} lindenmannm@0: \usepackage[cm]{fullpage} lindenmannm@0: \usepackage{amsthm, amsmath, amsfonts} lindenmannm@0: \usepackage{float} lindenmannm@0: \usepackage{paralist} lindenmannm@0: \usepackage{listings} lindenmannm@0: \usepackage{color} lindenmannm@0: \usepackage{bookmark} lindenmannm@0: lindenmannm@0: % Festlegung Art der Zitierung - Havardmethode: Abkuerzung Autor + Jahr lindenmannm@0: \bibliographystyle{alphadin} lindenmannm@0: lindenmannm@0: \title{\underline{Exzerpt Algorithmentheorie WS10/11}} lindenmannm@0: \author{Markus Lindenmann} lindenmannm@0: \date{\today{} } lindenmannm@0: lindenmannm@0: \begin{document} lindenmannm@0: \maketitle lindenmannm@0: lindenmannm@0: \tableofcontents lindenmannm@0: \newpage lindenmannm@0: lindenmannm@0: \section{Einleitung}\label{sec:intro} lindenmannm@0: Dozent: Matthias Westermann\\ lindenmannm@1: Website: \url{http://lak.informatik.uni-freiburg.de}\\ lindenmannm@0: Klausur: 09.03.2011\\ lindenmannm@0: Hilfsmittel: Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt lindenmannm@0: \subsection{Themen:} lindenmannm@0: \begin{itemize} lindenmannm@0: \item[$\bullet$] Divide and Conquer lindenmannm@0: \item[$\bullet$] Greedy Prinzip lindenmannm@0: \item[$\bullet$] Dynamische Programmierung lindenmannm@0: \item[$\bullet$] Randomisierung lindenmannm@0: \item[$\bullet$] Amortisierte Analyse lindenmannm@0: \end{itemize} lindenmannm@0: \subsection{Problem-/Anwendungsbereiche:} lindenmannm@0: \begin{itemize} lindenmannm@0: \item[$\bullet$] Geometrische Algorithmen lindenmannm@0: \item[$\bullet$] Algebraische Algorithmen lindenmannm@0: \item[$\bullet$] Graphenalgorithmen lindenmannm@0: \item[$\bullet$] Datenstrukturen lindenmannm@0: \item[$\bullet$] Internet-Algorithmen lindenmannm@0: \item[$\bullet$] ptimierungs-Verfahren lindenmannm@0: \item[$\bullet$] Zeichenkettenverarbeitung lindenmannm@0: \end{itemize} lindenmannm@0: \subsection{Literatur:} lindenmannm@0: \bibliography{literatur} lindenmannm@1: \nocite{*} lindenmannm@0: lindenmannm@0: \newpage lindenmannm@0: \section{Divide and Conquer}\label{sec:div&conq} lindenmannm@0: \begin{itemize} lindenmannm@0: \item[$\bullet$] Quicksort lindenmannm@0: \item[$\bullet$] Formulierung und Analyse des Prinzips lindenmannm@0: \item[$\bullet$] Geometrisches Devide and Conquer lindenmannm@0: \begin{itemize} lindenmannm@0: \item[-] Closest-Pair lindenmannm@0: \item[-] Segmentschnitt lindenmannm@0: \end{itemize} lindenmannm@0: \end{itemize} lindenmannm@0: lindenmannm@0: \subsection{Formulierung des Divide and Conquer Prinzips} lindenmannm@0: D\&C Verfahren zur Lösung eines Problems der Größe $n$ lindenmannm@0: \begin{itemize} lindenmannm@0: \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 lindenmannm@0: \item[2.] Conquer\\Löse die $k$ Teilprobleme auf dieselbe Art (rekursiv) lindenmannm@0: \item[3.] Merge\\Füge die berechneten Teillösungen zu einer Gesamtlösung zusammen lindenmannm@0: \end{itemize} lindenmannm@0: lindenmannm@0: \subsection{Quicksort} lindenmannm@0: 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. lindenmannm@0: lindenmannm@0: \subsubsection{Analyse} lindenmannm@0: $T(n)$ - maximale Anzahl von Schritten, um ein Problem der Größe $n$ zu lösen. lindenmannm@0: \[T(n)=\begin{cases}n\neq c&a \\ n>c&T(n_1+\ldots+T(n_k)+\text{Divide- und Mergeaufwand}\end{cases}\] lindenmannm@0: Best Case: $k=2, n_1=n_2=\frac{n}{2}$\\ lindenmannm@0: Divide- und Mergeaufwand: $DM(n)$\\ lindenmannm@0: $T(1)=a$\\ lindenmannm@0: $T(n)=2T(\frac{n}{2})+DM(n)$ lindenmannm@0: lindenmannm@0: \subsection{Nächste Paare} lindenmannm@0: Eingabe: $n$ Punkte in Ebene\\ lindenmannm@0: Ausgabe: Punkt-Paar $q,r$ mit geringstem Abstand\\ lindenmannm@0: Abstand: $d(q,r)$ bechreibt Abstand zwischen Punkten $q$ und $r$ lindenmannm@0: \subsubsection{Algorithmus} lindenmannm@0: \begin{itemize} lindenmannm@0: \item[$\bullet$] sortiere Punktmenge nach x-Koordinate lindenmannm@0: \item[$\bullet$] Teile Punktmenge in der Mitte L in die Mengen Q und R lindenmannm@0: \item[$\bullet$] Löse rekursiv auf Q und R lindenmannm@0: \item[$\bullet$] Sortiere Punkte nach y-Koordinate lindenmannm@0: \item[$\bullet$] Teste alle Paare, deren Abstand in der Sortierung kleiner als 16 ist (siehe unten) lindenmannm@0: \item[$\bullet$] Füge zusammen lindenmannm@0: \end{itemize} lindenmannm@0: lindenmannm@0: $\delta=$ Minimum der Teillösungen\\ lindenmannm@0: 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.\\ lindenmannm@0: \textbf{Problem:} alle Punkte können innerhalb der $\delta$-Zone liegen\\ lindenmannm@0: \textbf{Lösung:}\begin{itemize} lindenmannm@0: \item[$\bullet$] Sortiere Punkte in $\delta$ Zone nach $y$-Abstand lindenmannm@0: \item[$\bullet$] Liegen in dieser Sortierung mehr als $c$ Punkte zwischen $q$ und $r$, dann kann $(q,r)$ nicht nächstes Paar sein lindenmannm@0: \end{itemize} lindenmannm@0: lindenmannm@0: Dies kann für $c=15$ bewiesen werden (vgl. Abbildung \ref{cl_pair}): lindenmannm@0: \begin{itemize} lindenmannm@0: \item[$\bullet$] Seien min. 15 Punkte zwischen $q$ und $r$ lindenmannm@0: \item[$\bullet$] Dann sind mindestens 3 Reihen Quadrate zwischen $q,r$, weil in jedem Quadrat höchstens ein Punkt ist. lindenmannm@0: \item[$\rightarrow$] Dann muss $d(q,r)$ mindestens $\frac{3}{2}\delta > \delta$ sein. lindenmannm@0: \end{itemize} lindenmannm@0: lindenmannm@0: \begin{figure}[H] lindenmannm@0: \centering lindenmannm@0: \includegraphics[scale=0.5]{img/cl_pair} lindenmannm@0: \caption{Nächste Paare: Prüf Distanz} lindenmannm@0: \label{cl_pair} lindenmannm@0: \end{figure} lindenmannm@0: lindenmannm@0: \subsubsection{Analyse} lindenmannm@0: \[T(n)=\begin{cases}n\leq3&a \\ n>3&2T(\frac{n}{2})+an\end{cases}\] lindenmannm@0: \[T(n)\leq an \log n \] lindenmannm@0: lindenmannm@0: \subsection{Segmentschnitt} lindenmannm@0: Eingabe: Menge S bestehend aus vertikalen Segmenten und Endpunkten vn horizontalen Segmenten\\ lindenmannm@0: Ausgabe: Alle Schnittpunkte von vertikalen Segmenten mit horizontalen Segmenten, von denen mindesens ein Endpunkt in S ist lindenmannm@0: lindenmannm@0: \subsubsection{Algorithmus} lindenmannm@0: \textbf{Divide \& Conquer:}\\Fallunterscheidung lindenmannm@0: \begin{itemize} lindenmannm@0: \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. lindenmannm@0: \item[2.] else: S enthält keine Schnitte lindenmannm@0: \end{itemize} lindenmannm@0: lindenmannm@0: \textbf{Merge}\\ lindenmannm@0: Bilde L(S), R(S) und V(S) (Definition am Beispiel $i=1,2$ berechnet: $S=S_1\cup S_2$): lindenmannm@0: \begin{itemize} lindenmannm@0: \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))$ lindenmannm@0: \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))$ lindenmannm@0: \item[$\bullet$] V(S): y-Intervalle der vertikalen Segmente in S\\$=V(S_1)\cup V(S_2)$ lindenmannm@0: \end{itemize} lindenmannm@0: L,R sortiert nach steigender y-Koordinate\\ lindenmannm@0: V sortiert nach steigendem unteren Endpunkt\\ lindenmannm@0: \medskip lindenmannm@0: lindenmannm@0: \textbf{Basisfälle}\\ lindenmannm@0: S enthält nur ein Element s. Fallunterscheidung: lindenmannm@0: \begin{itemize} lindenmannm@0: \item[1.] $s=(x,y)$ ist ein linker Endpunkt:\\$L(S)=\{y\},\qquad R(S)=\emptyset,\qquad V(S)=\emptyset$ lindenmannm@0: \item[2.] $s=(x,y)$ ist ein rechter Endpunkt:\\$L(S)=\emptyset,\qquad R(S)=\{y\},\qquad V(S)=\emptyset$ lindenmannm@0: \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]\}$ lindenmannm@0: \end{itemize} lindenmannm@0: lindenmannm@0: \subsubsection{Analyse} lindenmannm@0: Eingabe wird Anfangs sortiert und in Array gespeichert lindenmannm@0: \[T(n)=2T(\frac{n}{2}+an+\text{Größe der Ausgabe}\] lindenmannm@0: \[T(1)=O(1)\] lindenmannm@0: \[O(n \log n + k \mid k=\#Schnittpunkte\] lindenmannm@0: lindenmannm@0: \subsection{Polynomprodukt und Fast Fourier-Transformation} lindenmannm@0: lindenmannm@0: lindenmannm@1: \newpage lindenmannm@0: \section{Randomisierung} lindenmannm@0: \subsection{Hashing} lindenmannm@0: lindenmannm@0: \newpage lindenmannm@0: \section{Amortisierte Analyse} lindenmannm@0: \subsection{Binomial Heaps} lindenmannm@0: \subsection{Fibonacci Heaps} lindenmannm@0: \subsection{Union Find} lindenmannm@0: lindenmannm@0: \newpage lindenmannm@0: \section{Greedy} lindenmannm@1: \subsection{Kürzeste (billigste) Wege} lindenmannm@0: lindenmannm@0: \newpage lindenmannm@1: \section{Bin Packing} lindenmannm@1: \textbf{Problembeschreibung:}\\ lindenmannm@1: Man hat $n$ Objekte verschiedener Größe mit $0\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. lindenmannm@1: lindenmannm@1: \subsubsection{Next Fit (NF)} lindenmannm@1: 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.\\ lindenmannm@1: \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$.\\ lindenmannm@1: \textbf{Beweis}\\ lindenmannm@1: (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!\\ lindenmannm@1: (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)\\ lindenmannm@1: Laufzeit für Inputfolgen der Länge $n$: NF $O(n)$ lindenmannm@1: \subsubsection{First-Fit (FF)} lindenmannm@1: Packe nächstes Objekt in die erste Kiste, in die es noch hineinpasst, wenn es eine solche Kiste gibt, sonst in eine neue Kiste.\\ lindenmannm@1: \textbf{Beobachtung}: Zu jedem Zeitpunkt kann es höchstens eine Kiste geben, die weniger als halb voll ist. ($\implies FF(I) \leq 2OPT(I)$)\\ lindenmannm@1: \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)$.\\ lindenmannm@1: \textbf{Beweis}\\ lindenmannm@1: (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.\\ lindenmannm@1: Laufzeit für Inputfolgen der Länge $n$: FF $O(n^2) \rightarrow O(n \log n)$ lindenmannm@1: \subsubsection{Best-Fit (BF)} lindenmannm@1: Verpacke das nächste Objekt in diejenige Kiste, in die es am besten passt (d.h. den geringsten Platz ungenutzt lässt). lindenmannm@1: Verhalten von BF ähnlich zu FF. lindenmannm@1: Laufzeit für Inputfolgen der Länge $n$: BF $O(n^2) \rightarrow O(n \log n)$ lindenmannm@1: \subsection{Offline Verfahren} lindenmannm@1: \underline{NP-schwieriges Problem! Entscheidungsproblem ist NP-vollständig!}\\ lindenmannm@1: Zunächst wird die Anzahl $n$ und alle $n$ Objekte vorgegeben. Dann beginnt die Verpackung.\\ lindenmannm@1: $n$ und $s_1, ..., s_n$ sind gegeben, bevor die Verpackung beginnt!\\ lindenmannm@1: $\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!\\ lindenmannm@1: Idee für Offline Approximationsalgorithmen: Sortiere die Objekte zunächst nach abnhemender Größe und verpacke größere Objekte zuerst! lindenmannm@1: \subsubsection{First Fit Decreasing (FFD oder FFNI)} lindenmannm@1: \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}$.\\ lindenmannm@1: \textbf{Beweis}: \$\$\$TODO:Elsässer hat das in seiner VL gemacht - aber hässlich lang\$\$\$\\ lindenmannm@1: \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$.\\ lindenmannm@1: \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?\$\$\$\\ lindenmannm@1: \textbf{Satz}: Für alle Inputfolgen I gilt $FFD(I)\leq(4 OPT(I)+\frac{1}{3})$.\\ lindenmannm@1: \textbf{Satz}: lindenmannm@1: \begin{itemize} lindenmannm@1: \item[1.] Für alle Inputfolgen $I$ gilt: $FFD(I)\leq \frac{11}{9} OPT(I)+4$ lindenmannm@1: \item[2.] Es gibt Inputfolgen $I$ mit: $FFD(I)=\frac{11}{9}OPT(I)$. lindenmannm@1: \end{itemize} lindenmannm@1: \textbf{Beweis}: \$\$\$TODO\$\$\$ lindenmannm@1: \subsubsection{Best Fit Decreasing (BFD)} lindenmannm@1: Nicht im Script??? lindenmannm@1: lindenmannm@1: \newpage lindenmannm@1: \section{Dynamische Programmierung} lindenmannm@1: lindenmannm@1: lindenmannm@1: \newpage lindenmannm@1: \begin{appendix} lindenmannm@1: \section{Landau-Symbole} lindenmannm@0: \begin{figure}[H] lindenmannm@0: \centering lindenmannm@0: \includegraphics[scale=0.45]{img/landau_sym} lindenmannm@0: \caption{Definition der Landau Symbole} lindenmannm@0: \label{fig:landau_sym} lindenmannm@0: \end{figure} lindenmannm@1: \end{appendix} sawine@2: \end{document}