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