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