\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<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.

        \subsection{Online Verfahren}

            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.\\

            Kein Online Bin Packing Verfahren kann stets eine optimale Lösung finden!\\            

            \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.\\

            \textbf{Beweis} Annahme: Online Bin Packing Algorithmus benötigt stets weniger als $\frac{4}{3}OPT$ Bins.\\

            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.

            \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}