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

\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$] Optimierungs-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}\label{ch:qs}

Wähle beliebiges Pivot Element $v$ (meist das letzte Element in der

Input-Folge!) 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{Algorithmus}

\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus Quicksort,

captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,

basicstyle=\footnotesize]{./code/quicksort.code}

\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 (TODO)}

%TODO

\newpage

\section{Randomisierung}

\begin{itemize}

  \item Klassen von randomisierten Algorithmen

  \begin{itemize}

    \item \textbf{Las Vegas}: \underline{immer} Korrekt, erwartete Laufzeit

    (randomisierter Qicksort)

    \item \textbf{Monte Carlo}: \underline{wahrscheinlich} (MC:mostly correct)

    Korrekt, garantierte Laufzeit (randomisierter Primzahltest)

  \end{itemize}

  \item Randomisierter Quicksort

  \item Randomisierter Primzahltest

  \item Kryptographie

\end{itemize}

\subsection{Randomisierter Quicksort}

  Refer to \ref{ch:qs} for basic description of the algorithm.\\

  Problem von Quicksort: bisher nimmt Quicksort immer das letzte Element in der

  Folge $\implies$ Worst-Case: sortierte Folge als Eingabe ($\Theta(n^2)$).

  Ziel: keine quadratische Laufzeit.\\

  Lösung: randomisierte Auswahl des Pivotelements an Stelle $i$. Anschließend

  tauschen von Position $i$ und $r$ (mit $r$=rechte Grenze des zu sortierenden

  Segments).

  \subsubsection{Analyse}

  \textbf{Analyse 1: erwartete Laufzeit}\\

  Mit Wahrscheinlichkeit $\frac{1}{n}$ wird das $i$-kleinste Element $S_i$

  gewählt wobei $n$ zu sortierenden Elemente vorhanden sind. Abhängig von der

  Wahl von $S_i$ ergeben sich Teilprobleme der Größe $i-1$ und $n-i$. Damit

  ergibt sich für die Laufzeit $T(n)$.

  \[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+\]

  \[\frac{1}{n}(T(n-1)+T(0))+\Theta(n))\mid

  \Theta(n)\text{ für partition}\]

  \[=\frac{1}{n}\sum_{k=1}^n(T(k-1)+T(n-k))+\Theta(n)\]

  \[\frac{2}{n}\sum_{k=1}^nT(k-1)+\Theta(n)\]

  \[=O(n \log n)\]

  \textbf{Analys 2: Erwartete Anzahl der Vergleiche}\\

  $x_{ij}=

  \begin{cases}

  	1&\text{falls }S_i\text{ mit }S_j\text{ verglichen wird}\\

  	0&\text{sonst}

  \end{cases}$

  \[E\left[\sum_{i=1}^n\sum_{j>1}x_{ij}\right]=\sum_{i=1}^n\sum_{j>1}E[x_{ij}]\]

  $p_{ij} =$ Wahrscheinlichkeit $S_i$ wird mit $S_j$ verglichen

  \[E[x_{ij}=1\cdot p_{ij}+0\cdot(1-p_{ij}=p_{ij}\]

\subsection{Randomisierter Primzahltest (TODO)}

%TODO schnelle exponentiation

\subsection{RSA (TODO)}

%TODO

%erw. Euklid

\subsection{Treaps (TODO)}

%TODO haben wir nicht so im detail gemacht wie Elsässer!

\subsection{Hashing (TODO)}

%TODO

\newpage

\section{Amortisierte Analyse (TODO)}

%TODO

\subsection{Binomial Heaps (TODO)}

%TODO

\subsection{Fibonacci Heaps (TODO)}

%TODO

\subsection{Union Find (TODO)}

%TODO

\newpage

\section{Greedy}

Momentan beste Teillösung wählen. Die Summe dieser optimalen Teillösung ergibt

die gesamt Lösung. Möglicher Zustand der Gesamtlösung:

\begin{itemize}

  \item Wir erhalten die optimale Gesamtlösung.

  \item Wir erhalten eine Lösung, die zwar nicht immer optimal ist, aber vom

  Optimum stets nur wenig abweicht.

  \item Die berechnete Lösung kann beliebig schlecht werden.

\end{itemize}

\underline{Beispiele:}

\begin{itemize}

  \item Münzwechselproblem\\\textbf{Ziel:} Bezahlung eines Betrages in möglichst

  wenig Münzen und Banknoten.\\\textbf{Lösung (Greedy):} Wähle die maximale

  Anzahl von Banknoten und Münzen mit jeweils größtmöglichem Wert, bis der

  gewünschte Betrag erreicht ist. (Dies führt nur für bestimmte Werte der

  Zahlungsmittel zur optimalen Gesamtlösung!)

  \item Handlungsreisenden-Problem (Traveling Sales Man Problem,

  TSP)\\\textbf{Ziel:} Finden der billigsten Rundreise, diealle Orte genau

  einmal besucht.\\\textbf{Lösung (Greedy):} Gehe immer den günstigsten Weg vom

  aktuellen Knoten zu einem noch nicht besuchten Knoten. Wenn alle besucht

  wurden, kehre zum Anfang zurück. (Mit Greedy keine optimale Gesamtlösung!)

  \item Aktivitäten Auswahlproblem\\\textbf{Ziel:} möglichst viele Anfragen

  erfüllen. (Muss nicht bedeuten, dass die Ressource optimal

  genutzt wird!)\\\textbf{Lösung (Greedy):} Nimm die Anfrage, die am frühesten

  fertig ist. (optimale Gesamtlösung!)\\\textbf{Analyse:} $\Theta(n)$

\end{itemize}

\subsection{Kürzeste (billigste) Wege}

Pfad $P=$ Folge von Knoten.

Kosten eines Pfades:\[c(P)=\sum_{i=0}^{P.length-1}c(v_i,v_{i+1}\]

Entfernung von $v$ nach $w$ sind die Kosten des

günstigsten Pfades:\[dist(v,w)=inf{c(P)\mid P\text{= Weg von v nach

w}}\]

Kosten eines unerreichbaren Knoten sind definiert als $\infty$. Kosten eines

Pfades in einem negativen Zyklus: $-\infty$. Es können also nur Graphen ohne

negative Zyklen sinnvoll betrachtet werden!

\subsubsection{Single Source Shortest Paths}

Kürzeste/Günstigste Pfade von einem Knoten $s$ zu allen anderen Knoten. Hierfür

nutzt man die Dreiecksungleichung über $dist(u,v)\mid (u,v)\in E$ und $s\in V$:

\[dist(s,v)\leq dist(s,u)+dist(u,v)\]

\textbf{Greedy-Ansatz}

\begin{itemize}

  \item Überschätze die dist-Funktion \[dist(s,v)=\begin{cases}0&\text{ falls }

  v=s\\\infty&\text{ falls }v\neq s\end{cases}\]

  \item Solange eine Kante $e=(u,v)$ existiert mit

  $dist(s,v)>dist(s,u)+c(u,v)$ setze $dist(s,v)=dist(s,u)+c(u,v)$

\end{itemize}

Durch die Überschätzung kann die Dreicksungleichung nur noch für Knoten $s$ und

seine direkten Nachfolger verletzt werden!\\Alle folgenden Verfahren basieren

auf diesem Prinzip!\\

%Elsässer führt einige Lemmas ein und beweist sie - diese beziehen sich auf den

% ersten optimimierten Algorithmus und diesen erachte ich in Relation zu

% Dijkstra als irrelevant!

\textbf{Effiziente Implementierungen}

Diese sind im Allgemeinen nicht bekannt, jedoch für wichtige Spezialfälle.

\begin{itemize}

  \item Nicht-negative Netzwerke: \underline{Dijkstra}

  \item Netzwerke ohne negative Zyklen: \underline{Bellman-Ford}

  \item Azyklische Netzwerke

\end{itemize}

\underline{Dijkstra}

\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von

Dijkstra, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,

basicstyle=\footnotesize]{./code/dijkstra.code}

Dijkstra Beispiel:

\begin{figure}

	\centering

	\includegraphics[scale=0.6]{img/dijkstraExT}

	\caption{Tree for Dijkstra Example}

	\label{fig:dijExT}

\end{figure}

\begin{table}[ht]

    \centering

    \begin{tabular}{|c c c c c c c|c|}

        \hline

        \multicolumn{7}{|c|}{DIST[v]} & \\

        \hline

        s & a & b & c & d & e & f & U\\\hline\hline

		0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & s,a,b,c,d,e,f\\

		0* & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & a,b,c,d,e,f\\

		0* & 6 & 7 & 5* & $\infty$ & $\infty$ & $\infty$ & a,b,d,e,f\\

		0* & 6* & 7 & 5* & $\infty$ & $\infty$ & 14 & b,d,e,f\\

		0* & 6* & 7* & 5* & 9 & 10 & 14 & d,e,f\\

		0* & 6* & 7* & 5* & 9* & 10 & 11 & e,f\\

		0* & 6* & 7* & 5* & 9* & 10* & 11 & f\\

		0* & 6* & 7* & 5* & 9* & 10* & 11* & $\emptyset$\\\hline

    \end{tabular}

    \caption{Dijkstra Example}\label{tab:dijEx}

\end{table}

Komplexität:

\[O(n\cdot(T_{insert}+T_{Empty}+T_{DeleteMin})+m\cdot T_{DecreaseKey}+m+n)\]

Implementierung mit Fibonaci-Heaps:\\

$T_{Insert}:O(1)$\\

$T_{DeleteMin}:O(\log n)$ (amortisiert)\\

$T_{DecreaseKey}:O(1)$ (amortisiert)

\[O(n\log n+m)\]

\underline{Bellman-Ford}

\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von

Belman-Ford, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,

basicstyle=\footnotesize]{./code/BelmanFord.code}

\underline{Azyklische Netzwerke}

\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus für

Azyklische Netzwerke, captionpos=b, numbers=left, numberstyle=\tiny,

numbersep=5pt, basicstyle=\footnotesize]{./code/AzyklischeNetzwerke.code}

