lindenmannm@3: \documentclass[a4paper,11pt,twoside]{article}
lindenmannm@3: 
lindenmannm@3: \usepackage[ngerman]{babel} \usepackage[T1]{fontenc}
lindenmannm@3: \usepackage[latin1]{inputenc}
lindenmannm@3: \usepackage[colorlinks=true,linkcolor=black]{hyperref}
lindenmannm@3: 
lindenmannm@3: \usepackage{vaucanson-g}
lindenmannm@3: \usepackage{hyperref}
lindenmannm@3: \usepackage{hypcap}
lindenmannm@3: \usepackage{fancyhdr}
lindenmannm@3: \usepackage{graphicx}
lindenmannm@3: \usepackage{lastpage}
lindenmannm@3: \usepackage[cm]{fullpage}
lindenmannm@3: \usepackage{amsthm, amsmath, amsfonts}
lindenmannm@3: \usepackage{float}
lindenmannm@3: \usepackage{paralist}
lindenmannm@3: \usepackage{listings}
lindenmannm@3: \usepackage{color}
lindenmannm@3: \usepackage{bookmark}
lindenmannm@3: 
lindenmannm@3: \bibliographystyle{alphadin}
lindenmannm@3: 
lindenmannm@3: \title{\underline{Exzerpt Algorithmentheorie WS10/11}}
lindenmannm@3: \author{Markus Lindenmann}
lindenmannm@3: \date{\today{} }
lindenmannm@3: 
lindenmannm@3: \begin{document}
lindenmannm@3: \maketitle
lindenmannm@3: 
lindenmannm@3: \tableofcontents \newpage
lindenmannm@3: 
lindenmannm@3: \section{Einleitung}\label{sec:intro}
lindenmannm@3: Dozent:     Matthias Westermann\\
lindenmannm@3: Website:    \url{http://lak.informatik.uni-freiburg.de}\\
lindenmannm@3: Klausur:    09.03.2011\\
lindenmannm@3: Hilfsmittel:    Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt
lindenmannm@3: \subsection{Themen:}
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item[$\bullet$] Divide and Conquer
lindenmannm@3:   \item[$\bullet$] Greedy Prinzip
lindenmannm@3:   \item[$\bullet$] Dynamische Programmierung
lindenmannm@3:   \item[$\bullet$] Randomisierung
lindenmannm@3:   \item[$\bullet$] Amortisierte Analyse
lindenmannm@3: \end{itemize}
lindenmannm@3: \subsection{Problem-/Anwendungsbereiche:}
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item[$\bullet$] Geometrische Algorithmen
lindenmannm@3:   \item[$\bullet$] Algebraische Algorithmen
lindenmannm@3:   \item[$\bullet$] Graphenalgorithmen
lindenmannm@3:   \item[$\bullet$] Datenstrukturen
lindenmannm@3:   \item[$\bullet$] Internet-Algorithmen
lindenmannm@3:   \item[$\bullet$] Optimierungs-Verfahren
lindenmannm@3:   \item[$\bullet$] Zeichenkettenverarbeitung
lindenmannm@3: \end{itemize}
lindenmannm@3: \subsection{Literatur:}
lindenmannm@3: \bibliography{literatur}
lindenmannm@3: \nocite{*}
lindenmannm@3: 
lindenmannm@3: \newpage
lindenmannm@3: \section{Divide and Conquer}\label{sec:div&conq}
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item[$\bullet$] Quicksort
lindenmannm@3:   \item[$\bullet$] Formulierung und Analyse des Prinzips
lindenmannm@3:   \item[$\bullet$] Geometrisches Devide and Conquer
lindenmannm@3:   \begin{itemize}
lindenmannm@3:     \item[-] Closest-Pair
lindenmannm@3:     \item[-] Segmentschnitt
lindenmannm@3:   \end{itemize}
lindenmannm@3: \end{itemize}
lindenmannm@3: 
lindenmannm@3: \subsection{Formulierung des Divide and Conquer Prinzips}
lindenmannm@3: D\&C Verfahren zur Lösung eines Problems der Größe $n$
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \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@3:   \item[2.]   Conquer\\Löse die $k$ Teilprobleme auf dieselbe Art (rekursiv)
lindenmannm@3:   \item[3.]   Merge\\Füge die berechneten Teillösungen zu einer Gesamtlösung zusammen
lindenmannm@3: \end{itemize}
lindenmannm@3: 
lindenmannm@3: \subsection{Quicksort}\label{ch:qs}
lindenmannm@3: Wähle beliebiges Pivot Element $v$ (meist das letzte Element in der
lindenmannm@3: Input-Folge!) und sortiere alle Elemente aus der Menge, die größer sind als $v$
lindenmannm@3: rechts von $v$ ein, die anderen links. Verfahre im selben Muster mit den neuen
lindenmannm@3: Teilmengen links und rechts des Pivot Elements. Wenn die zu sortierende Folge
lindenmannm@3: $F$ nur ein Element beinhaltet, gebe $F$ zurück.
lindenmannm@3: \subsubsection{Algorithmus}
lindenmannm@3: \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus Quicksort,
lindenmannm@3: captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
lindenmannm@3: basicstyle=\footnotesize]{./code/quicksort.code}
lindenmannm@3: 
lindenmannm@3: \subsubsection{Analyse}
lindenmannm@3: $T(n)$ - maximale Anzahl von Schritten, um ein Problem der Größe $n$ zu lösen.
lindenmannm@3: \[T(n)=\begin{cases}n\neq c&a \\ n>c&T(n_1+\ldots+T(n_k)+\text{Divide- und Mergeaufwand}\end{cases}\]
lindenmannm@3: Best Case: $k=2, n_1=n_2=\frac{n}{2}$\\
lindenmannm@3: Divide- und Mergeaufwand: $DM(n)$\\
lindenmannm@3: $T(1)=a$\\
lindenmannm@3: $T(n)=2T(\frac{n}{2})+DM(n)$
lindenmannm@3: 
lindenmannm@3: \subsection{Nächste Paare}
lindenmannm@3: Eingabe:    $n$ Punkte in Ebene\\
lindenmannm@3: Ausgabe:    Punkt-Paar $q,r$ mit geringstem Abstand\\
lindenmannm@3: Abstand:    $d(q,r)$ bechreibt Abstand zwischen Punkten $q$ und $r$
lindenmannm@3: \subsubsection{Algorithmus}
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item[$\bullet$] sortiere Punktmenge nach x-Koordinate
lindenmannm@3:   \item[$\bullet$] Teile Punktmenge in der Mitte L in die Mengen Q und R
lindenmannm@3:   \item[$\bullet$] Löse rekursiv auf Q und R
lindenmannm@3:   \item[$\bullet$] Sortiere Punkte nach y-Koordinate
lindenmannm@3:   \item[$\bullet$] Teste alle Paare, deren Abstand in der
lindenmannm@3:   Sortierung kleiner als 16 ist (siehe unten)
lindenmannm@3:   \item[$\bullet$] Füge zusammen
lindenmannm@3: \end{itemize}
lindenmannm@3: 
lindenmannm@3: $\delta=$ Minimum der Teillösungen\\
lindenmannm@3: 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@3: \textbf{Problem:} alle Punkte können innerhalb der $\delta$-Zone liegen\\
lindenmannm@3: \textbf{Lösung:}\begin{itemize}
lindenmannm@3: \item[$\bullet$] Sortiere Punkte in $\delta$ Zone nach $y$-Abstand
lindenmannm@3: \item[$\bullet$] Liegen in dieser Sortierung mehr als $c$ Punkte zwischen $q$ und $r$, dann kann $(q,r)$ nicht nächstes Paar sein
lindenmannm@3: \end{itemize}
lindenmannm@3: 
lindenmannm@3: Dies kann für $c=15$ bewiesen werden (vgl. Abbildung \ref{cl_pair}):
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item[$\bullet$] Seien min. 15 Punkte zwischen $q$ und $r$
lindenmannm@3:   \item[$\bullet$] Dann sind mindestens 3 Reihen Quadrate zwischen $q,r$, weil in jedem Quadrat höchstens ein Punkt ist.
lindenmannm@3:   \item[$\rightarrow$] Dann muss $d(q,r)$ mindestens $\frac{3}{2}\delta > \delta$ sein.
lindenmannm@3: \end{itemize}
lindenmannm@3: 
lindenmannm@3: \begin{figure}[H]
lindenmannm@3: \centering
lindenmannm@3: \includegraphics[scale=0.5]{img/cl_pair}
lindenmannm@3: \caption{Nächste Paare: Prüf Distanz}
lindenmannm@3: \label{cl_pair}
lindenmannm@3: \end{figure}
lindenmannm@3: 
lindenmannm@3: \subsubsection{Analyse}
lindenmannm@3: \[T(n)=\begin{cases}n\leq3&a \\ n>3&2T(\frac{n}{2})+an\end{cases}\]
lindenmannm@3: \[T(n)\leq an \log n \]
lindenmannm@3: 
lindenmannm@3: \subsection{Segmentschnitt}
lindenmannm@3: Eingabe:    Menge S bestehend aus vertikalen Segmenten und Endpunkten vn horizontalen Segmenten\\
lindenmannm@3: Ausgabe:    Alle Schnittpunkte von vertikalen Segmenten mit horizontalen Segmenten, von denen mindesens ein Endpunkt in S ist
lindenmannm@3: 
lindenmannm@3: \subsubsection{Algorithmus}
lindenmannm@3: \textbf{Divide \& Conquer:}\\Fallunterscheidung
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \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@3:   \item[2.] else: S enthält keine Schnitte
lindenmannm@3: \end{itemize}
lindenmannm@3: 
lindenmannm@3: \textbf{Merge}\\
lindenmannm@3: Bilde L(S), R(S) und V(S) (Definition am Beispiel $i=1,2$ berechnet: $S=S_1\cup S_2$):
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \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@3:   \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@3:   \item[$\bullet$] V(S): y-Intervalle der vertikalen Segmente in S\\$=V(S_1)\cup V(S_2)$
lindenmannm@3: \end{itemize}
lindenmannm@3: L,R sortiert nach steigender y-Koordinate\\
lindenmannm@3: V sortiert nach steigendem unteren Endpunkt\\
lindenmannm@3: \medskip
lindenmannm@3: 
lindenmannm@3: \textbf{Basisfälle}\\
lindenmannm@3: S enthält nur ein Element s. Fallunterscheidung:
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item[1.] $s=(x,y)$ ist ein linker Endpunkt:\\$L(S)=\{y\},\qquad R(S)=\emptyset,\qquad V(S)=\emptyset$
lindenmannm@3:   \item[2.] $s=(x,y)$ ist ein rechter Endpunkt:\\$L(S)=\emptyset,\qquad R(S)=\{y\},\qquad V(S)=\emptyset$
lindenmannm@3:   \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@3: \end{itemize}
lindenmannm@3: 
lindenmannm@3: \subsubsection{Analyse}
lindenmannm@3: Eingabe wird Anfangs sortiert und in Array gespeichert
lindenmannm@3: \[T(n)=2T(\frac{n}{2}+an+\text{Größe der Ausgabe}\]
lindenmannm@3: \[T(1)=O(1)\]
lindenmannm@3: \[O(n \log n + k \mid k=\#Schnittpunkte\]
lindenmannm@3: 
lindenmannm@3: \subsection{Polynomprodukt und Fast Fourier-Transformation (TODO)}
lindenmannm@3: %TODO
lindenmannm@3: 
lindenmannm@3: \newpage
lindenmannm@3: \section{Randomisierung}
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item Klassen von randomisierten Algorithmen
lindenmannm@3:   \begin{itemize}
lindenmannm@3:     \item \textbf{Las Vegas}: \underline{immer} Korrekt, erwartete Laufzeit
lindenmannm@3:     (randomisierter Qicksort)
lindenmannm@3:     \item \textbf{Monte Carlo}: \underline{wahrscheinlich} (MC:mostly correct)
lindenmannm@3:     Korrekt, garantierte Laufzeit (randomisierter Primzahltest)
lindenmannm@3:   \end{itemize}
lindenmannm@3:   \item Randomisierter Quicksort
lindenmannm@3:   \item Randomisierter Primzahltest
lindenmannm@3:   \item Kryptographie
lindenmannm@3: \end{itemize}
lindenmannm@3: \subsection{Randomisierter Quicksort}
lindenmannm@3:   Refer to \ref{ch:qs} for basic description of the algorithm.\\
lindenmannm@3:   Problem von Quicksort: bisher nimmt Quicksort immer das letzte Element in der
lindenmannm@3:   Folge $\implies$ Worst-Case: sortierte Folge als Eingabe ($\Theta(n^2)$).
lindenmannm@3:   Ziel: keine quadratische Laufzeit.\\
lindenmannm@3:   Lösung: randomisierte Auswahl des Pivotelements an Stelle $i$. Anschließend
lindenmannm@3:   tauschen von Position $i$ und $r$ (mit $r$=rechte Grenze des zu sortierenden
lindenmannm@3:   Segments).
lindenmannm@3:   \subsubsection{Analyse}
lindenmannm@3:   \textbf{Analyse 1: erwartete Laufzeit}\\
lindenmannm@3:   Mit Wahrscheinlichkeit $\frac{1}{n}$ wird das $i$-kleinste Element $S_i$
lindenmannm@3:   gewählt wobei $n$ zu sortierenden Elemente vorhanden sind. Abhängig von der
lindenmannm@3:   Wahl von $S_i$ ergeben sich Teilprobleme der Größe $i-1$ und $n-i$. Damit
lindenmannm@3:   ergibt sich für die Laufzeit $T(n)$.
lindenmannm@3:   \[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+\]
lindenmannm@3:   \[\frac{1}{n}(T(n-1)+T(0))+\Theta(n))\mid
lindenmannm@3:   \Theta(n)\text{ für partition}\]
lindenmannm@3:   \[=\frac{1}{n}\sum_{k=1}^n(T(k-1)+T(n-k))+\Theta(n)\]
lindenmannm@3:   \[\frac{2}{n}\sum_{k=1}^nT(k-1)+\Theta(n)\]
lindenmannm@3:   \[=O(n \log n)\]
lindenmannm@3:   \textbf{Analys 2: Erwartete Anzahl der Vergleiche}\\
lindenmannm@3:   $x_{ij}=
lindenmannm@3:   \begin{cases}
lindenmannm@3:   	1&\text{falls }S_i\text{ mit }S_j\text{ verglichen wird}\\
lindenmannm@3:   	0&\text{sonst}
lindenmannm@3:   \end{cases}$
lindenmannm@3:   \[E\left[\sum_{i=1}^n\sum_{j>1}x_{ij}\right]=\sum_{i=1}^n\sum_{j>1}E[x_{ij}]\]
lindenmannm@3:   $p_{ij} =$ Wahrscheinlichkeit $S_i$ wird mit $S_j$ verglichen
lindenmannm@3:   \[E[x_{ij}=1\cdot p_{ij}+0\cdot(1-p_{ij}=p_{ij}\]
lindenmannm@3: \subsection{Randomisierter Primzahltest (TODO)}
lindenmannm@3: %TODO schnelle exponentiation
lindenmannm@3: \subsection{RSA (TODO)}
lindenmannm@3: %TODO
lindenmannm@3: %erw. Euklid
lindenmannm@3: \subsection{Treaps (TODO)}
lindenmannm@3: %TODO haben wir nicht so im detail gemacht wie Elsässer!
lindenmannm@3: \subsection{Hashing (TODO)}
lindenmannm@3: %TODO
lindenmannm@3: 
lindenmannm@3: \newpage
lindenmannm@3: \section{Amortisierte Analyse (TODO)}
lindenmannm@3: %TODO
lindenmannm@3: \subsection{Binomial Heaps (TODO)}
lindenmannm@3: %TODO
lindenmannm@3: \subsection{Fibonacci Heaps (TODO)}
lindenmannm@3: %TODO
lindenmannm@3: \subsection{Union Find (TODO)}
lindenmannm@3: %TODO
lindenmannm@3: 
lindenmannm@3: \newpage
lindenmannm@3: \section{Greedy}
lindenmannm@3: Momentan beste Teillösung wählen. Die Summe dieser optimalen Teillösung ergibt
lindenmannm@3: die gesamt Lösung. Möglicher Zustand der Gesamtlösung:
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item Wir erhalten die optimale Gesamtlösung.
lindenmannm@3:   \item Wir erhalten eine Lösung, die zwar nicht immer optimal ist, aber vom
lindenmannm@3:   Optimum stets nur wenig abweicht.
lindenmannm@3:   \item Die berechnete Lösung kann beliebig schlecht werden.
lindenmannm@3: \end{itemize}
lindenmannm@3: \underline{Beispiele:}
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item Münzwechselproblem\\\textbf{Ziel:} Bezahlung eines Betrages in möglichst
lindenmannm@3:   wenig Münzen und Banknoten.\\\textbf{Lösung (Greedy):} Wähle die maximale
lindenmannm@3:   Anzahl von Banknoten und Münzen mit jeweils größtmöglichem Wert, bis der
lindenmannm@3:   gewünschte Betrag erreicht ist. (Dies führt nur für bestimmte Werte der
lindenmannm@3:   Zahlungsmittel zur optimalen Gesamtlösung!)
lindenmannm@3:   \item Handlungsreisenden-Problem (Traveling Sales Man Problem,
lindenmannm@3:   TSP)\\\textbf{Ziel:} Finden der billigsten Rundreise, diealle Orte genau
lindenmannm@3:   einmal besucht.\\\textbf{Lösung (Greedy):} Gehe immer den günstigsten Weg vom
lindenmannm@3:   aktuellen Knoten zu einem noch nicht besuchten Knoten. Wenn alle besucht
lindenmannm@3:   wurden, kehre zum Anfang zurück. (Mit Greedy keine optimale Gesamtlösung!)
lindenmannm@3:   \item Aktivitäten Auswahlproblem\\\textbf{Ziel:} möglichst viele Anfragen
lindenmannm@3:   erfüllen. (Muss nicht bedeuten, dass die Ressource optimal
lindenmannm@3:   genutzt wird!)\\\textbf{Lösung (Greedy):} Nimm die Anfrage, die am frühesten
lindenmannm@3:   fertig ist. (optimale Gesamtlösung!)\\\textbf{Analyse:} $\Theta(n)$
lindenmannm@3: \end{itemize}
lindenmannm@3: 
lindenmannm@3: \subsection{Kürzeste (billigste) Wege}
lindenmannm@3: Pfad $P=$ Folge von Knoten.
lindenmannm@3: Kosten eines Pfades:\[c(P)=\sum_{i=0}^{P.length-1}c(v_i,v_{i+1}\]
lindenmannm@3: Entfernung von $v$ nach $w$ sind die Kosten des
lindenmannm@3: günstigsten Pfades:\[dist(v,w)=inf{c(P)\mid P\text{= Weg von v nach
lindenmannm@3: w}}\]
lindenmannm@3: Kosten eines unerreichbaren Knoten sind definiert als $\infty$. Kosten eines
lindenmannm@3: Pfades in einem negativen Zyklus: $-\infty$. Es können also nur Graphen ohne
lindenmannm@3: negative Zyklen sinnvoll betrachtet werden!
lindenmannm@3: \subsubsection{Single Source Shortest Paths}
lindenmannm@3: Kürzeste/Günstigste Pfade von einem Knoten $s$ zu allen anderen Knoten. Hierfür
lindenmannm@3: nutzt man die Dreiecksungleichung über $dist(u,v)\mid (u,v)\in E$ und $s\in V$:
lindenmannm@3: \[dist(s,v)\leq dist(s,u)+dist(u,v)\]
lindenmannm@3: \textbf{Greedy-Ansatz}
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item Überschätze die dist-Funktion \[dist(s,v)=\begin{cases}0&\text{ falls }
lindenmannm@3:   v=s\\\infty&\text{ falls }v\neq s\end{cases}\]
lindenmannm@3:   \item Solange eine Kante $e=(u,v)$ existiert mit
lindenmannm@3:   $dist(s,v)>dist(s,u)+c(u,v)$ setze $dist(s,v)=dist(s,u)+c(u,v)$
lindenmannm@3: \end{itemize}
lindenmannm@3: Durch die Überschätzung kann die Dreicksungleichung nur noch für Knoten $s$ und
lindenmannm@3: seine direkten Nachfolger verletzt werden!\\Alle folgenden Verfahren basieren
lindenmannm@3: auf diesem Prinzip!\\
lindenmannm@3: %Elsässer führt einige Lemmas ein und beweist sie - diese beziehen sich auf den
lindenmannm@3: % ersten optimimierten Algorithmus und diesen erachte ich in Relation zu
lindenmannm@3: % Dijkstra als irrelevant!
lindenmannm@3: \textbf{Effiziente Implementierungen}
lindenmannm@3: Diese sind im Allgemeinen nicht bekannt, jedoch für wichtige Spezialfälle.
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item Nicht-negative Netzwerke: \underline{Dijkstra}
lindenmannm@3:   \item Netzwerke ohne negative Zyklen: \underline{Bellman-Ford}
lindenmannm@3:   \item Azyklische Netzwerke
lindenmannm@3: \end{itemize}
lindenmannm@3: \underline{Dijkstra}
lindenmannm@3: \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
lindenmannm@3: Dijkstra, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
lindenmannm@3: basicstyle=\footnotesize]{./code/dijkstra.code}
lindenmannm@3: Dijkstra Beispiel:
lindenmannm@3: \begin{figure}
lindenmannm@3: 	\centering
lindenmannm@3: 	\includegraphics[scale=0.6]{img/dijkstraExT}
lindenmannm@3: 	\caption{Tree for Dijkstra Example}
lindenmannm@3: 	\label{fig:dijExT}
lindenmannm@3: \end{figure}
lindenmannm@3: \begin{table}[ht]
lindenmannm@3:     \centering
lindenmannm@3:     \begin{tabular}{|c c c c c c c|c|}
lindenmannm@3:         \hline
lindenmannm@3:         \multicolumn{7}{|c|}{DIST[v]} & \\
lindenmannm@3:         \hline
lindenmannm@3:         s & a & b & c & d & e & f & U\\\hline\hline
lindenmannm@3: 		0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & s,a,b,c,d,e,f\\
lindenmannm@3: 		0* & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & a,b,c,d,e,f\\
lindenmannm@3: 		0* & 6 & 7 & 5* & $\infty$ & $\infty$ & $\infty$ & a,b,d,e,f\\
lindenmannm@3: 		0* & 6* & 7 & 5* & $\infty$ & $\infty$ & 14 & b,d,e,f\\
lindenmannm@3: 		0* & 6* & 7* & 5* & 9 & 10 & 14 & d,e,f\\
lindenmannm@3: 		0* & 6* & 7* & 5* & 9* & 10 & 11 & e,f\\
lindenmannm@3: 		0* & 6* & 7* & 5* & 9* & 10* & 11 & f\\
lindenmannm@3: 		0* & 6* & 7* & 5* & 9* & 10* & 11* & $\emptyset$\\\hline
lindenmannm@3:     \end{tabular}
lindenmannm@3:     \caption{Dijkstra Example}\label{tab:dijEx}
lindenmannm@3: \end{table}
lindenmannm@3: Komplexität:
lindenmannm@3: \[O(n\cdot(T_{insert}+T_{Empty}+T_{DeleteMin})+m\cdot T_{DecreaseKey}+m+n)\]
lindenmannm@3: Implementierung mit Fibonaci-Heaps:\\
lindenmannm@3: $T_{Insert}:O(1)$\\
lindenmannm@3: $T_{DeleteMin}:O(\log n)$ (amortisiert)\\
lindenmannm@3: $T_{DecreaseKey}:O(1)$ (amortisiert)
lindenmannm@3: \[O(n\log n+m)\]
lindenmannm@3: \underline{Bellman-Ford}
lindenmannm@3: \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
lindenmannm@3: Belman-Ford, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
lindenmannm@3: basicstyle=\footnotesize]{./code/BelmanFord.code}
lindenmannm@3: \underline{Azyklische Netzwerke}
lindenmannm@3: \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus für
lindenmannm@3: Azyklische Netzwerke, captionpos=b, numbers=left, numberstyle=\tiny,
lindenmannm@3: numbersep=5pt, basicstyle=\footnotesize]{./code/AzyklischeNetzwerke.code}
lindenmannm@3: \subsection{Spannbäume minimalen Gewichts}
lindenmannm@3: Ungerichteter Graph $G=(V,E)$, Kostenfunktion $c:E\rightarrow R$.\\Sei
lindenmannm@3: $T\subseteq E$ ein Baum (zusammenhängender azyklischer Teilgraph) Kosten von T:
lindenmannm@3: $c(T)=\sum_{(u,v)\in T}c(u,v)$.\\Ein minimaler Spannbaum ist ein Baum
lindenmannm@3: $T\subseteq E$, der alle Knoten in $V$ verbindet minimale Kosten hat.
lindenmannm@3: \subsubsection{Das Wachsen von min. Spannbäumen}
lindenmannm@3: \textbf{Invariante:} Verwalte Menge $A\subseteq E$, die Teilmenge eines
lindenmannm@3: minimalen Spannbaums ist.\\
lindenmannm@3: \textbf{Definition:} Eine Kante $(u,v)\in E\backslash A$ ist sicher für $A$, wenn
lindenmannm@3: $A\cup {(u,v)}$ Teilmenge eines minimalen Spannbaums ist.
lindenmannm@3: \lstinputlisting[language=Java,label=lst:TTlookup,caption=Greedy Algorithmus für
lindenmannm@3: Spannbäume, captionpos=b, numbers=left, numberstyle=\tiny,
lindenmannm@3: numbersep=5pt, basicstyle=\footnotesize]{./code/spannbaeumeGreedy.code}
lindenmannm@3: \subsubsection{Schnitte}
lindenmannm@3: Ein Schnitt $(S,V\backslash S)$ ist eine Partition von $V$. Eine Kante $(u,v)$
lindenmannm@3: schneidet $(S,V\backslash S)$, wenn ein Endpunkt in $S$ und der andere in
lindenmannm@3: $V\backslash S$ liegt.\\Ein Schnitt "`respektiert $A$"', wenn keine Kante aus
lindenmannm@3: $A$ den Schnitt schneidet.\\Eine Kante heißt minimal bzgl. eines Schnitts, wenn
lindenmannm@3: sie den Schnitt schneidet und unter allen solchen Kanten minimale Kosten hat.
lindenmannm@3: \subsubsection{Sichere Kanten}
lindenmannm@3: \textbf{Satz:} Sei $A$ Teilmenge eines minimalen Spannbaums $T$ und
lindenmannm@3: $(S,V\backslash S)$ ein Schnitt, der $A$ respektiert. Ist $(u,v)$ eine minimale
lindenmannm@3: Kante bzgl. $(S,V\S)$, dann ist $(u,v)$ sicher für $A$.\\
lindenmannm@3: \textbf{Beweis}: \begin{itemize}
lindenmannm@3:   \item[1. Fall] $(u,v)\in T$ : ok
lindenmannm@3:   \item[2. Fall] $(u,v)\not\in T$ : Wir konstruieren minimalen Spannbaum $T'$
lindenmannm@3:   mit $(u,v)\in T'$ und $A\subseteq T'$.
lindenmannm@3: \end{itemize}
lindenmannm@3: \subsubsection{Der Graph $G_A$}
lindenmannm@3: \[G_A=(V,A)\]
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item ist ein \underline{Wald}, d.h. eine Menge von Bäumen
lindenmannm@3:   \item anfangs, wenn $A=\emptyset$, ist jeder Baum ein einzelner Knoten
lindenmannm@3:   \item eine sichere Kante verbindet verschiedene Bäume
lindenmannm@3: \end{itemize}
lindenmannm@3: \textbf{Korollar:} Sei $B$ ein Baum in $G_A=(V,A)$. Ist $(u,v)$ eine Kante
lindenmannm@3: minimaler Kosten, die $B$ und einen anderen Baum in $G_A$ verbindet, dann ist
lindenmannm@3: $(u,v)$ sicher für A.
lindenmannm@3: \subsubsection{Algorithmus von Kruskal}
lindenmannm@3: Wähle stets eine Kante minimaler Kosten, die zwei Bäume $B_1$ und $B_2$ in $G_A$
lindenmannm@3: verbindet.
lindenmannm@3: \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
lindenmannm@3: Kruskal, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
lindenmannm@3: basicstyle=\footnotesize]{./code/spannbaeumeKruskal.code}
lindenmannm@3: Laufzeit: $O(m\alpha(n)+m+m\log n)$
lindenmannm@3: \subsubsection{Algorithmus von Prim}
lindenmannm@3: $A$ ist immer ein einziger Baum. Starte mit einem beliebigen Wurzelknoten $w$.
lindenmannm@3: Füge in jedem Schritt eine minimale Kante hinzu, die einen Knoten in $A$ mit
lindenmannm@3: einem Knoten in $V\backslash A$ verbindet.
lindenmannm@3: \textbf{Implementierung}\\$Q$: Prioritätenwarteschlange, die alle Knoten $v\in
lindenmannm@3: V\backslash A$ enthält.\\Schlüssel von $v$: minimale Kosten einer Kante, die $v$
lindenmannm@3: mit einem Knoten aus $A$ verbindet.\\Für einen Knoten $v$ ist $p[v]$ der
lindenmannm@3: Elter-Knoten von $v$ in dem Baum.\[A={(v,p[v]):v\in V-{w}-Q}\]
lindenmannm@3: \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
lindenmannm@3: Prim, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
lindenmannm@3: basicstyle=\footnotesize]{./code/spannbaeumePrim.code}
lindenmannm@3: Laufzeit: $O(n\log n+m)$
lindenmannm@3: 
lindenmannm@3: \newpage
lindenmannm@3: \section{Bin Packing}
lindenmannm@3: \textbf{Problembeschreibung:}\\
lindenmannm@3: 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.
lindenmannm@3: \subsection{Online Verfahren}
lindenmannm@3: Jedes (ankommende) Objekt muss verpackt sein, bevor das nächste
lindenmannm@3: Objekt betrachtet wird. Ein Objekt verbleibt in derjenigen Kiste,
lindenmannm@3: in die es zuerst gepackt wird.\\ Kein Online Bin Packing Verfahren
lindenmannm@3: kann stets eine optimale Lösung finden!\\ \textbf{Satz 1}: Es gibt
lindenmannm@3: Eingaben, die jeden Online Bin Packing Algorithmus zwingen,
lindenmannm@3: wenigstens $\frac{4}{3} OPT$ Bins zu verwenden, wobei $OPT$ die
lindenmannm@3: minimal mögliche Binzahl ist.\\ \textbf{Beweis} Annahme: Online Bin
lindenmannm@3: Packing Algorithmus benötigt stets weniger als $\frac{4}{3}OPT$
lindenmannm@3: Bins.\\ Es wird eine Eingabe mit $2m$ Objekten angenommen. Die
lindenmannm@3: ersten $m$ sind um $\epsilon$ kleiner als $\frac{1}{2}$, die
lindenmannm@3: zweiten $m$ um $\epsilon$ größer. Die optimale Lösung sind $m$
lindenmannm@3: Kisten, da immer ein großes mit einem kleinen Paket kombiniert
lindenmannm@3: werden kann. Nun teilt man die Analyse in zwei Zeitpunkte: nach $m$
lindenmannm@3: Objekten und nach $2m$ Objekten. Laut Annahme gilt nach nach $m$
lindenmannm@3: Objekten, dass die Anzahl der Bins $b$ nur maximal $\frac{4}{3}
lindenmannm@3: OPT$ groß sein darf. Mit $OPT=\frac{m}{2}$ gilt somit:
lindenmannm@3: $b=\frac{4}{3}\cdot\frac{m}{2}=\frac{2}{3}m$. Sei $b=b_1+b_2\mid
lindenmannm@3: b_1=\#$Bins mit einem Objekt, $b_2=\#$Bins mit zwei Objekten, so
lindenmannm@3: folgt $b_1+2b_2=m\implies b_1=m-2b_2\implies b=b_1+b_2=m-b_2$. Nach
lindenmannm@3: $2m$ Objekten ist $OPT=m$, wie zuvor beschrieben. $b_1$ Bins können
lindenmannm@3: zu diesem Zeitpunkt mit Objekten des zweiten Bereichs gefüllt
lindenmannm@3: werden, für die verbleibenden muss man neue Bins öffnen. Die Anzahl
lindenmannm@3: der neu zu öffnenden beträgt damit genau $b_2\implies \#$Bins $\geq
lindenmannm@3: b+m-b_1=m+b_2$. Die Annahme besagt $m+b_2\leq\#$Bins $<\frac{4}{3}m
lindenmannm@3: \wedge b_2<\frac{m}{3}$. Dies ist nur möglich, wenn
lindenmannm@3: $b=m-b_2>\frac{2}{3}m$ - Dies führt zu einem
lindenmannm@3: \underline{Widerspruch}, da $b$ zum Zeitpunkt 1, nach $m$ Objekten
lindenmannm@3: $<\frac{2}{3}m$ sein muss.
lindenmannm@3: 
lindenmannm@3: \subsubsection{Next Fit (NF)}
lindenmannm@3: Verpacke das nächste Objekt in dieselbe Kiste wie das
lindenmannm@3: vorherige, wenn es dort noch hineinpasst, sonst öffne eine neue
lindenmannm@3: Kiste und verpacke es dort.\\ \textbf{Satz 2}: (a) Für alle
lindenmannm@3: Inputfolgen $I$ gilt: $NF(I)\leq2OPT(I)$. (b) Es gibt
lindenmannm@3: Inputfolgen I mit $NF(I)\geq2OPT(I)-2$.\\ \textbf{Beweis}\\ (a)
lindenmannm@3: Betrachte zwei beliebige aufeinanderfolgende Kisten $B_{2k-1},
lindenmannm@3: B_{2k}$. Man weiß, dass die beinhalteten Objekte eine
lindenmannm@3: Summengröße $>1$ haben, sonst wären selbige in einer Kiste.
lindenmannm@3: Daraus folgt, man kann nicht mehr als die doppelte Anzahl an
lindenmannm@3: Kisten als beim Optimum erreichen!\\ (b) Inputfolge: $0.5,
lindenmannm@3: \frac{2}{n}, 0.5, \frac{2}{n}, 0.5, \frac{2}{n}, \ldots 0.5,
lindenmannm@3: \frac{2}{n}$.\\Next-Fit liefert nun immer Bins gefüllt mit $0.5
lindenmannm@3: + \frac{2}{n}$. Darausfolgt $NF(I)=\frac{n}{2}$ und
lindenmannm@3: $OPT=\frac{n}{4}+1$ (weil $\frac{n}{2}$ mal 0.5er Objekte in
lindenmannm@3: $=\frac{n}{4}$ Kisten passen und $\frac{n}{2}$ $\frac{2}{n}$er
lindenmannm@3: Objekte in eine Kiste passen)\\ Laufzeit für Inputfolgen der
lindenmannm@3: Länge $n$: NF $O(n)$
lindenmannm@3: \subsubsection{First-Fit (FF)}
lindenmannm@3: Packe nächstes Objekt in die erste Kiste, in die es noch
lindenmannm@3: hineinpasst, wenn es eine solche Kiste gibt, sonst in eine neue
lindenmannm@3: Kiste.\\ \textbf{Beobachtung}: Zu jedem Zeitpunkt kann es
lindenmannm@3: höchstens eine Kiste geben, die weniger als halb voll ist.
lindenmannm@3: ($\implies FF(I) \leq 2OPT(I)$)\\ \textbf{Satz 3}: (a) Für alle
lindenmannm@3: Inputfolgen $I$ gilt $FF(I)\leq \lceil\frac{17}{10}
lindenmannm@3: OPT(I)\rceil$. (b) Es gibt Inputfolgen $I$ mit
lindenmannm@3: $FF(I)\geq\frac{17}{10}(OPT(I)-1)$. (b') Es gibt Inputfolgen
lindenmannm@3: $I$ mit $FF(I)=\frac{10}{6}OPT(I)$.\\ \textbf{Beweis}\\ (b')
lindenmannm@3: Inputfolge der Länge $3\cdot6m$. Dabei je $6m$ Objekte der
lindenmannm@3: Größen $\frac{1}{7}+\epsilon, \frac{1}{3}+\epsilon,
lindenmannm@3: \frac{1}{2}+\epsilon$, welche in gegebener Reihenfolge in
lindenmannm@3: Gruppen eingegeben werden. FF liefert hierbei $m$ Kisten
lindenmannm@3: gefüllt mit den Objekten der Größe $\frac{1}{7}+\epsilon$
lindenmannm@3: (jeweils 6 pro Kiste) gefolgt von $\frac{6m}{2}=3m$ Kisten
lindenmannm@3: gefüllt mit Objekten der Größe $\frac{1}{3}+\epsilon$ (jeweils
lindenmannm@3: 2 pro Kiste) und schlussendlich $6m$ Kisten mit je einem Objekt
lindenmannm@3: der Größe $\frac{1}{2}+\epsilon$. Das macht in der Summe $10m$
lindenmannm@3: Kisten. Die optimale Lösung packt je ein Objekt jeder Größe in
lindenmannm@3: eine Kiste und benötigt somit nur $6m$ Kisten.\\ Laufzeit für
lindenmannm@3: Inputfolgen der Länge $n$: FF $O(n^2) \rightarrow O(n \log n)$
lindenmannm@3: \subsubsection{Best-Fit (BF)}
lindenmannm@3: Verpacke das nächste Objekt in diejenige Kiste, in die es am
lindenmannm@3: besten passt (d.h. den geringsten Platz ungenutzt lässt).
lindenmannm@3: Verhalten von BF ähnlich zu FF. Laufzeit für Inputfolgen der
lindenmannm@3: Länge $n$: BF $O(n^2) \rightarrow O(n \log n)$
lindenmannm@3: \subsection{Offline Verfahren}
lindenmannm@3: \underline{NP-schwieriges Problem! Entscheidungsproblem ist NP-vollständig!}\\
lindenmannm@3: Zunächst wird die Anzahl $n$ und alle $n$ Objekte vorgegeben. Dann
lindenmannm@3: beginnt die Verpackung.\\ $n$ und $s_1, ..., s_n$ sind gegeben,
lindenmannm@3: bevor die Verpackung beginnt!\\ $\rightarrow$ \underline{Optimale
lindenmannm@3: Verpackung} kann durch erschöpfende Suche bestimmt werden. ABER:
lindenmannm@3: Benötigt exponentielle Zeit! Daher Approximimationsalgorithmen, die
lindenmannm@3: schneller sind aber dafür unter Umständen nicht optimal!\\
lindenmannm@3: Idee für Offline Approximationsalgorithmen: Sortiere die Objekte
lindenmannm@3: zunächst nach abnhemender Größe und verpacke größere Objekte zuerst!
lindenmannm@3: \subsubsection{First Fit Decreasing (FFD oder FFNI)}
lindenmannm@3: \textbf{Lemma 1}: Sei $I$ eine Folge von $n$ Objekten mit
lindenmannm@3: Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann
lindenmannm@3: haben alle von FFD in den Bins
lindenmannm@3: $B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackten Objekte eine
lindenmannm@3: Größe von höchstens $\frac{1}{3}$.
lindenmannm@3: \\ \textbf{Beweis}:
lindenmannm@3: %TODO:Elsässer hat das in seiner VL gemacht - aber hässlich lang
lindenmannm@3: \textbf{Lemma 2}: Sei $I$ eine Folge von $n$ Objekten mit
lindenmannm@3: Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann
lindenmannm@3: ist die Anzahl der Objekte, die FFD in die Kisten
lindenmannm@3: $B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackt, höchstens
lindenmannm@3: $m-1$.\\ \textbf{Beweis}: Annahme: Es gibt mehr als $m-1$
lindenmannm@3: Objekte. $x_1,\ldots,x_m$ in $I$, die FFD in extra Kisten
lindenmannm@3: verpacken. Dies führt zu einem Widerspruch.
lindenmannm@3: %TODO:Warum?
lindenmannm@3: \textbf{Satz}: Für alle Inputfolgen I
lindenmannm@3: gilt $FFD(I)\leq(4 OPT(I)+\frac{1}{3})$.\\ \textbf{Satz}:
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item[1.] Für alle Inputfolgen $I$ gilt: $FFD(I)\leq \frac{11}{9} OPT(I)+4$
lindenmannm@3:   \item[2.] Es gibt Inputfolgen $I$ mit: $FFD(I)=\frac{11}{9}OPT(I)$.
lindenmannm@3: \end{itemize}
lindenmannm@3: \textbf{Beweis}: %TODO
lindenmannm@3: \subsubsection{Best Fit Decreasing (BFD)}
lindenmannm@3: %TODO Nicht im Script???
lindenmannm@3: 
lindenmannm@3: \newpage
lindenmannm@3: \section{Dynamische Programmierung}
lindenmannm@3: \textbf{Idee:} Speichern von zwischen Ergebnissen, welche sonst mehrfach
lindenmannm@3: berechnet werden müssten.\\
lindenmannm@3: \textbf{Vorgehen:}
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item Rekursive Beschreibung des Problems P
lindenmannm@3:   \item Bestimmung einer Menge T, die alle Teilprobleme von P enthält, auf die
lindenmannm@3:   bei der Lösung von P zugegriffen wird.
lindenmannm@3:   \item Bestimmung einer Reihenfolge $T_0,\ldots T_k$ der Probleme in T, so dass
lindenmannm@3:   bei der Lösung von $T_i$ nur auf Probleme $T_j$ mit $j<i$ zurückgegriffen
lindenmannm@3:   wird.
lindenmannm@3:   \item Sukzessive Berechnung und Speicherung von Lösungen für $T_0,\ldots T_k$.
lindenmannm@3: \end{itemize}
lindenmannm@3: Wird im Script anhand der Fibonacci Zahlen demonstriert aber ist trivial \ldots
lindenmannm@3: \subsection{Matrixkettenprodukt (TODO)}
lindenmannm@3: %TODO
lindenmannm@3: \subsection{Optimale Suchbäume (TODO)}
lindenmannm@3: %TODO
lindenmannm@3: \subsection{Editierdistanz}
lindenmannm@3: Berechne für zwei gegebene Zeichenfolgen $A$ und $B$ möglichst effizient die
lindenmannm@3: Editier-Distanz $D(A,B)$ und eine minimale Folge von Editieroperationen, die
lindenmannm@3: $A$ in $B$ überführt.\\
lindenmannm@3: \textbf{Editieroperationen:}
lindenmannm@3: \begin{itemize}
lindenmannm@3:   \item Ersetzen eines Zeichens von $A$ durch ein Zeichen von $B$
lindenmannm@3:   \item Löschen eines Zeichens von $A$
lindenmannm@3:   \item Einfügen eines Zeichens von $B$
lindenmannm@3: \end{itemize}
lindenmannm@3: \textbf{Einheitskostenmodell:}
lindenmannm@3: \[c(a,b)=\begin{cases}1 & \text{falls } a\neq b\\0 & \text{falls } a=b\end{cases}\]
lindenmannm@3: $a=\epsilon, b=\epsilon$ möglich Dreiecksungleichung soll für $c$ im
lindenmannm@3: allgemeinen gelten:
lindenmannm@3: \[c(a,c)\leq c(a,b)+c(b,c)\]
lindenmannm@3: $\rightarrow$ ein Buchstabe wird höchstens einmal
lindenmannm@3: verändert.\\
lindenmannm@3: Rekursionsgleichung, falls $m,n\geq 1$ 
lindenmannm@3: \[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\}\]
lindenmannm@3: Anfangsbedingung:\\
lindenmannm@3: \[D_{0,0}=D(\epsilon,\epsilon)=0\]
lindenmannm@3: \[D_{0,j}=D(\epsilon,B_j)=j\]
lindenmannm@3: \[D_{i,0}=D(A_i,\epsilon)=i\]
lindenmannm@3: \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus zur
lindenmannm@3: Editierdistanz, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
lindenmannm@3: basicstyle=\footnotesize]{./code/editierdistanz.code}
lindenmannm@3: \textbf{Spurgraph:}\\
lindenmannm@3: Übersicht über alle möglichen Spuren zur Transformation von $A$ in $B$,
lindenmannm@3: gerichtete Kanten von Knoten $(i,j)$ zu $(i+1,j)$, $(i,j+1)$ und $(i+1,j+1)$.
lindenmannm@3: Gewichtung der Kanten entspricht den Editierkosten. Kosten nehmen entlang eines
lindenmannm@3: optimalen Weges monoton zu. Jeder Weg mit monotin wachsenden Kosten von der
lindenmannm@3: linken oberen Ecke zur rechten unteren Ecke entspricht einer optimalen Spur. Zur
lindenmannm@3: Berechnung der Spur der minimalen Editieroperationen (es gibt mehrere
lindenmannm@3: Lösungen), kann folgender Algorithmus verwendet werden:
lindenmannm@3: \lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus zum Spurgraphen, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\footnotesize]{./code/spurgraph.code}
lindenmannm@3: 
lindenmannm@3: \section{Suche in Texten}
lindenmannm@3: \underline{Gegeben:} Text T $t_1t_2t_3\ldots t_n\in\Sigma^n$ und
lindenmannm@3: rin Muster P $p_1p_2p_3\ldots p_m\in\Sigma^m$\\
lindenmannm@3: \underline{Gesucht:} Ein oder alle Vorkommen des Musters im Text, d.h.
lindenmannm@3: Verschiebungen $i$ mit $0\leq i\leq n-m$.\\
lindenmannm@3: \textbf{Naives Verfahren:} iteriere über den Text und suche das Muster. Aufwand:
lindenmannm@3: $m\cdot(n-m+1)$ Vergleiche $\implies \Omega(n\cdot m)$
lindenmannm@3: \textbf{Verfahren nach Knuth-Morris-Pratt (KMP):} 
lindenmannm@3: Präffix=Suffix Verfahren. Daraus resultiert eine Shiftmöglichkeit des Musters
lindenmannm@3: über den Text. Der Shift geschieht um $next[j]$=Länge des längsten Präfix von
lindenmannm@3: $P$, das echtes Suffix von $P_{1\ldots j}$ ist, wobei $j=$Position des letzten
lindenmannm@3: Vergleiches.\\
lindenmannm@3: \underline{Erstellung des $next[j]$ arrays über P.}\\
lindenmannm@3: $P=0101101011$
lindenmannm@3: \begin{table}[H]
lindenmannm@3: 	\centering
lindenmannm@3: 	\begin{tabular}{c|c|c|c|c|c|c|c|c|c}
lindenmannm@3: 		1&2&3&4&5&6&7&8&9&10\\\hline
lindenmannm@3: 		0&1&0&1&1&0&1&0&1&1\\\hline
lindenmannm@3: 		 & &0& & & & & & & \\
lindenmannm@3: 		 & &0&1& & & & & & \\
lindenmannm@3: 		 & & & & &0& & & & \\
lindenmannm@3: 		 & & & & &0&1& & & \\
lindenmannm@3: 		 & & & & &0&1&0& & \\
lindenmannm@3: 		 & & & & &0&1&0&1& \\
lindenmannm@3: 		 & & & & &0&1&0&1&1\\
lindenmannm@3: 	\end{tabular}
lindenmannm@3: 	\caption{next[j] Beispiel}
lindenmannm@3: 	\label{tab:nextJ}
lindenmannm@3: \end{table}
lindenmannm@3: $\rightarrow next[j]=[0,0,1,2,0,1,2,3,4,5]$\\
lindenmannm@3: \underline{Algorithmus:}
lindenmannm@3: \lstinputlisting[language=Java,label=lst:TTlookup,caption=KMP Algorithmus,
lindenmannm@3: captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\footnotesize]{./code/kmp.code}
lindenmannm@3: \underline{Analyse:}
lindenmannm@3: inkrement $j$ = inkrement $i$ und dekrement $j$ = inkrement $j$!
lindenmannm@3: $\rightarrow O(n)$ hinzu kommt noch die Berechnung des next-arrays mit $O(m)$.\\
lindenmannm@3: KMP kann also mit $O(n+m)$ berechnet werden. (i.e. Untere Schranke
lindenmannm@3: $\Omega(m+n/m)$)
lindenmannm@3: 
lindenmannm@3: \newpage
lindenmannm@3: \begin{appendix}
lindenmannm@3: \section{Landau-Symbole}
lindenmannm@3: \begin{figure}[H]
lindenmannm@3: \centering
lindenmannm@3: \includegraphics[scale=0.45]{img/landau_sym}
lindenmannm@3: \caption{Definition der Landau Symbole}
lindenmannm@3: \label{fig:landau_sym}
lindenmannm@3: \end{figure}
lindenmannm@3: \end{appendix}
lindenmannm@3: \end{document}