1.1 Binary file AT_Exzerpt.dvi has changed
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/AT_Exzerpt.tex Tue Feb 22 19:02:39 2011 +0100
2.3 @@ -0,0 +1,624 @@
2.4 +\documentclass[a4paper,11pt,twoside]{article}
2.5 +
2.6 +\usepackage[ngerman]{babel} \usepackage[T1]{fontenc}
2.7 +\usepackage[latin1]{inputenc}
2.8 +\usepackage[colorlinks=true,linkcolor=black]{hyperref}
2.9 +
2.10 +\usepackage{vaucanson-g}
2.11 +\usepackage{hyperref}
2.12 +\usepackage{hypcap}
2.13 +\usepackage{fancyhdr}
2.14 +\usepackage{graphicx}
2.15 +\usepackage{lastpage}
2.16 +\usepackage[cm]{fullpage}
2.17 +\usepackage{amsthm, amsmath, amsfonts}
2.18 +\usepackage{float}
2.19 +\usepackage{paralist}
2.20 +\usepackage{listings}
2.21 +\usepackage{color}
2.22 +\usepackage{bookmark}
2.23 +
2.24 +\bibliographystyle{alphadin}
2.25 +
2.26 +\title{\underline{Exzerpt Algorithmentheorie WS10/11}}
2.27 +\author{Markus Lindenmann}
2.28 +\date{\today{} }
2.29 +
2.30 +\begin{document}
2.31 +\maketitle
2.32 +
2.33 +\tableofcontents \newpage
2.34 +
2.35 +\section{Einleitung}\label{sec:intro}
2.36 +Dozent: Matthias Westermann\\
2.37 +Website: \url{http://lak.informatik.uni-freiburg.de}\\
2.38 +Klausur: 09.03.2011\\
2.39 +Hilfsmittel: Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt
2.40 +\subsection{Themen:}
2.41 +\begin{itemize}
2.42 + \item[$\bullet$] Divide and Conquer
2.43 + \item[$\bullet$] Greedy Prinzip
2.44 + \item[$\bullet$] Dynamische Programmierung
2.45 + \item[$\bullet$] Randomisierung
2.46 + \item[$\bullet$] Amortisierte Analyse
2.47 +\end{itemize}
2.48 +\subsection{Problem-/Anwendungsbereiche:}
2.49 +\begin{itemize}
2.50 + \item[$\bullet$] Geometrische Algorithmen
2.51 + \item[$\bullet$] Algebraische Algorithmen
2.52 + \item[$\bullet$] Graphenalgorithmen
2.53 + \item[$\bullet$] Datenstrukturen
2.54 + \item[$\bullet$] Internet-Algorithmen
2.55 + \item[$\bullet$] Optimierungs-Verfahren
2.56 + \item[$\bullet$] Zeichenkettenverarbeitung
2.57 +\end{itemize}
2.58 +\subsection{Literatur:}
2.59 +\bibliography{literatur}
2.60 +\nocite{*}
2.61 +
2.62 +\newpage
2.63 +\section{Divide and Conquer}\label{sec:div&conq}
2.64 +\begin{itemize}
2.65 + \item[$\bullet$] Quicksort
2.66 + \item[$\bullet$] Formulierung und Analyse des Prinzips
2.67 + \item[$\bullet$] Geometrisches Devide and Conquer
2.68 + \begin{itemize}
2.69 + \item[-] Closest-Pair
2.70 + \item[-] Segmentschnitt
2.71 + \end{itemize}
2.72 +\end{itemize}
2.73 +
2.74 +\subsection{Formulierung des Divide and Conquer Prinzips}
2.75 +D\&C Verfahren zur Lösung eines Problems der Größe $n$
2.76 +\begin{itemize}
2.77 + \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
2.78 + \item[2.] Conquer\\Löse die $k$ Teilprobleme auf dieselbe Art (rekursiv)
2.79 + \item[3.] Merge\\Füge die berechneten Teillösungen zu einer Gesamtlösung zusammen
2.80 +\end{itemize}
2.81 +
2.82 +\subsection{Quicksort}\label{ch:qs}
2.83 +Wähle beliebiges Pivot Element $v$ (meist das letzte Element in der
2.84 +Input-Folge!) und sortiere alle Elemente aus der Menge, die größer sind als $v$
2.85 +rechts von $v$ ein, die anderen links. Verfahre im selben Muster mit den neuen
2.86 +Teilmengen links und rechts des Pivot Elements. Wenn die zu sortierende Folge
2.87 +$F$ nur ein Element beinhaltet, gebe $F$ zurück.
2.88 +\subsubsection{Algorithmus}
2.89 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus Quicksort,
2.90 +captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
2.91 +basicstyle=\footnotesize]{./code/quicksort.code}
2.92 +
2.93 +\subsubsection{Analyse}
2.94 +$T(n)$ - maximale Anzahl von Schritten, um ein Problem der Größe $n$ zu lösen.
2.95 +\[T(n)=\begin{cases}n\neq c&a \\ n>c&T(n_1+\ldots+T(n_k)+\text{Divide- und Mergeaufwand}\end{cases}\]
2.96 +Best Case: $k=2, n_1=n_2=\frac{n}{2}$\\
2.97 +Divide- und Mergeaufwand: $DM(n)$\\
2.98 +$T(1)=a$\\
2.99 +$T(n)=2T(\frac{n}{2})+DM(n)$
2.100 +
2.101 +\subsection{Nächste Paare}
2.102 +Eingabe: $n$ Punkte in Ebene\\
2.103 +Ausgabe: Punkt-Paar $q,r$ mit geringstem Abstand\\
2.104 +Abstand: $d(q,r)$ bechreibt Abstand zwischen Punkten $q$ und $r$
2.105 +\subsubsection{Algorithmus}
2.106 +\begin{itemize}
2.107 + \item[$\bullet$] sortiere Punktmenge nach x-Koordinate
2.108 + \item[$\bullet$] Teile Punktmenge in der Mitte L in die Mengen Q und R
2.109 + \item[$\bullet$] Löse rekursiv auf Q und R
2.110 + \item[$\bullet$] Sortiere Punkte nach y-Koordinate
2.111 + \item[$\bullet$] Teste alle Paare, deren Abstand in der
2.112 + Sortierung kleiner als 16 ist (siehe unten)
2.113 + \item[$\bullet$] Füge zusammen
2.114 +\end{itemize}
2.115 +
2.116 +$\delta=$ Minimum der Teillösungen\\
2.117 +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.\\
2.118 +\textbf{Problem:} alle Punkte können innerhalb der $\delta$-Zone liegen\\
2.119 +\textbf{Lösung:}\begin{itemize}
2.120 +\item[$\bullet$] Sortiere Punkte in $\delta$ Zone nach $y$-Abstand
2.121 +\item[$\bullet$] Liegen in dieser Sortierung mehr als $c$ Punkte zwischen $q$ und $r$, dann kann $(q,r)$ nicht nächstes Paar sein
2.122 +\end{itemize}
2.123 +
2.124 +Dies kann für $c=15$ bewiesen werden (vgl. Abbildung \ref{cl_pair}):
2.125 +\begin{itemize}
2.126 + \item[$\bullet$] Seien min. 15 Punkte zwischen $q$ und $r$
2.127 + \item[$\bullet$] Dann sind mindestens 3 Reihen Quadrate zwischen $q,r$, weil in jedem Quadrat höchstens ein Punkt ist.
2.128 + \item[$\rightarrow$] Dann muss $d(q,r)$ mindestens $\frac{3}{2}\delta > \delta$ sein.
2.129 +\end{itemize}
2.130 +
2.131 +\begin{figure}[H]
2.132 +\centering
2.133 +\includegraphics[scale=0.5]{img/cl_pair}
2.134 +\caption{Nächste Paare: Prüf Distanz}
2.135 +\label{cl_pair}
2.136 +\end{figure}
2.137 +
2.138 +\subsubsection{Analyse}
2.139 +\[T(n)=\begin{cases}n\leq3&a \\ n>3&2T(\frac{n}{2})+an\end{cases}\]
2.140 +\[T(n)\leq an \log n \]
2.141 +
2.142 +\subsection{Segmentschnitt}
2.143 +Eingabe: Menge S bestehend aus vertikalen Segmenten und Endpunkten vn horizontalen Segmenten\\
2.144 +Ausgabe: Alle Schnittpunkte von vertikalen Segmenten mit horizontalen Segmenten, von denen mindesens ein Endpunkt in S ist
2.145 +
2.146 +\subsubsection{Algorithmus}
2.147 +\textbf{Divide \& Conquer:}\\Fallunterscheidung
2.148 +\begin{itemize}
2.149 + \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.
2.150 + \item[2.] else: S enthält keine Schnitte
2.151 +\end{itemize}
2.152 +
2.153 +\textbf{Merge}\\
2.154 +Bilde L(S), R(S) und V(S) (Definition am Beispiel $i=1,2$ berechnet: $S=S_1\cup S_2$):
2.155 +\begin{itemize}
2.156 + \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))$
2.157 + \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))$
2.158 + \item[$\bullet$] V(S): y-Intervalle der vertikalen Segmente in S\\$=V(S_1)\cup V(S_2)$
2.159 +\end{itemize}
2.160 +L,R sortiert nach steigender y-Koordinate\\
2.161 +V sortiert nach steigendem unteren Endpunkt\\
2.162 +\medskip
2.163 +
2.164 +\textbf{Basisfälle}\\
2.165 +S enthält nur ein Element s. Fallunterscheidung:
2.166 +\begin{itemize}
2.167 + \item[1.] $s=(x,y)$ ist ein linker Endpunkt:\\$L(S)=\{y\},\qquad R(S)=\emptyset,\qquad V(S)=\emptyset$
2.168 + \item[2.] $s=(x,y)$ ist ein rechter Endpunkt:\\$L(S)=\emptyset,\qquad R(S)=\{y\},\qquad V(S)=\emptyset$
2.169 + \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]\}$
2.170 +\end{itemize}
2.171 +
2.172 +\subsubsection{Analyse}
2.173 +Eingabe wird Anfangs sortiert und in Array gespeichert
2.174 +\[T(n)=2T(\frac{n}{2}+an+\text{Größe der Ausgabe}\]
2.175 +\[T(1)=O(1)\]
2.176 +\[O(n \log n + k \mid k=\#Schnittpunkte\]
2.177 +
2.178 +\subsection{Polynomprodukt und Fast Fourier-Transformation (TODO)}
2.179 +%TODO
2.180 +
2.181 +\newpage
2.182 +\section{Randomisierung}
2.183 +\begin{itemize}
2.184 + \item Klassen von randomisierten Algorithmen
2.185 + \begin{itemize}
2.186 + \item \textbf{Las Vegas}: \underline{immer} Korrekt, erwartete Laufzeit
2.187 + (randomisierter Qicksort)
2.188 + \item \textbf{Monte Carlo}: \underline{wahrscheinlich} (MC:mostly correct)
2.189 + Korrekt, garantierte Laufzeit (randomisierter Primzahltest)
2.190 + \end{itemize}
2.191 + \item Randomisierter Quicksort
2.192 + \item Randomisierter Primzahltest
2.193 + \item Kryptographie
2.194 +\end{itemize}
2.195 +\subsection{Randomisierter Quicksort}
2.196 + Refer to \ref{ch:qs} for basic description of the algorithm.\\
2.197 + Problem von Quicksort: bisher nimmt Quicksort immer das letzte Element in der
2.198 + Folge $\implies$ Worst-Case: sortierte Folge als Eingabe ($\Theta(n^2)$).
2.199 + Ziel: keine quadratische Laufzeit.\\
2.200 + Lösung: randomisierte Auswahl des Pivotelements an Stelle $i$. Anschließend
2.201 + tauschen von Position $i$ und $r$ (mit $r$=rechte Grenze des zu sortierenden
2.202 + Segments).
2.203 + \subsubsection{Analyse}
2.204 + \textbf{Analyse 1: erwartete Laufzeit}\\
2.205 + Mit Wahrscheinlichkeit $\frac{1}{n}$ wird das $i$-kleinste Element $S_i$
2.206 + gewählt wobei $n$ zu sortierenden Elemente vorhanden sind. Abhängig von der
2.207 + Wahl von $S_i$ ergeben sich Teilprobleme der Größe $i-1$ und $n-i$. Damit
2.208 + ergibt sich für die Laufzeit $T(n)$.
2.209 + \[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+\]
2.210 + \[\frac{1}{n}(T(n-1)+T(0))+\Theta(n))\mid
2.211 + \Theta(n)\text{ für partition}\]
2.212 + \[=\frac{1}{n}\sum_{k=1}^n(T(k-1)+T(n-k))+\Theta(n)\]
2.213 + \[\frac{2}{n}\sum_{k=1}^nT(k-1)+\Theta(n)\]
2.214 + \[=O(n \log n)\]
2.215 + \textbf{Analys 2: Erwartete Anzahl der Vergleiche}\\
2.216 + $x_{ij}=
2.217 + \begin{cases}
2.218 + 1&\text{falls }S_i\text{ mit }S_j\text{ verglichen wird}\\
2.219 + 0&\text{sonst}
2.220 + \end{cases}$
2.221 + \[E\left[\sum_{i=1}^n\sum_{j>1}x_{ij}\right]=\sum_{i=1}^n\sum_{j>1}E[x_{ij}]\]
2.222 + $p_{ij} =$ Wahrscheinlichkeit $S_i$ wird mit $S_j$ verglichen
2.223 + \[E[x_{ij}=1\cdot p_{ij}+0\cdot(1-p_{ij}=p_{ij}\]
2.224 +\subsection{Randomisierter Primzahltest (TODO)}
2.225 +%TODO schnelle exponentiation
2.226 +\subsection{RSA (TODO)}
2.227 +%TODO
2.228 +%erw. Euklid
2.229 +\subsection{Treaps (TODO)}
2.230 +%TODO haben wir nicht so im detail gemacht wie Elsässer!
2.231 +\subsection{Hashing (TODO)}
2.232 +%TODO
2.233 +
2.234 +\newpage
2.235 +\section{Amortisierte Analyse (TODO)}
2.236 +%TODO
2.237 +\subsection{Binomial Heaps (TODO)}
2.238 +%TODO
2.239 +\subsection{Fibonacci Heaps (TODO)}
2.240 +%TODO
2.241 +\subsection{Union Find (TODO)}
2.242 +%TODO
2.243 +
2.244 +\newpage
2.245 +\section{Greedy}
2.246 +Momentan beste Teillösung wählen. Die Summe dieser optimalen Teillösung ergibt
2.247 +die gesamt Lösung. Möglicher Zustand der Gesamtlösung:
2.248 +\begin{itemize}
2.249 + \item Wir erhalten die optimale Gesamtlösung.
2.250 + \item Wir erhalten eine Lösung, die zwar nicht immer optimal ist, aber vom
2.251 + Optimum stets nur wenig abweicht.
2.252 + \item Die berechnete Lösung kann beliebig schlecht werden.
2.253 +\end{itemize}
2.254 +\underline{Beispiele:}
2.255 +\begin{itemize}
2.256 + \item Münzwechselproblem\\\textbf{Ziel:} Bezahlung eines Betrages in möglichst
2.257 + wenig Münzen und Banknoten.\\\textbf{Lösung (Greedy):} Wähle die maximale
2.258 + Anzahl von Banknoten und Münzen mit jeweils größtmöglichem Wert, bis der
2.259 + gewünschte Betrag erreicht ist. (Dies führt nur für bestimmte Werte der
2.260 + Zahlungsmittel zur optimalen Gesamtlösung!)
2.261 + \item Handlungsreisenden-Problem (Traveling Sales Man Problem,
2.262 + TSP)\\\textbf{Ziel:} Finden der billigsten Rundreise, diealle Orte genau
2.263 + einmal besucht.\\\textbf{Lösung (Greedy):} Gehe immer den günstigsten Weg vom
2.264 + aktuellen Knoten zu einem noch nicht besuchten Knoten. Wenn alle besucht
2.265 + wurden, kehre zum Anfang zurück. (Mit Greedy keine optimale Gesamtlösung!)
2.266 + \item Aktivitäten Auswahlproblem\\\textbf{Ziel:} möglichst viele Anfragen
2.267 + erfüllen. (Muss nicht bedeuten, dass die Ressource optimal
2.268 + genutzt wird!)\\\textbf{Lösung (Greedy):} Nimm die Anfrage, die am frühesten
2.269 + fertig ist. (optimale Gesamtlösung!)\\\textbf{Analyse:} $\Theta(n)$
2.270 +\end{itemize}
2.271 +
2.272 +\subsection{Kürzeste (billigste) Wege}
2.273 +Pfad $P=$ Folge von Knoten.
2.274 +Kosten eines Pfades:\[c(P)=\sum_{i=0}^{P.length-1}c(v_i,v_{i+1}\]
2.275 +Entfernung von $v$ nach $w$ sind die Kosten des
2.276 +günstigsten Pfades:\[dist(v,w)=inf{c(P)\mid P\text{= Weg von v nach
2.277 +w}}\]
2.278 +Kosten eines unerreichbaren Knoten sind definiert als $\infty$. Kosten eines
2.279 +Pfades in einem negativen Zyklus: $-\infty$. Es können also nur Graphen ohne
2.280 +negative Zyklen sinnvoll betrachtet werden!
2.281 +\subsubsection{Single Source Shortest Paths}
2.282 +Kürzeste/Günstigste Pfade von einem Knoten $s$ zu allen anderen Knoten. Hierfür
2.283 +nutzt man die Dreiecksungleichung über $dist(u,v)\mid (u,v)\in E$ und $s\in V$:
2.284 +\[dist(s,v)\leq dist(s,u)+dist(u,v)\]
2.285 +\textbf{Greedy-Ansatz}
2.286 +\begin{itemize}
2.287 + \item Überschätze die dist-Funktion \[dist(s,v)=\begin{cases}0&\text{ falls }
2.288 + v=s\\\infty&\text{ falls }v\neq s\end{cases}\]
2.289 + \item Solange eine Kante $e=(u,v)$ existiert mit
2.290 + $dist(s,v)>dist(s,u)+c(u,v)$ setze $dist(s,v)=dist(s,u)+c(u,v)$
2.291 +\end{itemize}
2.292 +Durch die Überschätzung kann die Dreicksungleichung nur noch für Knoten $s$ und
2.293 +seine direkten Nachfolger verletzt werden!\\Alle folgenden Verfahren basieren
2.294 +auf diesem Prinzip!\\
2.295 +%Elsässer führt einige Lemmas ein und beweist sie - diese beziehen sich auf den
2.296 +% ersten optimimierten Algorithmus und diesen erachte ich in Relation zu
2.297 +% Dijkstra als irrelevant!
2.298 +\textbf{Effiziente Implementierungen}
2.299 +Diese sind im Allgemeinen nicht bekannt, jedoch für wichtige Spezialfälle.
2.300 +\begin{itemize}
2.301 + \item Nicht-negative Netzwerke: \underline{Dijkstra}
2.302 + \item Netzwerke ohne negative Zyklen: \underline{Bellman-Ford}
2.303 + \item Azyklische Netzwerke
2.304 +\end{itemize}
2.305 +\underline{Dijkstra}
2.306 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
2.307 +Dijkstra, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
2.308 +basicstyle=\footnotesize]{./code/dijkstra.code}
2.309 +Dijkstra Beispiel:
2.310 +\begin{figure}
2.311 + \centering
2.312 + \includegraphics[scale=0.6]{img/dijkstraExT}
2.313 + \caption{Tree for Dijkstra Example}
2.314 + \label{fig:dijExT}
2.315 +\end{figure}
2.316 +\begin{table}[ht]
2.317 + \centering
2.318 + \begin{tabular}{|c c c c c c c|c|}
2.319 + \hline
2.320 + \multicolumn{7}{|c|}{DIST[v]} & \\
2.321 + \hline
2.322 + s & a & b & c & d & e & f & U\\\hline\hline
2.323 + 0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & s,a,b,c,d,e,f\\
2.324 + 0* & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & a,b,c,d,e,f\\
2.325 + 0* & 6 & 7 & 5* & $\infty$ & $\infty$ & $\infty$ & a,b,d,e,f\\
2.326 + 0* & 6* & 7 & 5* & $\infty$ & $\infty$ & 14 & b,d,e,f\\
2.327 + 0* & 6* & 7* & 5* & 9 & 10 & 14 & d,e,f\\
2.328 + 0* & 6* & 7* & 5* & 9* & 10 & 11 & e,f\\
2.329 + 0* & 6* & 7* & 5* & 9* & 10* & 11 & f\\
2.330 + 0* & 6* & 7* & 5* & 9* & 10* & 11* & $\emptyset$\\\hline
2.331 + \end{tabular}
2.332 + \caption{Dijkstra Example}\label{tab:dijEx}
2.333 +\end{table}
2.334 +Komplexität:
2.335 +\[O(n\cdot(T_{insert}+T_{Empty}+T_{DeleteMin})+m\cdot T_{DecreaseKey}+m+n)\]
2.336 +Implementierung mit Fibonaci-Heaps:\\
2.337 +$T_{Insert}:O(1)$\\
2.338 +$T_{DeleteMin}:O(\log n)$ (amortisiert)\\
2.339 +$T_{DecreaseKey}:O(1)$ (amortisiert)
2.340 +\[O(n\log n+m)\]
2.341 +\underline{Bellman-Ford}
2.342 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
2.343 +Belman-Ford, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
2.344 +basicstyle=\footnotesize]{./code/BelmanFord.code}
2.345 +\underline{Azyklische Netzwerke}
2.346 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus für
2.347 +Azyklische Netzwerke, captionpos=b, numbers=left, numberstyle=\tiny,
2.348 +numbersep=5pt, basicstyle=\footnotesize]{./code/AzyklischeNetzwerke.code}
2.349 +\subsection{Spannbäume minimalen Gewichts}
2.350 +Ungerichteter Graph $G=(V,E)$, Kostenfunktion $c:E\rightarrow R$.\\Sei
2.351 +$T\subseteq E$ ein Baum (zusammenhängender azyklischer Teilgraph) Kosten von T:
2.352 +$c(T)=\sum_{(u,v)\in T}c(u,v)$.\\Ein minimaler Spannbaum ist ein Baum
2.353 +$T\subseteq E$, der alle Knoten in $V$ verbindet minimale Kosten hat.
2.354 +\subsubsection{Das Wachsen von min. Spannbäumen}
2.355 +\textbf{Invariante:} Verwalte Menge $A\subseteq E$, die Teilmenge eines
2.356 +minimalen Spannbaums ist.\\
2.357 +\textbf{Definition:} Eine Kante $(u,v)\in E\backslash A$ ist sicher für $A$, wenn
2.358 +$A\cup {(u,v)}$ Teilmenge eines minimalen Spannbaums ist.
2.359 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Greedy Algorithmus für
2.360 +Spannbäume, captionpos=b, numbers=left, numberstyle=\tiny,
2.361 +numbersep=5pt, basicstyle=\footnotesize]{./code/spannbaeumeGreedy.code}
2.362 +\subsubsection{Schnitte}
2.363 +Ein Schnitt $(S,V\backslash S)$ ist eine Partition von $V$. Eine Kante $(u,v)$
2.364 +schneidet $(S,V\backslash S)$, wenn ein Endpunkt in $S$ und der andere in
2.365 +$V\backslash S$ liegt.\\Ein Schnitt "`respektiert $A$"', wenn keine Kante aus
2.366 +$A$ den Schnitt schneidet.\\Eine Kante heißt minimal bzgl. eines Schnitts, wenn
2.367 +sie den Schnitt schneidet und unter allen solchen Kanten minimale Kosten hat.
2.368 +\subsubsection{Sichere Kanten}
2.369 +\textbf{Satz:} Sei $A$ Teilmenge eines minimalen Spannbaums $T$ und
2.370 +$(S,V\backslash S)$ ein Schnitt, der $A$ respektiert. Ist $(u,v)$ eine minimale
2.371 +Kante bzgl. $(S,V\S)$, dann ist $(u,v)$ sicher für $A$.\\
2.372 +\textbf{Beweis}: \begin{itemize}
2.373 + \item[1. Fall] $(u,v)\in T$ : ok
2.374 + \item[2. Fall] $(u,v)\not\in T$ : Wir konstruieren minimalen Spannbaum $T'$
2.375 + mit $(u,v)\in T'$ und $A\subseteq T'$.
2.376 +\end{itemize}
2.377 +\subsubsection{Der Graph $G_A$}
2.378 +\[G_A=(V,A)\]
2.379 +\begin{itemize}
2.380 + \item ist ein \underline{Wald}, d.h. eine Menge von Bäumen
2.381 + \item anfangs, wenn $A=\emptyset$, ist jeder Baum ein einzelner Knoten
2.382 + \item eine sichere Kante verbindet verschiedene Bäume
2.383 +\end{itemize}
2.384 +\textbf{Korollar:} Sei $B$ ein Baum in $G_A=(V,A)$. Ist $(u,v)$ eine Kante
2.385 +minimaler Kosten, die $B$ und einen anderen Baum in $G_A$ verbindet, dann ist
2.386 +$(u,v)$ sicher für A.
2.387 +\subsubsection{Algorithmus von Kruskal}
2.388 +Wähle stets eine Kante minimaler Kosten, die zwei Bäume $B_1$ und $B_2$ in $G_A$
2.389 +verbindet.
2.390 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
2.391 +Kruskal, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
2.392 +basicstyle=\footnotesize]{./code/spannbaeumeKruskal.code}
2.393 +Laufzeit: $O(m\alpha(n)+m+m\log n)$
2.394 +\subsubsection{Algorithmus von Prim}
2.395 +$A$ ist immer ein einziger Baum. Starte mit einem beliebigen Wurzelknoten $w$.
2.396 +Füge in jedem Schritt eine minimale Kante hinzu, die einen Knoten in $A$ mit
2.397 +einem Knoten in $V\backslash A$ verbindet.
2.398 +\textbf{Implementierung}\\$Q$: Prioritätenwarteschlange, die alle Knoten $v\in
2.399 +V\backslash A$ enthält.\\Schlüssel von $v$: minimale Kosten einer Kante, die $v$
2.400 +mit einem Knoten aus $A$ verbindet.\\Für einen Knoten $v$ ist $p[v]$ der
2.401 +Elter-Knoten von $v$ in dem Baum.\[A={(v,p[v]):v\in V-{w}-Q}\]
2.402 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
2.403 +Prim, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
2.404 +basicstyle=\footnotesize]{./code/spannbaeumePrim.code}
2.405 +Laufzeit: $O(n\log n+m)$
2.406 +
2.407 +\newpage
2.408 +\section{Bin Packing}
2.409 +\textbf{Problembeschreibung:}\\
2.410 +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.
2.411 +\subsection{Online Verfahren}
2.412 +Jedes (ankommende) Objekt muss verpackt sein, bevor das nächste
2.413 +Objekt betrachtet wird. Ein Objekt verbleibt in derjenigen Kiste,
2.414 +in die es zuerst gepackt wird.\\ Kein Online Bin Packing Verfahren
2.415 +kann stets eine optimale Lösung finden!\\ \textbf{Satz 1}: Es gibt
2.416 +Eingaben, die jeden Online Bin Packing Algorithmus zwingen,
2.417 +wenigstens $\frac{4}{3} OPT$ Bins zu verwenden, wobei $OPT$ die
2.418 +minimal mögliche Binzahl ist.\\ \textbf{Beweis} Annahme: Online Bin
2.419 +Packing Algorithmus benötigt stets weniger als $\frac{4}{3}OPT$
2.420 +Bins.\\ Es wird eine Eingabe mit $2m$ Objekten angenommen. Die
2.421 +ersten $m$ sind um $\epsilon$ kleiner als $\frac{1}{2}$, die
2.422 +zweiten $m$ um $\epsilon$ größer. Die optimale Lösung sind $m$
2.423 +Kisten, da immer ein großes mit einem kleinen Paket kombiniert
2.424 +werden kann. Nun teilt man die Analyse in zwei Zeitpunkte: nach $m$
2.425 +Objekten und nach $2m$ Objekten. Laut Annahme gilt nach nach $m$
2.426 +Objekten, dass die Anzahl der Bins $b$ nur maximal $\frac{4}{3}
2.427 +OPT$ groß sein darf. Mit $OPT=\frac{m}{2}$ gilt somit:
2.428 +$b=\frac{4}{3}\cdot\frac{m}{2}=\frac{2}{3}m$. Sei $b=b_1+b_2\mid
2.429 +b_1=\#$Bins mit einem Objekt, $b_2=\#$Bins mit zwei Objekten, so
2.430 +folgt $b_1+2b_2=m\implies b_1=m-2b_2\implies b=b_1+b_2=m-b_2$. Nach
2.431 +$2m$ Objekten ist $OPT=m$, wie zuvor beschrieben. $b_1$ Bins können
2.432 +zu diesem Zeitpunkt mit Objekten des zweiten Bereichs gefüllt
2.433 +werden, für die verbleibenden muss man neue Bins öffnen. Die Anzahl
2.434 +der neu zu öffnenden beträgt damit genau $b_2\implies \#$Bins $\geq
2.435 +b+m-b_1=m+b_2$. Die Annahme besagt $m+b_2\leq\#$Bins $<\frac{4}{3}m
2.436 +\wedge b_2<\frac{m}{3}$. Dies ist nur möglich, wenn
2.437 +$b=m-b_2>\frac{2}{3}m$ - Dies führt zu einem
2.438 +\underline{Widerspruch}, da $b$ zum Zeitpunkt 1, nach $m$ Objekten
2.439 +$<\frac{2}{3}m$ sein muss.
2.440 +
2.441 +\subsubsection{Next Fit (NF)}
2.442 +Verpacke das nächste Objekt in dieselbe Kiste wie das
2.443 +vorherige, wenn es dort noch hineinpasst, sonst öffne eine neue
2.444 +Kiste und verpacke es dort.\\ \textbf{Satz 2}: (a) Für alle
2.445 +Inputfolgen $I$ gilt: $NF(I)\leq2OPT(I)$. (b) Es gibt
2.446 +Inputfolgen I mit $NF(I)\geq2OPT(I)-2$.\\ \textbf{Beweis}\\ (a)
2.447 +Betrachte zwei beliebige aufeinanderfolgende Kisten $B_{2k-1},
2.448 +B_{2k}$. Man weiß, dass die beinhalteten Objekte eine
2.449 +Summengröße $>1$ haben, sonst wären selbige in einer Kiste.
2.450 +Daraus folgt, man kann nicht mehr als die doppelte Anzahl an
2.451 +Kisten als beim Optimum erreichen!\\ (b) Inputfolge: $0.5,
2.452 +\frac{2}{n}, 0.5, \frac{2}{n}, 0.5, \frac{2}{n}, \ldots 0.5,
2.453 +\frac{2}{n}$.\\Next-Fit liefert nun immer Bins gefüllt mit $0.5
2.454 ++ \frac{2}{n}$. Darausfolgt $NF(I)=\frac{n}{2}$ und
2.455 +$OPT=\frac{n}{4}+1$ (weil $\frac{n}{2}$ mal 0.5er Objekte in
2.456 +$=\frac{n}{4}$ Kisten passen und $\frac{n}{2}$ $\frac{2}{n}$er
2.457 +Objekte in eine Kiste passen)\\ Laufzeit für Inputfolgen der
2.458 +Länge $n$: NF $O(n)$
2.459 +\subsubsection{First-Fit (FF)}
2.460 +Packe nächstes Objekt in die erste Kiste, in die es noch
2.461 +hineinpasst, wenn es eine solche Kiste gibt, sonst in eine neue
2.462 +Kiste.\\ \textbf{Beobachtung}: Zu jedem Zeitpunkt kann es
2.463 +höchstens eine Kiste geben, die weniger als halb voll ist.
2.464 +($\implies FF(I) \leq 2OPT(I)$)\\ \textbf{Satz 3}: (a) Für alle
2.465 +Inputfolgen $I$ gilt $FF(I)\leq \lceil\frac{17}{10}
2.466 +OPT(I)\rceil$. (b) Es gibt Inputfolgen $I$ mit
2.467 +$FF(I)\geq\frac{17}{10}(OPT(I)-1)$. (b') Es gibt Inputfolgen
2.468 +$I$ mit $FF(I)=\frac{10}{6}OPT(I)$.\\ \textbf{Beweis}\\ (b')
2.469 +Inputfolge der Länge $3\cdot6m$. Dabei je $6m$ Objekte der
2.470 +Größen $\frac{1}{7}+\epsilon, \frac{1}{3}+\epsilon,
2.471 +\frac{1}{2}+\epsilon$, welche in gegebener Reihenfolge in
2.472 +Gruppen eingegeben werden. FF liefert hierbei $m$ Kisten
2.473 +gefüllt mit den Objekten der Größe $\frac{1}{7}+\epsilon$
2.474 +(jeweils 6 pro Kiste) gefolgt von $\frac{6m}{2}=3m$ Kisten
2.475 +gefüllt mit Objekten der Größe $\frac{1}{3}+\epsilon$ (jeweils
2.476 +2 pro Kiste) und schlussendlich $6m$ Kisten mit je einem Objekt
2.477 +der Größe $\frac{1}{2}+\epsilon$. Das macht in der Summe $10m$
2.478 +Kisten. Die optimale Lösung packt je ein Objekt jeder Größe in
2.479 +eine Kiste und benötigt somit nur $6m$ Kisten.\\ Laufzeit für
2.480 +Inputfolgen der Länge $n$: FF $O(n^2) \rightarrow O(n \log n)$
2.481 +\subsubsection{Best-Fit (BF)}
2.482 +Verpacke das nächste Objekt in diejenige Kiste, in die es am
2.483 +besten passt (d.h. den geringsten Platz ungenutzt lässt).
2.484 +Verhalten von BF ähnlich zu FF. Laufzeit für Inputfolgen der
2.485 +Länge $n$: BF $O(n^2) \rightarrow O(n \log n)$
2.486 +\subsection{Offline Verfahren}
2.487 +\underline{NP-schwieriges Problem! Entscheidungsproblem ist NP-vollständig!}\\
2.488 +Zunächst wird die Anzahl $n$ und alle $n$ Objekte vorgegeben. Dann
2.489 +beginnt die Verpackung.\\ $n$ und $s_1, ..., s_n$ sind gegeben,
2.490 +bevor die Verpackung beginnt!\\ $\rightarrow$ \underline{Optimale
2.491 +Verpackung} kann durch erschöpfende Suche bestimmt werden. ABER:
2.492 +Benötigt exponentielle Zeit! Daher Approximimationsalgorithmen, die
2.493 +schneller sind aber dafür unter Umständen nicht optimal!\\
2.494 +Idee für Offline Approximationsalgorithmen: Sortiere die Objekte
2.495 +zunächst nach abnhemender Größe und verpacke größere Objekte zuerst!
2.496 +\subsubsection{First Fit Decreasing (FFD oder FFNI)}
2.497 +\textbf{Lemma 1}: Sei $I$ eine Folge von $n$ Objekten mit
2.498 +Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann
2.499 +haben alle von FFD in den Bins
2.500 +$B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackten Objekte eine
2.501 +Größe von höchstens $\frac{1}{3}$.
2.502 +\\ \textbf{Beweis}:
2.503 +%TODO:Elsässer hat das in seiner VL gemacht - aber hässlich lang
2.504 +\textbf{Lemma 2}: Sei $I$ eine Folge von $n$ Objekten mit
2.505 +Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann
2.506 +ist die Anzahl der Objekte, die FFD in die Kisten
2.507 +$B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackt, höchstens
2.508 +$m-1$.\\ \textbf{Beweis}: Annahme: Es gibt mehr als $m-1$
2.509 +Objekte. $x_1,\ldots,x_m$ in $I$, die FFD in extra Kisten
2.510 +verpacken. Dies führt zu einem Widerspruch.
2.511 +%TODO:Warum?
2.512 +\textbf{Satz}: Für alle Inputfolgen I
2.513 +gilt $FFD(I)\leq(4 OPT(I)+\frac{1}{3})$.\\ \textbf{Satz}:
2.514 +\begin{itemize}
2.515 + \item[1.] Für alle Inputfolgen $I$ gilt: $FFD(I)\leq \frac{11}{9} OPT(I)+4$
2.516 + \item[2.] Es gibt Inputfolgen $I$ mit: $FFD(I)=\frac{11}{9}OPT(I)$.
2.517 +\end{itemize}
2.518 +\textbf{Beweis}: %TODO
2.519 +\subsubsection{Best Fit Decreasing (BFD)}
2.520 +%TODO Nicht im Script???
2.521 +
2.522 +\newpage
2.523 +\section{Dynamische Programmierung}
2.524 +\textbf{Idee:} Speichern von zwischen Ergebnissen, welche sonst mehrfach
2.525 +berechnet werden müssten.\\
2.526 +\textbf{Vorgehen:}
2.527 +\begin{itemize}
2.528 + \item Rekursive Beschreibung des Problems P
2.529 + \item Bestimmung einer Menge T, die alle Teilprobleme von P enthält, auf die
2.530 + bei der Lösung von P zugegriffen wird.
2.531 + \item Bestimmung einer Reihenfolge $T_0,\ldots T_k$ der Probleme in T, so dass
2.532 + bei der Lösung von $T_i$ nur auf Probleme $T_j$ mit $j<i$ zurückgegriffen
2.533 + wird.
2.534 + \item Sukzessive Berechnung und Speicherung von Lösungen für $T_0,\ldots T_k$.
2.535 +\end{itemize}
2.536 +Wird im Script anhand der Fibonacci Zahlen demonstriert aber ist trivial \ldots
2.537 +\subsection{Matrixkettenprodukt (TODO)}
2.538 +%TODO
2.539 +\subsection{Optimale Suchbäume (TODO)}
2.540 +%TODO
2.541 +\subsection{Editierdistanz}
2.542 +Berechne für zwei gegebene Zeichenfolgen $A$ und $B$ möglichst effizient die
2.543 +Editier-Distanz $D(A,B)$ und eine minimale Folge von Editieroperationen, die
2.544 +$A$ in $B$ überführt.\\
2.545 +\textbf{Editieroperationen:}
2.546 +\begin{itemize}
2.547 + \item Ersetzen eines Zeichens von $A$ durch ein Zeichen von $B$
2.548 + \item Löschen eines Zeichens von $A$
2.549 + \item Einfügen eines Zeichens von $B$
2.550 +\end{itemize}
2.551 +\textbf{Einheitskostenmodell:}
2.552 +\[c(a,b)=\begin{cases}1 & \text{falls } a\neq b\\0 & \text{falls } a=b\end{cases}\]
2.553 +$a=\epsilon, b=\epsilon$ möglich Dreiecksungleichung soll für $c$ im
2.554 +allgemeinen gelten:
2.555 +\[c(a,c)\leq c(a,b)+c(b,c)\]
2.556 +$\rightarrow$ ein Buchstabe wird höchstens einmal
2.557 +verändert.\\
2.558 +Rekursionsgleichung, falls $m,n\geq 1$
2.559 +\[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\}\]
2.560 +Anfangsbedingung:\\
2.561 +\[D_{0,0}=D(\epsilon,\epsilon)=0\]
2.562 +\[D_{0,j}=D(\epsilon,B_j)=j\]
2.563 +\[D_{i,0}=D(A_i,\epsilon)=i\]
2.564 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus zur
2.565 +Editierdistanz, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
2.566 +basicstyle=\footnotesize]{./code/editierdistanz.code}
2.567 +\textbf{Spurgraph:}\\
2.568 +Übersicht über alle möglichen Spuren zur Transformation von $A$ in $B$,
2.569 +gerichtete Kanten von Knoten $(i,j)$ zu $(i+1,j)$, $(i,j+1)$ und $(i+1,j+1)$.
2.570 +Gewichtung der Kanten entspricht den Editierkosten. Kosten nehmen entlang eines
2.571 +optimalen Weges monoton zu. Jeder Weg mit monotin wachsenden Kosten von der
2.572 +linken oberen Ecke zur rechten unteren Ecke entspricht einer optimalen Spur. Zur
2.573 +Berechnung der Spur der minimalen Editieroperationen (es gibt mehrere
2.574 +Lösungen), kann folgender Algorithmus verwendet werden:
2.575 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus zum Spurgraphen, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\footnotesize]{./code/spurgraph.code}
2.576 +
2.577 +\section{Suche in Texten}
2.578 +\underline{Gegeben:} Text T $t_1t_2t_3\ldots t_n\in\Sigma^n$ und
2.579 +rin Muster P $p_1p_2p_3\ldots p_m\in\Sigma^m$\\
2.580 +\underline{Gesucht:} Ein oder alle Vorkommen des Musters im Text, d.h.
2.581 +Verschiebungen $i$ mit $0\leq i\leq n-m$.\\
2.582 +\textbf{Naives Verfahren:} iteriere über den Text und suche das Muster. Aufwand:
2.583 +$m\cdot(n-m+1)$ Vergleiche $\implies \Omega(n\cdot m)$
2.584 +\textbf{Verfahren nach Knuth-Morris-Pratt (KMP):}
2.585 +Präffix=Suffix Verfahren. Daraus resultiert eine Shiftmöglichkeit des Musters
2.586 +über den Text. Der Shift geschieht um $next[j]$=Länge des längsten Präfix von
2.587 +$P$, das echtes Suffix von $P_{1\ldots j}$ ist, wobei $j=$Position des letzten
2.588 +Vergleiches.\\
2.589 +\underline{Erstellung des $next[j]$ arrays über P.}\\
2.590 +$P=0101101011$
2.591 +\begin{table}[H]
2.592 + \centering
2.593 + \begin{tabular}{c|c|c|c|c|c|c|c|c|c}
2.594 + 1&2&3&4&5&6&7&8&9&10\\\hline
2.595 + 0&1&0&1&1&0&1&0&1&1\\\hline
2.596 + & &0& & & & & & & \\
2.597 + & &0&1& & & & & & \\
2.598 + & & & & &0& & & & \\
2.599 + & & & & &0&1& & & \\
2.600 + & & & & &0&1&0& & \\
2.601 + & & & & &0&1&0&1& \\
2.602 + & & & & &0&1&0&1&1\\
2.603 + \end{tabular}
2.604 + \caption{next[j] Beispiel}
2.605 + \label{tab:nextJ}
2.606 +\end{table}
2.607 +$\rightarrow next[j]=[0,0,1,2,0,1,2,3,4,5]$\\
2.608 +\underline{Algorithmus:}
2.609 +\lstinputlisting[language=Java,label=lst:TTlookup,caption=KMP Algorithmus,
2.610 +captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\footnotesize]{./code/kmp.code}
2.611 +\underline{Analyse:}
2.612 +inkrement $j$ = inkrement $i$ und dekrement $j$ = inkrement $j$!
2.613 +$\rightarrow O(n)$ hinzu kommt noch die Berechnung des next-arrays mit $O(m)$.\\
2.614 +KMP kann also mit $O(n+m)$ berechnet werden. (i.e. Untere Schranke
2.615 +$\Omega(m+n/m)$)
2.616 +
2.617 +\newpage
2.618 +\begin{appendix}
2.619 +\section{Landau-Symbole}
2.620 +\begin{figure}[H]
2.621 +\centering
2.622 +\includegraphics[scale=0.45]{img/landau_sym}
2.623 +\caption{Definition der Landau Symbole}
2.624 +\label{fig:landau_sym}
2.625 +\end{figure}
2.626 +\end{appendix}
2.627 +\end{document}
2.628 \ No newline at end of file
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/code/AzyklischeNetzwerke.code Tue Feb 22 19:02:39 2011 +0100
3.3 @@ -0,0 +1,12 @@
3.4 +Sortiere G=(V,E,c) topologisch;
3.5 +DIST[s]=0;
3.6 +forall(v:V\{s}){
3.7 + DIST[v]=infty;
3.8 +}
3.9 +U={v|v:V mit num(v)<n};
3.10 +while(!U.Empty) {
3.11 + Wähle und streiche Knoten u:U mit kleinstem num-Wert;
3.12 + forall(e=(u,v):E) {
3.13 + if(DIST[v]>DIST[u]+c(u,v)) {
3.14 + DIST[v]=DIST[u]+c(u,v);
3.15 +}}}
3.16 \ No newline at end of file
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/code/BelmanFord.code Tue Feb 22 19:02:39 2011 +0100
4.3 @@ -0,0 +1,17 @@
4.4 +DIST[s]=0;
4.5 +Z[s]=0;
4.6 +forall(v:V\{s}) {
4.7 + DIST[v]=infty;
4.8 + Z[v]=0;
4.9 +}
4.10 +U={s};
4.11 +while(!U.Empty) {
4.12 + Wähle und streiche Knoten u am Kopf von U;
4.13 + Z[u]=Z[u]+1;
4.14 + if Z[u]>n
4.15 + return "negativer Zyklus";
4.16 + forall(e=(u,v):E) {
4.17 + if(DIST[v]>DIST[u]+c(u,v)) {
4.18 + DIST[v]=DIST[u]+c(u,v);
4.19 + U=[U,{v}];
4.20 +}}}
4.21 \ No newline at end of file
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/code/dijkstra.code Tue Feb 22 19:02:39 2011 +0100
5.3 @@ -0,0 +1,13 @@
5.4 +DIST[s]=0;
5.5 +Insert(U,0,s);
5.6 +forall(v:V\{s}) {
5.7 + DIST[v]=infty;
5.8 + Insert(U, infty, v);
5.9 +}
5.10 +while !Empty(U) {
5.11 + (d,u)=DeleteMin(U);
5.12 + forall(e=(u,v):E) {
5.13 + if(DIST[v]>DIST[u]+c(u,v)){
5.14 + DIST[v]=DIST[u]+c(u,v);
5.15 + DecreaseKey(U,v,DIST[v]);
5.16 +}}}
5.17 \ No newline at end of file
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/code/editierdistanz.code Tue Feb 22 19:02:39 2011 +0100
6.3 @@ -0,0 +1,10 @@
6.4 +Input: Zwei Zeichenketten A und B
6.5 +Output: Matrix D=(Dij)
6.6 +D[0,0]:= 0
6.7 +for i := 1 to m do D[i,0] = i
6.8 +for j := 1 to n do D[0,j] = j
6.9 +for i := 1 to m do
6.10 + for j := 1 to n do
6.11 + D[i,j] := min(D[i - 1,j] + 1,
6.12 + D[i,j - 1] + 1,
6.13 + D[i-1,j-1]+c(ai,bj))
6.14 \ No newline at end of file
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/code/kmp.code Tue Feb 22 19:02:39 2011 +0100
7.3 @@ -0,0 +1,34 @@
7.4 +KMP := proc (T::string, P::string)
7.5 +# Input: Text T und Muster P
7.6 +# Output: Liste L mit Verschiebungen i,
7.7 +# an denen P in T vorkommt
7.8 + n := length (T); m := length(P);
7.9 + L := []; next := KMPnext(P);
7.10 + j := 0;
7.11 + for i from 1 to n do
7.12 + whilej>0and T[i]!=P[j+1]
7.13 + do j := next [j] od;
7.14 + if T[i] = P[j+1] then j := j+1 fi;
7.15 + if j = m then
7.16 + L := [L[] , i-m];
7.17 + j := next [j]
7.18 + fi;
7.19 + od;
7.20 + RETURN (L);
7.21 +end;
7.22 +
7.23 +KMPnext := proc (P : : string)
7.24 +#Input : Muster P
7.25 +#Output : next-Array für P
7.26 + m := length (P);
7.27 + next := array (1..m);
7.28 + next [1] := 0;
7.29 + j := 0;
7.30 + for i from 2 to m do
7.31 + while j > 0 and P[i] <> P[j+1]
7.32 + do j := next [j] od;
7.33 + if P[i] = P[j+1] then j := j+1 fi;
7.34 + next [i] := j
7.35 + od;
7.36 + RETURN (next);
7.37 +end;
7.38 \ No newline at end of file
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/code/quicksort.code Tue Feb 22 19:02:39 2011 +0100
8.3 @@ -0,0 +1,10 @@
8.4 +Input: unsortierter Bereich [p, r] in Array A
8.5 +Output: sortierter Bereich [p, r] in Array A
8.6 + if r > p then
8.7 + wähle Pivotelement x = A[r]
8.8 + m = partition(A, p , r)
8.9 + /* Teile A bzgl. x auf:
8.10 + * A[p],...,A[m-1] <= x <= A[m+1],...,A[r]
8.11 + */
8.12 + Quicksort(A, p , m - 1)
8.13 + Quicksort (A, m + 1, r)
8.14 \ No newline at end of file
9.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
9.2 +++ b/code/spannbaeumeGreedy.code Tue Feb 22 19:02:39 2011 +0100
9.3 @@ -0,0 +1,6 @@
9.4 +Algorithmus Generischer-MST(G,c);
9.5 +A = EmptySet;
9.6 +while(A ist kein Spannbaum) {
9.7 + Finde sichere Kante (u,v) für A;
9.8 + A = [A, {(u,v)}];
9.9 +}
9.10 \ No newline at end of file
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/code/spannbaeumeKruskal.code Tue Feb 22 19:02:39 2011 +0100
10.3 @@ -0,0 +1,12 @@
10.4 +A = EmptySet;
10.5 +forall(v:V)
10.6 + Bv={v};
10.7 +Erzeuge eine Liste L der Kanten in E, welche gemäß
10.8 +nicht-fallenden Kantenkosten sortiert ist;
10.9 +forall (u,v):L {
10.10 + B1=FIND(u);
10.11 + B2=FIND(v);
10.12 + if(B1!=B2)
10.13 + A=[A,{(u,v)}];
10.14 + UNION(B1, B2, B1);
10.15 +}
10.16 \ No newline at end of file
11.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
11.2 +++ b/code/spannbaeumePrim.code Tue Feb 22 19:02:39 2011 +0100
11.3 @@ -0,0 +1,12 @@
11.4 +forall(v:V)
11.5 + Insert(Q, infty, v);
11.6 +Wähle einen Knoten w:V als Wurzel;
11.7 +DecreaseKey(Q, 0, w);
11.8 +p[w]=nil;
11.9 +while(!Empty(Q)) {
11.10 + (d,u)=DeleteMin(Q);
11.11 + forall((u,v):E)
11.12 + if(v:Q && c(u,v)<v.Key) {
11.13 + DecreaseKey(Q, c(u,v), v);
11.14 + p[v]=u;
11.15 + }
11.16 \ No newline at end of file
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/code/spurgraph.code Tue Feb 22 19:02:39 2011 +0100
12.3 @@ -0,0 +1,12 @@
12.4 +Input: Berechnete Matrix D
12.5 +Output: Sequenz der Editieroperationen
12.6 +if i==0 & j==0 then return
12.7 +if i!=0 and D[i,j]==D[i-1,j]+1
12.8 + then Editieroperationen(i-1,j)
12.9 + "lösche a[i]"
12.10 +else if j!=0 and D[i,j]==D[i,j-1]+1
12.11 + then Editieroperationen(i,j-1)
12.12 + "füge b[j] ein"
12.13 +else /* D[i,j]=D[i-1,j-1 ]+c(a[i],b[j]) */
12.14 + Editieroperationen(i-1,j-1)
12.15 + "ersetze a[i] durch b[j]"
12.16 \ No newline at end of file
13.1 --- a/comp.log Thu Jan 20 00:56:20 2011 +0100
13.2 +++ b/comp.log Tue Feb 22 19:02:39 2011 +0100
13.3 @@ -106,21 +106,147 @@
13.4 ("C:\Program Files\MikTex\tex\latex\oberdiek\bookmark.sty"
13.5 ("C:\Program Files\MikTex\tex\latex\oberdiek\auxhook.sty")
13.6 ("C:\Program Files\MikTex\tex\latex\oberdiek\bkm-dvips.def"))
13.7 -(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
13.8 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\algori
13.9 thms_theory\exzerpt.aux)
13.10 ("C:\Program Files\MikTex\tex\latex\hyperref\nameref.sty"
13.11 ("C:\Program Files\MikTex\tex\latex\oberdiek\refcount.sty")
13.12 ("C:\Program Files\MikTex\tex\generic\oberdiek\gettitlestring.sty"))
13.13 ("C:\Program Files\MikTex\tex\latex\amsfonts\umsa.fd")
13.14 ("C:\Program Files\MikTex\tex\latex\amsfonts\umsb.fd")
13.15 -(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
13.16 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\algori
13.17 thms_theory\exzerpt.toc) [1] ("C:\Program Files\MikTex\tex\latex\base\t1cmtt.fd
13.18 ")
13.19 -(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
13.20 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\algori
13.21 thms_theory\exzerpt.bbl) [2] [3] <img/cl_pair.eps> [4] [5] [6] [7] [8] [9]
13.22 [10] [11] <img/landau_sym.eps> AED: lastpage setting LastPage
13.23 [12]
13.24 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\algori
13.25 +thms_theory\exzerpt.aux) )
13.26 +Output written on exzerpt.dvi (12 pages, 55792 bytes).
13.27 +Transcript written on exzerpt.log.
13.28 +This is pdfTeX, Version 3.1415926-1.40.10 (MiKTeX 2.8)
13.29 +entering extended mode
13.30 +
13.31 (M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
13.32 +thms_theory/exzerpt.tex
13.33 +LaTeX2e <2009/09/24>
13.34 +Babel <v3.8l> and hyphenation patterns for english, dumylang, nohyphenation, ge
13.35 +rman, ngerman, german-x-2009-06-19, ngerman-x-2009-06-19, french, loaded.
13.36 +("C:\Program Files\MikTex\tex\latex\base\article.cls"
13.37 +Document Class: article 2007/10/19 v1.4h Standard LaTeX document class
13.38 +("C:\Program Files\MikTex\tex\latex\base\size11.clo"))
13.39 +("C:\Program Files\MikTex\tex\generic\babel\babel.sty"
13.40 +*************************************
13.41 +* Local config file bblopts.cfg used
13.42 +*
13.43 +("C:\Program Files\MikTex\tex\latex\00miktex\bblopts.cfg")
13.44 +("C:\Program Files\MikTex\tex\generic\babel\ngermanb.ldf"
13.45 +("C:\Program Files\MikTex\tex\generic\babel\babel.def")))
13.46 +("C:\Program Files\MikTex\tex\latex\base\fontenc.sty"
13.47 +("C:\Program Files\MikTex\tex\latex\base\t1enc.def"))
13.48 +("C:\Program Files\MikTex\tex\latex\base\inputenc.sty"
13.49 +("C:\Program Files\MikTex\tex\latex\base\latin1.def"))
13.50 +("C:\Program Files\MikTex\tex\latex\hyperref\hyperref.sty"
13.51 +("C:\Program Files\MikTex\tex\generic\oberdiek\ltxcmds.sty")
13.52 +("C:\Program Files\MikTex\tex\generic\oberdiek\infwarerr.sty")
13.53 +("C:\Program Files\MikTex\tex\latex\graphics\keyval.sty")
13.54 +("C:\Program Files\MikTex\tex\generic\oberdiek\kvsetkeys.sty"
13.55 +("C:\Program Files\MikTex\tex\generic\oberdiek\etexcmds.sty"))
13.56 +("C:\Program Files\MikTex\tex\generic\oberdiek\pdfescape.sty"
13.57 +("C:\Program Files\MikTex\tex\generic\oberdiek\pdftexcmds.sty"
13.58 +("C:\Program Files\MikTex\tex\generic\oberdiek\ifluatex.sty")))
13.59 +("C:\Program Files\MikTex\tex\generic\oberdiek\ifpdf.sty")
13.60 +("C:\Program Files\MikTex\tex\generic\oberdiek\ifvtex.sty")
13.61 +("C:\Program Files\MikTex\tex\generic\ifxetex\ifxetex.sty")
13.62 +("C:\Program Files\MikTex\tex\latex\oberdiek\hycolor.sty"
13.63 +("C:\Program Files\MikTex\tex\latex\oberdiek\xcolor-patch.sty"))
13.64 +("C:\Program Files\MikTex\tex\latex\oberdiek\letltxmacro.sty")
13.65 +("C:\Program Files\MikTex\tex\latex\oberdiek\kvoptions.sty")
13.66 +("C:\Program Files\MikTex\tex\latex\hyperref\pd1enc.def")
13.67 +("C:\Program Files\MikTex\tex\generic\oberdiek\intcalc.sty")
13.68 +("C:\Program Files\MikTex\tex\latex\00miktex\hyperref.cfg")
13.69 +("C:\Program Files\MikTex\tex\latex\ltxmisc\url.sty")
13.70 +("C:\Program Files\MikTex\tex\generic\oberdiek\bitset.sty"
13.71 +("C:\Program Files\MikTex\tex\generic\oberdiek\bigintcalc.sty"))
13.72 +("C:\Program Files\MikTex\tex\generic\oberdiek\atbegshi.sty"))
13.73 +
13.74 +Package hyperref Message: Driver (default): hdvips.
13.75 +
13.76 +("C:\Program Files\MikTex\tex\latex\hyperref\hdvips.def"
13.77 +("C:\Program Files\MikTex\tex\latex\hyperref\pdfmark.def"
13.78 +("C:\Program Files\MikTex\tex\latex\oberdiek\rerunfilecheck.sty"
13.79 +("C:\Program Files\MikTex\tex\latex\oberdiek\atveryend.sty")
13.80 +("C:\Program Files\MikTex\tex\generic\oberdiek\uniquecounter.sty"))))
13.81 +("C:\Program Files\MikTex\tex\latex\vaucanson-g\vaucanson-g.sty"
13.82 +("C:\Program Files\MikTex\tex\latex\base\ifthen.sty")
13.83 +("C:\Program Files\MikTex\tex\latex\xcolor\xcolor.sty"
13.84 +("C:\Program Files\MikTex\tex\latex\00miktex\color.cfg")
13.85 +("C:\Program Files\MikTex\tex\latex\graphics\dvips.def"))
13.86 +("C:\Program Files\MikTex\tex\generic\vaucanson-g\VCColor-names.def")
13.87 +("C:\Program Files\MikTex\tex\latex\pstricks\pstricks.sty"
13.88 +("C:\Program Files\MikTex\tex\generic\pstricks\pstricks.tex"
13.89 +("C:\Program Files\MikTex\tex\generic\xkeyval\pst-xkey.tex"
13.90 +("C:\Program Files\MikTex\tex\latex\xkeyval\xkeyval.sty"
13.91 +("C:\Program Files\MikTex\tex\generic\xkeyval\xkeyval.tex")))
13.92 +("C:\Program Files\MikTex\tex\generic\pstricks\pst-fp.tex"
13.93 +`pst-fp' v0.05, 2010/01/17 (hv))
13.94 +`PSTricks' v2.12 <2010/09/16> (tvz)
13.95 +("C:\Program Files\MikTex\tex\generic\pstricks\pstricks.con"))
13.96 +("C:\Program Files\MikTex\tex\generic\pstricks\pst-fp.tex"))
13.97 +("C:\Program Files\MikTex\tex\latex\pst-node\pst-node.sty"
13.98 +("C:\Program Files\MikTex\tex\generic\pst-node\pst-node.tex"
13.99 + v1.13, 2010/06/06)) ("C:\Program Files\MikTex\tex\latex\pst-plot\pst-plot.sty"
13.100 +("C:\Program Files\MikTex\tex\generic\pst-plot\pst-plot.tex"
13.101 +("C:\Program Files\MikTex\tex\generic\multido\multido.tex"
13.102 + v1.42, 2010/05/14 <tvz>) v1.21, 2010/09/28 (tvz,hv)))
13.103 +("C:\Program Files\MikTex\tex\latex\pst-coil\pst-coil.sty"
13.104 +("C:\Program Files\MikTex\tex\generic\pst-coil\pst-coil.tex"
13.105 + v1.21, 2010/09/28)) ("C:\Program Files\MikTex\tex\latex\multido\multido.sty")
13.106 +("C:\Program Files\MikTex\tex\latex\pst-3d\pst-3d.sty"
13.107 +("C:\Program Files\MikTex\tex\generic\pst-3d\pst-3d.tex"
13.108 +`PST-3d' v1.11, 2010/02/14 (tvz)))
13.109 +("C:\Program Files\MikTex\tex\latex\tools\calc.sty")
13.110 +("C:\Program Files\MikTex\tex\generic\vaucanson-g\Vaucanson-G.tex")
13.111 +("C:\Program Files\MikTex\tex\generic\vaucanson-g\VCPref-default.tex"))
13.112 +("C:\Program Files\MikTex\tex\latex\oberdiek\hypcap.sty")
13.113 +("C:\Program Files\MikTex\tex\latex\fancyhdr\fancyhdr.sty")
13.114 +("C:\Program Files\MikTex\tex\latex\graphics\graphicx.sty"
13.115 +("C:\Program Files\MikTex\tex\latex\graphics\graphics.sty"
13.116 +("C:\Program Files\MikTex\tex\latex\graphics\trig.sty")
13.117 +("C:\Program Files\MikTex\tex\latex\00miktex\graphics.cfg")))
13.118 +("C:\Program Files\MikTex\tex\latex\lastpage\lastpage.sty")
13.119 +("C:\Program Files\MikTex\tex\latex\preprint\fullpage.sty")
13.120 +("C:\Program Files\MikTex\tex\latex\ams\classes\amsthm.sty")
13.121 +("C:\Program Files\MikTex\tex\latex\ams\math\amsmath.sty"
13.122 +For additional information on amsmath, use the `?' option.
13.123 +("C:\Program Files\MikTex\tex\latex\ams\math\amstext.sty"
13.124 +("C:\Program Files\MikTex\tex\latex\ams\math\amsgen.sty"))
13.125 +("C:\Program Files\MikTex\tex\latex\ams\math\amsbsy.sty")
13.126 +("C:\Program Files\MikTex\tex\latex\ams\math\amsopn.sty"))
13.127 +("C:\Program Files\MikTex\tex\latex\amsfonts\amsfonts.sty")
13.128 +("C:\Program Files\MikTex\tex\latex\float\float.sty")
13.129 +("C:\Program Files\MikTex\tex\latex\paralist\paralist.sty")
13.130 +("C:\Program Files\MikTex\tex\latex\listings\listings.sty"
13.131 +("C:\Program Files\MikTex\tex\latex\listings\lstmisc.sty")
13.132 +("C:\Program Files\MikTex\tex\latex\listings\listings.cfg"))
13.133 +("C:\Program Files\MikTex\tex\latex\oberdiek\bookmark.sty"
13.134 +("C:\Program Files\MikTex\tex\latex\oberdiek\auxhook.sty")
13.135 +("C:\Program Files\MikTex\tex\latex\oberdiek\bkm-dvips.def"))
13.136 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\algori
13.137 +thms_theory\exzerpt.aux)
13.138 +("C:\Program Files\MikTex\tex\latex\hyperref\nameref.sty"
13.139 +("C:\Program Files\MikTex\tex\latex\oberdiek\refcount.sty")
13.140 +("C:\Program Files\MikTex\tex\generic\oberdiek\gettitlestring.sty"))
13.141 +("C:\Program Files\MikTex\tex\latex\amsfonts\umsa.fd")
13.142 +("C:\Program Files\MikTex\tex\latex\amsfonts\umsb.fd")
13.143 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\algori
13.144 +thms_theory\exzerpt.toc) [1] ("C:\Program Files\MikTex\tex\latex\base\t1cmtt.fd
13.145 +")
13.146 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\algori
13.147 +thms_theory\exzerpt.bbl) [2] [3] <img/cl_pair.eps> [4] [5] [6] [7] [8] [9]
13.148 +[10] [11] <img/landau_sym.eps> AED: lastpage setting LastPage
13.149 +[12]
13.150 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\algori
13.151 thms_theory\exzerpt.aux) )
13.152 -Output written on exzerpt.dvi (12 pages, 67136 bytes).
13.153 +Output written on exzerpt.dvi (12 pages, 55792 bytes).
13.154 Transcript written on exzerpt.log.
14.1 --- a/exzerpt.aux Thu Jan 20 00:56:20 2011 +0100
14.2 +++ b/exzerpt.aux Tue Feb 22 19:02:39 2011 +0100
14.3 @@ -55,9 +55,9 @@
14.4 \newlabel{cl_pair}{{1}{4}{Nächste Paare: Prüf Distanz\relax }{figure.1}{}}
14.5 \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.3.2}Analyse}{4}{subsubsection.2.3.2}}
14.6 \@writefile{toc}{\contentsline {subsection}{\numberline {2.4}Segmentschnitt}{4}{subsection.2.4}}
14.7 +\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.4.1}Algorithmus}{4}{subsubsection.2.4.1}}
14.8 \BKM@entry{id=14,dest={73756273756273656374696F6E2E322E342E32}}{416E616C797365}
14.9 \BKM@entry{id=15,dest={73756273656374696F6E2E322E35}}{506F6C796E6F6D70726F64756B7420756E64204661737420466F75726965722D5472616E73666F726D6174696F6E}
14.10 -\@writefile{toc}{\contentsline {subsubsection}{\numberline {2.4.1}Algorithmus}{5}{subsubsection.2.4.1}}
14.11 \@writefile{toc}{\contentsline {subsubsection}{\numberline {2.4.2}Analyse}{5}{subsubsection.2.4.2}}
14.12 \@writefile{toc}{\contentsline {subsection}{\numberline {2.5}Polynomprodukt und Fast Fourier-Transformation}{5}{subsection.2.5}}
14.13 \BKM@entry{id=16,dest={73656374696F6E2E33}}{52616E646F6D6973696572756E67}
15.1 Binary file exzerpt.dvi has changed
16.1 --- a/exzerpt.log Thu Jan 20 00:56:20 2011 +0100
16.2 +++ b/exzerpt.log Tue Feb 22 19:02:39 2011 +0100
16.3 @@ -1,4 +1,4 @@
16.4 -This is pdfTeX, Version 3.1415926-1.40.10 (MiKTeX 2.8) (preloaded format=latex 2011.1.19) 20 JAN 2011 00:54
16.5 +This is pdfTeX, Version 3.1415926-1.40.10 (MiKTeX 2.8) (preloaded format=latex 2011.1.19) 31 JAN 2011 23:07
16.6 entering extended mode
16.7 **M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algor
16.8 ithms_theory/exzerpt.tex
16.9 @@ -604,7 +604,7 @@
16.10 File: bkm-dvips.def 2010/04/08 v1.12 bookmark driver for dvips (HO)
16.11 \BKM@id=\count156
16.12 ))
16.13 -(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
16.14 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\algori
16.15 thms_theory\exzerpt.aux)
16.16 LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 29.
16.17 LaTeX Font Info: ... okay on input line 29.
16.18 @@ -655,7 +655,7 @@
16.19 ("C:\Program Files\MikTex\tex\latex\amsfonts\umsb.fd"
16.20 File: umsb.fd 2009/06/22 v3.00 AMS symbols B
16.21 )
16.22 -(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
16.23 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\algori
16.24 thms_theory\exzerpt.toc)
16.25 \tf@toc=\write3
16.26 [1
16.27 @@ -665,7 +665,7 @@
16.28 ("C:\Program Files\MikTex\tex\latex\base\t1cmtt.fd"
16.29 File: t1cmtt.fd 1999/05/25 v2.5h Standard LaTeX font definitions
16.30 )
16.31 -(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
16.32 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\algori
16.33 thms_theory\exzerpt.bbl) [2] [3]
16.34 File: img/cl_pair.eps Graphic file (type eps)
16.35 <img/cl_pair.eps> [4] [5] [6] [7] [8] [9]
16.36 @@ -677,17 +677,17 @@
16.37 Package atveryend Info: Executing hook `AfterLastShipout' on input line 250.
16.38 \BKM@file=\write4
16.39
16.40 -(M:/Documents/004_Uni-Freiburg/VLR/Semester_1/Algorithmentheorie/Exzerpt/algori
16.41 +(M:\Documents\004_Uni-Freiburg\VLR\Semester_1\Algorithmentheorie\Exzerpt\algori
16.42 thms_theory\exzerpt.aux)
16.43 Package atveryend Info: Empty hook `AtVeryEndDocument' on input line 250.
16.44 )
16.45 Here is how much of TeX's memory you used:
16.46 11535 strings out of 495270
16.47 164528 string characters out of 3180477
16.48 - 305233 words of memory out of 3000000
16.49 + 304233 words of memory out of 3000000
16.50 14498 multiletter control sequences out of 15000+200000
16.51 19725 words of font info for 55 fonts, out of 3000000 for 9000
16.52 14 hyphenation exceptions out of 8191
16.53 44i,9n,53p,1340b,398s stack positions out of 5000i,500n,10000p,200000b,50000s
16.54
16.55 -Output written on exzerpt.dvi (12 pages, 67136 bytes).
16.56 +Output written on exzerpt.dvi (12 pages, 55792 bytes).
17.1 --- a/exzerpt.tex Thu Jan 20 00:56:20 2011 +0100
17.2 +++ b/exzerpt.tex Tue Feb 22 19:02:39 2011 +0100
17.3 @@ -235,6 +235,11 @@
17.4
17.5 \newpage
17.6 \section{Dynamische Programmierung}
17.7 + \subsection{Matrixkettenprodukt}
17.8 + \subsection{Optimale Suchbäume}
17.9 + \subsection{Editierdistanz}
17.10 +
17.11 + \section{Suche in Texten}
17.12
17.13
17.14 \newpage
18.1 --- a/exzerpt.toc Thu Jan 20 00:56:20 2011 +0100
18.2 +++ b/exzerpt.toc Tue Feb 22 19:02:39 2011 +0100
18.3 @@ -11,7 +11,7 @@
18.4 \contentsline {subsubsection}{\numberline {2.3.1}Algorithmus}{3}{subsubsection.2.3.1}
18.5 \contentsline {subsubsection}{\numberline {2.3.2}Analyse}{4}{subsubsection.2.3.2}
18.6 \contentsline {subsection}{\numberline {2.4}Segmentschnitt}{4}{subsection.2.4}
18.7 -\contentsline {subsubsection}{\numberline {2.4.1}Algorithmus}{5}{subsubsection.2.4.1}
18.8 +\contentsline {subsubsection}{\numberline {2.4.1}Algorithmus}{4}{subsubsection.2.4.1}
18.9 \contentsline {subsubsection}{\numberline {2.4.2}Analyse}{5}{subsubsection.2.4.2}
18.10 \contentsline {subsection}{\numberline {2.5}Polynomprodukt und Fast Fourier-Transformation}{5}{subsection.2.5}
18.11 \contentsline {section}{\numberline {3}Randomisierung}{6}{section.3}
19.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
19.2 +++ b/img/dijkstraExT.eps Tue Feb 22 19:02:39 2011 +0100
19.3 @@ -0,0 +1,99 @@
19.4 +%!PS-Adobe-3.0 EPSF-3.0
19.5 +%%Pages: 1
19.6 +%%BoundingBox: 0 0 420 263
19.7 +%%DocumentData: Clean7Bit
19.8 +%%LanguageLevel: 2
19.9 +%%EndComments
19.10 +%%Page: 1 1
19.11 +save 9 dict begin
19.12 +{/T currentfile/ASCII85Decode filter def/DeviceGray setcolorspace
19.13 +/F T/LZWDecode filter def
19.14 +<</ImageType 1/Width 420/Height 263/BitsPerComponent
19.15 +8/ImageMatrix[1 0 0 -1 0 263]/Decode
19.16 +[0 1]/DataSource F>> image
19.17 + F closefile T closefile}
19.18 +%%BeginData:
19.19 +exec
19.20 +J3Vsg3$]7K#D>EP:q1$o*=mro@So+\<\5,H7Uo<*jE<[.O@Wn[3@'nb-^757;Rp>H>q_R=AlC^cenm
19.21 +@9:1mM9jS"!dTMT<$3[GQ$8#0$s<4ZX!SPQ1`C/m<k<ioH)<b27<j_DJ9YY9QY3us(#B=(5][[Uj:h
19.22 +%I-MmT2B[NO%68f4hF(]=-sRPIT*h5QO"5KGpOdO(r7kN:pMICPPiee,X#Uhln!.j(Bj8]KmR=P9AC
19.23 +[8@@5d:M"DiM4/uYRHZH+:LTdK7.mS8A0nNl1-"LOROaF.[t?i.,??/SSI^&mbaaJa[tR8RC8_P+#<
19.24 +!L\g@P5=Y*Sc$`#A=HEHZi/+SO$*r_OnTPKaVCPQ(SAK=#B+U/1C]r]0.T!;.N].74.\6`_&[]s$3.
19.25 +^QNFp.0DVmRLj;M8>ut)6VI=d#pKMB*tY,6.<:-Ia>:XH0BL;&\r#s/&pjTj+q!][K-U[@/]4X%KLM
19.26 +h,h&mh8$3"RtW,-^0Q*EH5["bg-"L?/5)!`9b%&qr]`!B>JJ$[RlgG-kB7):ZC"!KTWT[(d%1<dp8`
19.27 +idQbPk@2cPO/64ckHom6-tiIoH(@f4,Fp$'<85tb3/]/29KifC-g,N,o7#LP]G/$Te=S9'Zb:sBQ;I
19.28 +b;TOPePk)^DUB5fT)a21dRj(jMXJJuK`GB.E5Ljib0ht81a\p`Je%m%J`=7;m=S;`1Am$U^lV+kjBa
19.29 +6.X`[#;VP'28RX.4"">$TcpTgCo*?it7Z7;/1,DHpqEEZU4J\g$jOa)0RTbg-H)L;"I`lE!!3W2aA:
19.30 +QP7+5Zrd4j#!EeA'_l+h3iNT!YVF/m&@S;=oN;G7rHD^hj-N0-B5#@Qj%@$!Gc[gJ$7F#Q3SHfS\RH
19.31 +#3i"kWQOZaH9@]8=HKV`Thn<7Ga&:#$cM+@ke5Cp1N?uqrRl@*?"(kaCHateo)6<defDLn%cB,N$DL
19.32 +:\So\.GN,H`jAP8g(_uk0(srl^;XiWgb6s!,0&7DUZ6IHMTL',(!R2HSVZQe9c*2@[FbQS-1L]_K<'
19.33 +&bK/lH(!S0iE]_>d]Ta7LOKK:<8`8CE"4S^ri]kak*<[6$FT'*Xjl"5c=Guk!,^J-h8dBI#GDO;&q&
19.34 +fYBr!j#8<h3X&QrG[U%>R=1&K$a-.2@b0it0hJKPJ&V`L)aCr$C'\!$pC+3E3.a(kG$1_cG!iBf2AS
19.35 +k7a3ZA=dq.cCmZ%SC1%XT?o#$QrLd9#GkAa'cN<O3?G.jB(T4p::VsR6DcS#m>f;"MpEd$g(`PS8$c
19.36 +FYebE-*iH;b8@r^6L@WQCuhr"/V9nrb'_bMd!lW&hq-EZ7n\0t)#+dL5>0/[N&npu85e?VnU-@\U`J
19.37 +mrWK\k[TH5g[>fRba8G1Om\bn^st7H6K'>n*Tt1#-+;si(CES#o=\O;VL*<r*@W,5KSLq\t,88$P11
19.38 +Sn[hX>ZkHs.o1HRh?B9T6kD/ijI?/Tt.GW*jWdYJS&)d`S^Mj7Q]eloso(KjPl2LKD/GK5KTs(dnr%
19.39 +"u!CBpgMHcl=RcsmEL_X.u9h8$7j%\#ime/nE7O[M7^,uBM($*95g7h.-_]?:sYbH_9jU9@4>&k8!?
19.40 +Cr!3X]N6>uP!hKk`\#tXZUUmhSK&j$e6=7I1"mor\WRr1,,2BKh[h`q/@NWmO6iP"b"IDdpVG8Tf.8
19.41 +1>r3\C/P3O&@]/'lU0qra=:5c??bkAA<LkORK:(+GiL/F-i0Y1#D/JP,/mkk2<ctp@!"k-..*:VAar
19.42 +?Vt!0\&_0;idJ4<7D=5[8GJtX\AIh$nYI),P>nmZW7V@AR<rMl9AM*9'pa!f8Mk?Z;@t=R--k:eW"7
19.43 +q'='E*g<*Ed#$MG;UsLDgXh^T3P23NdgPVOXDr"!u`?&9C^!*;$-iMM?-C89YG@*:\Q%!%`r*Z,*<b
19.44 +:dK?V/64I_YYQ!Gl1(*Zp!WM.R?WanT1+J`4j3+PnE2p-gWDq%bcLj)a3aO(D.B6^hP%AD$80cDkTC
19.45 +k3E4SS$S?sc(6-SPN&!D#bC@/2-N__UI,?jJ"U10D",7*2En%!?lE@>R]SXaJsjXTk.8U[g9)m1_-.
19.46 +W2J\!p9%AU'T[V(9XfqO0a^`0j$]'@nEZ*L/equaa-]<:gBDjk;:3lTlZQCDiZ(Cdnsq0%abE(S(j;
19.47 +K<_*8GVKHX8S<)>hTM0^"G>C"`-9WD:YGP1\Z<@=Ip2WG3CScqH@1f71Ss]#'"rh?0?QMGQ(2JiG]Q
19.48 +&S)Z](8"tTZ4Jb@+q:-jdm3,f+)#\g\]>O"5BJ6nC38X\O/c8sb(\7I7pZ(nVT3pl:^?!dJ?]4J@O4
19.49 +!t=a6riH0E>O@jk:gnqZ5G-AK@^0[?Hq2E$-tM+g<7E^rJW-T@p&m0Q;`]"VaVbW==J,[LL)_*=%_c
19.50 +?\N'C#G%ed$j^Al9h#I.S>4=:iR&0j89E4rpL_]G4?84.2BF-]P7QVdLPSeaLdY2R6m5e[0$uF)&Eo
19.51 +^DO6`'gA_noUnfnn\g(/-WE3dIHcpPuY\Jaaj&3"X"4%0IPN:FiC&f<,$<jF;iKnMe5ZTfESnI6M7b
19.52 +U87ugq=BLjrVENG)FZ,!t'SG(kPFBT]18GA#[.Z1+\q'OIcFSLbos$N.ZjQ*$%Eq\WBX8Pq1hJ-c5p
19.53 +-$R<#`LflnA,n-OpV&!4U@K&7+aK5l$e5hWBa":jW2B62e.tk^1.#FIZPG$Dd`2IuT(%Co6J^?:T$'
19.54 +%VJ(s`m>4=AAD<_"Ng$l^A>)U(RP.;"u/*+=pa:P/j(6)]L+$>HH<,4dq<>kNULg4)g@"uFUD"-HOM
19.55 +,#L2p+[UG6TZ#LC8;%Zp)^,`b6P,2Qi?gtu*6rF9@Z(qOM%.OO*23\ce=#7\*GIql#.0bU#Z1ptWE?
19.56 +BJe@_ST\\LSNQt2kqfY3i;-Q^1-.3c/BMMsfm;b3S-"N&<V'`c<eLo>Hl&O<-+;#1fYbtK>R9!&[!p
19.57 +*Aq"?`!jcN5umR;FUXl!!'a/OV$e.8=RJJ[D'3cE1]B,fb(Aek'g(a67?B$';]jhL'C7t7RShrYiOS
19.58 +ZK^p%/.:%r]1TcelU+9g]M"Ufa=GdMZK4de&JmYpMKV-o6CL6e0RKKo8P+cr%aE7)MDG5Z8qd`P("b
19.59 +NX1KS^!r`=[tmFfC!Wae?>*5t9+B+r:Eq+3VE>=[2s(JWddIK9@a%Ubet-e1qAXel(:7i??gP3KX]s
19.60 +IW*d6^R+Zo?i0qTE#&PkQkoj3lf`-'D?n"F2[<ag+;?Jg\%NU+(1B'IEaTm9Tto71gu`]G0=>Dh!!"
19.61 +q9N'_ca:"O0)K+M?5=$;<Yho5"c\`/8BpVqJ+'t4P)h_H'b#`[SW(M)"Nb[=!+>o^1q^EX9eRu%Hu:
19.62 +Sg&ad&BV$M]?:c+kM&dOtl>o#QA%K=^Zsd>e##udIG-8I`RX#Ak;8`?^RM;f+B0uBI\!oas:P='>cu
19.63 +,1SHD),^_Z/'UnVf%Sn<,@#sO2-_X)MWmG:\D!,7^V=V:I`?a6\-B_IEoKa,sp2GguZ7[XneHF<r!W
19.64 +N4P_'#sq.MW<rKu"hJ<dZYI&rFRM5R8?9.iO"/A!+:urN\;(a<0[\XFYCfHUl_@<n\<2-(3")ZY@)3
19.65 +EtNa:'J]FC:3Ama7qcmu1gC&MTdWTtaP=?u+A%t@EN+(`rm)LVC%Q0<k*9D[=X_QMXTg:<)DNeLMH.
19.66 +4e9=[N0F./pt.(L8IA?+%WjsKehhd?.=Q,aOPNnpsBkbGN+FhGU;8N%[mgQ.?MD:^m]O[:qM:=,g7/
19.67 +=!M:-g;bVg\O[Y"Kg9sHY>#jDn:\%5RBSA%A%^\Ai7337!ctIUY.Lp?8N,GU=danL-Pdi>M<-,GKl[
19.68 +2,EIl?ppX#F![)5R8bU]@&pi_P`U`R[Q4@/'_"M4_`Fj1P20N952/$P7PI/Y_9%SJ+D&XkM?[3e!Cm
19.69 +/$sP3)'c+CkrQK[F@jAR2#6)<W#3:o$cLcI3C5K-B:bLI<?Z%MF`OkFNV]+kYJ>DViEg4@7uj"ZMEO
19.70 +72cn8,InjPH%T&JX]f8R)DRK)=W1=8j+PuVQ;_L,81ReT6=,c8jt::LA<beRRSjHC69A`R\HeC48_o
19.71 +8ids8BH7-=^;m%7*gRY%5H#tfPVBPF00S=o]oG,"4HQ?m[eW_Ekndu"?s5c@:uTL.eK$@J^"UtUj-=
19.72 +CfE,WiG9]!01`\P*;lo>&pdDlM=tb;6!eP[S5tTmZF[:.TKiZkZ\3:Xt4>Q`h.%sK$'^%`.#V2C:OE
19.73 +"SLfJXeXc)LDU,_.$[,[[em!lH\C"MmkdKd2``BS"l`t08O\;#4\aN)Cl<J7aB)4p!$i]_6,YQgI^u
19.74 +[Zn&\g$#q[.SP(+TlWnH:KM`Gh>n&Ao@OAjOG`HqPU$1'TfVA+E1F->TMAY#MGX8"-]21AJU=5r+DV
19.75 +.a?NA[C4B>4S8crF<h44dan*;,&XZV,$151/NQ4"./dUnIWOcu&AtnMF^WY*b^X9Y&8akV^)%5!AC'
19.76 +t?#AJ3:oFF?7Xq`9)cZX0WB]'IS]cGiK>:H,u1d,2teluH<$tp2(k;oHdIO5WMGQ's(j<%oFL=gc`i
19.77 +F:Hmc7bbW[nWKXjWQf4I>KaDV$uO4#_Sh+W`Y8BagWnM_:H7%(Tr\gAj76sr&lhoo)"g#a'u<fs3'n
19.78 +VrmSiG]bSR!o"A/Cc0)b7o@o(#02pbEr%:@iOFC9e3qp@Q2rWSA3>:jYY[=0s6$ft%qbfNO-qih#5L
19.79 +Ko+RCi2bO:8@[G8UG&qu9ua"Y%7:MG>9N&SA(`Q,'c/"j*e4IunNf27=5';Tp:2CQ8ij<9jEaX<1*^
19.80 +XgJg58INUM'33DU1W*9h9jr-(+`J`E6T!7&aK!jI&IaK5[<U==<(Tm5"kgiBD%Tci7o#1?Loe[c(#;
19.81 +gS>>XuT7Fa.f+r"H0;.WEi\BO0n6oT]0XGn8lSt4mkJrJjN@7=Ye*E:4pLlfSN`q]9J9M2`lNg;rMJ
19.82 +i=_`oQj?]nZOO!B'Gh"8PB`(432[r,%!''EKY303Hm/G,`5*TC.^Z=V6]&+1Qa'U'g,(`>:<=,UQP,
19.83 +i9.G3dN9+N9MlHZ"3@T:t,daq2WMWnD3HG3,qW4+9,!h@uJ:/aWTSY,6Nm2:":*f*eRF?%e(A5ci-N
19.84 +T'n#3p%o.En."e7tOBhJj]!aZJ%K(a?5:H4u_!b9DjHKILAUcfr>!;1/.=n6IS@g($lV!c"B&Sd)!*
19.85 +%7CNHp,:DP@mDl16g2WYU.#Q9/r0"WBZ2/C<,BM#e[55$XWaNP%[%KO9YDMt&uARSTi0Iac<dR+6<)
19.86 +7%P\P$@BVVPQ-^('#@Y[b:NBqtG*:d'4Slb2Fr2EHmUDoYm<XL]]Lc%p+Za4^QlNpt"6o(8g7UBS?"
19.87 +_oR\NGMWt,0:71Bs)$1[PdiKeAsdnYD;CrV5ist>J'<p&bL]W]*MPRYf%iQ\iEH^a^Yjdd?!ue)cp5
19.88 +`.qs:hZW8],=Oqm]D!F-U"`DK9Bp/W=ZEgnJ-I,ejGs-qeffOc7p*$./&qBtI3qggX+o#$2LM8.ZK8
19.89 +g9F:]P[#AWO:kXtc#XZ6[3d4Va_Uk8p;a$H/=XK]uUK8Wn187a9+K#-Qi+PR&H6NT@[:H16L]^^Y,f
19.90 +64T\PH*(b-!!PA204EBI)XF[WDk6MiBafrdGHVL-WBOQf>p^'/Z73QhAMi$WNX&D&EH#)77Ng2sQ?u
19.91 +;@K-aboQ749<T^!Ob-pJ3O.A%F#7$^Ht72=sDT8$!;'uV]I,@rePj+GK;L3T0o!B2,TCeH"0<^n4M-
19.92 +R5EQ`[&OEj#Y-*Pt2N.LIg!(b/l=bjq9Rf,H.`cAc"At9Gr9,i<kQiRDGAU*Jec_50:dDo<<mY3:i*
19.93 +8[Z;!8kG2]-1H?FA=sbEO+oX*6=u@*VcU5;]]nKV_L5"XJbakX97.40BB:=@-l1g!O6T(a'Ubb:$4Y
19.94 +NJLOKEW9dou'SDlttC]%;9"?L.!.XTDNOV'+Ak\?04X71O]lj(.%^I:?c/G/cIdeh:L\$\;b(:E`5L
19.95 +;NVQJ['lC3b:+5V]F5ED6RLZl].\.Xh8:Ks<,3as7W4AE:V2Z'GUB-99uVAL0f0[A2gMKn&hV?%ine
19.96 +D-B,l\6im`?$E@3)B[s;r1N_#02'?[U?TFq=2`S<X9,=POa5LeeJaJkQcr.NgfmJK<[M,'H@N&"fC(
19.97 +gm)O/N2cR72TlSb%<qp't9BWQ!SWhKk[S%,<Tf$F>%^RSp?@*W3-Mu9ngpPX2Q)%h-7O"%8;nNjO(&
19.98 +PktCf%:<sjE]sG0@mbce]O)jZ:e$kDM~>
19.99 +%%EndData
19.100 +end restore showpage
19.101 +%%Trailer
19.102 +%%EOF
20.1 Binary file img/dijkstraExT.png has changed