\subsection{Spannbäume minimalen Gewichts}

Ungerichteter Graph $G=(V,E)$, Kostenfunktion $c:E\rightarrow R$.\\Sei

$T\subseteq E$ ein Baum (zusammenhängender azyklischer Teilgraph) Kosten von T:

$c(T)=\sum_{(u,v)\in T}c(u,v)$.\\Ein minimaler Spannbaum ist ein Baum

$T\subseteq E$, der alle Knoten in $V$ verbindet minimale Kosten hat.

\subsubsection{Das Wachsen von min. Spannbäumen}

\textbf{Invariante:} Verwalte Menge $A\subseteq E$, die Teilmenge eines

minimalen Spannbaums ist.\\

\textbf{Definition:} Eine Kante $(u,v)\in E\backslash A$ ist sicher für $A$, wenn

$A\cup {(u,v)}$ Teilmenge eines minimalen Spannbaums ist.

\lstinputlisting[language=Java,label=lst:TTlookup,caption=Greedy Algorithmus für

Spannbäume, captionpos=b, numbers=left, numberstyle=\tiny,

numbersep=5pt, basicstyle=\footnotesize]{./code/spannbaeumeGreedy.code}

\subsubsection{Schnitte}

Ein Schnitt $(S,V\backslash S)$ ist eine Partition von $V$. Eine Kante $(u,v)$

schneidet $(S,V\backslash S)$, wenn ein Endpunkt in $S$ und der andere in

$V\backslash S$ liegt.\\Ein Schnitt "`respektiert $A$"', wenn keine Kante aus

$A$ den Schnitt schneidet.\\Eine Kante heißt minimal bzgl. eines Schnitts, wenn

sie den Schnitt schneidet und unter allen solchen Kanten minimale Kosten hat.

\subsubsection{Sichere Kanten}

\textbf{Satz:} Sei $A$ Teilmenge eines minimalen Spannbaums $T$ und

$(S,V\backslash S)$ ein Schnitt, der $A$ respektiert. Ist $(u,v)$ eine minimale

Kante bzgl. $(S,V\S)$, dann ist $(u,v)$ sicher für $A$.\\

\textbf{Beweis}: \begin{itemize}

  \item[1. Fall] $(u,v)\in T$ : ok

  \item[2. Fall] $(u,v)\not\in T$ : Wir konstruieren minimalen Spannbaum $T'$

  mit $(u,v)\in T'$ und $A\subseteq T'$.

\end{itemize}

\subsubsection{Der Graph $G_A$}

\[G_A=(V,A)\]

\begin{itemize}

  \item ist ein \underline{Wald}, d.h. eine Menge von Bäumen

  \item anfangs, wenn $A=\emptyset$, ist jeder Baum ein einzelner Knoten

  \item eine sichere Kante verbindet verschiedene Bäume

\end{itemize}

\textbf{Korollar:} Sei $B$ ein Baum in $G_A=(V,A)$. Ist $(u,v)$ eine Kante

minimaler Kosten, die $B$ und einen anderen Baum in $G_A$ verbindet, dann ist

$(u,v)$ sicher für A.

\subsubsection{Algorithmus von Kruskal}

Wähle stets eine Kante minimaler Kosten, die zwei Bäume $B_1$ und $B_2$ in $G_A$

verbindet.

\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von

Kruskal, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,

basicstyle=\footnotesize]{./code/spannbaeumeKruskal.code}

Laufzeit: $O(m\alpha(n)+m+m\log n)$

\subsubsection{Algorithmus von Prim}

$A$ ist immer ein einziger Baum. Starte mit einem beliebigen Wurzelknoten $w$.

Füge in jedem Schritt eine minimale Kante hinzu, die einen Knoten in $A$ mit

einem Knoten in $V\backslash A$ verbindet.

\textbf{Implementierung}\\$Q$: Prioritätenwarteschlange, die alle Knoten $v\in

V\backslash A$ enthält.\\Schlüssel von $v$: minimale Kosten einer Kante, die $v$

mit einem Knoten aus $A$ verbindet.\\Für einen Knoten $v$ ist $p[v]$ der

Elter-Knoten von $v$ in dem Baum.\[A={(v,p[v]):v\in V-{w}-Q}\]

\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von

Prim, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,

basicstyle=\footnotesize]{./code/spannbaeumePrim.code}

Laufzeit: $O(n\log n+m)$

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

%TODO Nicht im Script???

\newpage

\section{Dynamische Programmierung}

\textbf{Idee:} Speichern von zwischen Ergebnissen, welche sonst mehrfach

berechnet werden müssten.\\

\textbf{Vorgehen:}

\begin{itemize}

  \item Rekursive Beschreibung des Problems P

  \item Bestimmung einer Menge T, die alle Teilprobleme von P enthält, auf die

  bei der Lösung von P zugegriffen wird.

  \item Bestimmung einer Reihenfolge $T_0,\ldots T_k$ der Probleme in T, so dass

  bei der Lösung von $T_i$ nur auf Probleme $T_j$ mit $j<i$ zurückgegriffen

  wird.

  \item Sukzessive Berechnung und Speicherung von Lösungen für $T_0,\ldots T_k$.

\end{itemize}

Wird im Script anhand der Fibonacci Zahlen demonstriert aber ist trivial \ldots

\subsection{Matrixkettenprodukt (TODO)}

%TODO

\subsection{Optimale Suchbäume (TODO)}

%TODO

\subsection{Editierdistanz}

Berechne für zwei gegebene Zeichenfolgen $A$ und $B$ möglichst effizient die

Editier-Distanz $D(A,B)$ und eine minimale Folge von Editieroperationen, die

$A$ in $B$ überführt.\\

\textbf{Editieroperationen:}

\begin{itemize}

  \item Ersetzen eines Zeichens von $A$ durch ein Zeichen von $B$

  \item Löschen eines Zeichens von $A$

  \item Einfügen eines Zeichens von $B$

\end{itemize}

\textbf{Einheitskostenmodell:}

\[c(a,b)=\begin{cases}1 & \text{falls } a\neq b\\0 & \text{falls } a=b\end{cases}\]

$a=\epsilon, b=\epsilon$ möglich Dreiecksungleichung soll für $c$ im

allgemeinen gelten:

\[c(a,c)\leq c(a,b)+c(b,c)\]

$\rightarrow$ ein Buchstabe wird höchstens einmal

verändert.\\

Rekursionsgleichung, falls $m,n\geq 1$ 

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

Anfangsbedingung:\\

\[D_{0,0}=D(\epsilon,\epsilon)=0\]

\[D_{0,j}=D(\epsilon,B_j)=j\]

\[D_{i,0}=D(A_i,\epsilon)=i\]

\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus zur

Editierdistanz, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,

basicstyle=\footnotesize]{./code/editierdistanz.code}

\textbf{Spurgraph:}\\

Übersicht über alle möglichen Spuren zur Transformation von $A$ in $B$,

gerichtete Kanten von Knoten $(i,j)$ zu $(i+1,j)$, $(i,j+1)$ und $(i+1,j+1)$.

Gewichtung der Kanten entspricht den Editierkosten. Kosten nehmen entlang eines

optimalen Weges monoton zu. Jeder Weg mit monotin wachsenden Kosten von der

linken oberen Ecke zur rechten unteren Ecke entspricht einer optimalen Spur. Zur

Berechnung der Spur der minimalen Editieroperationen (es gibt mehrere

Lösungen), kann folgender Algorithmus verwendet werden:

\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus zum Spurgraphen, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\footnotesize]{./code/spurgraph.code}

\section{Suche in Texten}

\underline{Gegeben:} Text T $t_1t_2t_3\ldots t_n\in\Sigma^n$ und

rin Muster P $p_1p_2p_3\ldots p_m\in\Sigma^m$\\

\underline{Gesucht:} Ein oder alle Vorkommen des Musters im Text, d.h.

Verschiebungen $i$ mit $0\leq i\leq n-m$.\\

\textbf{Naives Verfahren:} iteriere über den Text und suche das Muster. Aufwand:

$m\cdot(n-m+1)$ Vergleiche $\implies \Omega(n\cdot m)$

\textbf{Verfahren nach Knuth-Morris-Pratt (KMP):} 

Präffix=Suffix Verfahren. Daraus resultiert eine Shiftmöglichkeit des Musters

über den Text. Der Shift geschieht um $next[j]$=Länge des längsten Präfix von

$P$, das echtes Suffix von $P_{1\ldots j}$ ist, wobei $j=$Position des letzten

Vergleiches.\\

\underline{Erstellung des $next[j]$ arrays über P.}\\

$P=0101101011$

\begin{table}[H]

	\centering

	\begin{tabular}{c|c|c|c|c|c|c|c|c|c}

		1&2&3&4&5&6&7&8&9&10\\\hline

		0&1&0&1&1&0&1&0&1&1\\\hline

		 & &0& & & & & & & \\

		 & &0&1& & & & & & \\

		 & & & & &0& & & & \\

		 & & & & &0&1& & & \\

		 & & & & &0&1&0& & \\

		 & & & & &0&1&0&1& \\

		 & & & & &0&1&0&1&1\\

	\end{tabular}

	\caption{next[j] Beispiel}

	\label{tab:nextJ}

\end{table}

$\rightarrow next[j]=[0,0,1,2,0,1,2,3,4,5]$\\

\underline{Algorithmus:}

\lstinputlisting[language=Java,label=lst:TTlookup,caption=KMP Algorithmus,

captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\footnotesize]{./code/kmp.code}

\underline{Analyse:}

inkrement $j$ = inkrement $i$ und dekrement $j$ = inkrement $j$!

$\rightarrow O(n)$ hinzu kommt noch die Berechnung des next-arrays mit $O(m)$.\\

KMP kann also mit $O(n+m)$ berechnet werden. (i.e. Untere Schranke

$\Omega(m+n/m)$)

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