lindenmannm@3
|
1 |
\documentclass[a4paper,11pt,twoside]{article}
|
lindenmannm@3
|
2 |
|
lindenmannm@3
|
3 |
\usepackage[ngerman]{babel} \usepackage[T1]{fontenc}
|
lindenmannm@3
|
4 |
\usepackage[latin1]{inputenc}
|
lindenmannm@3
|
5 |
\usepackage[colorlinks=true,linkcolor=black]{hyperref}
|
lindenmannm@3
|
6 |
|
lindenmannm@3
|
7 |
\usepackage{vaucanson-g}
|
lindenmannm@3
|
8 |
\usepackage{hyperref}
|
lindenmannm@3
|
9 |
\usepackage{hypcap}
|
lindenmannm@3
|
10 |
\usepackage{fancyhdr}
|
lindenmannm@3
|
11 |
\usepackage{graphicx}
|
lindenmannm@3
|
12 |
\usepackage{lastpage}
|
lindenmannm@3
|
13 |
\usepackage[cm]{fullpage}
|
lindenmannm@3
|
14 |
\usepackage{amsthm, amsmath, amsfonts}
|
lindenmannm@3
|
15 |
\usepackage{float}
|
lindenmannm@3
|
16 |
\usepackage{paralist}
|
lindenmannm@3
|
17 |
\usepackage{listings}
|
lindenmannm@3
|
18 |
\usepackage{color}
|
lindenmannm@3
|
19 |
\usepackage{bookmark}
|
lindenmannm@3
|
20 |
|
lindenmannm@3
|
21 |
\bibliographystyle{alphadin}
|
lindenmannm@3
|
22 |
|
lindenmannm@3
|
23 |
\title{\underline{Exzerpt Algorithmentheorie WS10/11}}
|
lindenmannm@3
|
24 |
\author{Markus Lindenmann}
|
lindenmannm@3
|
25 |
\date{\today{} }
|
lindenmannm@3
|
26 |
|
lindenmannm@3
|
27 |
\begin{document}
|
lindenmannm@3
|
28 |
\maketitle
|
lindenmannm@3
|
29 |
|
lindenmannm@3
|
30 |
\tableofcontents \newpage
|
lindenmannm@3
|
31 |
|
lindenmannm@3
|
32 |
\section{Einleitung}\label{sec:intro}
|
lindenmannm@3
|
33 |
Dozent: Matthias Westermann\\
|
lindenmannm@3
|
34 |
Website: \url{http://lak.informatik.uni-freiburg.de}\\
|
lindenmannm@3
|
35 |
Klausur: 09.03.2011\\
|
lindenmannm@3
|
36 |
Hilfsmittel: Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt
|
lindenmannm@3
|
37 |
\subsection{Themen:}
|
lindenmannm@3
|
38 |
\begin{itemize}
|
lindenmannm@3
|
39 |
\item[$\bullet$] Divide and Conquer
|
lindenmannm@3
|
40 |
\item[$\bullet$] Greedy Prinzip
|
lindenmannm@3
|
41 |
\item[$\bullet$] Dynamische Programmierung
|
lindenmannm@3
|
42 |
\item[$\bullet$] Randomisierung
|
lindenmannm@3
|
43 |
\item[$\bullet$] Amortisierte Analyse
|
lindenmannm@3
|
44 |
\end{itemize}
|
lindenmannm@3
|
45 |
\subsection{Problem-/Anwendungsbereiche:}
|
lindenmannm@3
|
46 |
\begin{itemize}
|
lindenmannm@3
|
47 |
\item[$\bullet$] Geometrische Algorithmen
|
lindenmannm@3
|
48 |
\item[$\bullet$] Algebraische Algorithmen
|
lindenmannm@3
|
49 |
\item[$\bullet$] Graphenalgorithmen
|
lindenmannm@3
|
50 |
\item[$\bullet$] Datenstrukturen
|
lindenmannm@3
|
51 |
\item[$\bullet$] Internet-Algorithmen
|
lindenmannm@3
|
52 |
\item[$\bullet$] Optimierungs-Verfahren
|
lindenmannm@3
|
53 |
\item[$\bullet$] Zeichenkettenverarbeitung
|
lindenmannm@3
|
54 |
\end{itemize}
|
lindenmannm@3
|
55 |
\subsection{Literatur:}
|
lindenmannm@3
|
56 |
\bibliography{literatur}
|
lindenmannm@3
|
57 |
\nocite{*}
|
lindenmannm@3
|
58 |
|
lindenmannm@3
|
59 |
\newpage
|
lindenmannm@3
|
60 |
\section{Divide and Conquer}\label{sec:div&conq}
|
lindenmannm@3
|
61 |
\begin{itemize}
|
lindenmannm@3
|
62 |
\item[$\bullet$] Quicksort
|
lindenmannm@3
|
63 |
\item[$\bullet$] Formulierung und Analyse des Prinzips
|
lindenmannm@3
|
64 |
\item[$\bullet$] Geometrisches Devide and Conquer
|
lindenmannm@3
|
65 |
\begin{itemize}
|
lindenmannm@3
|
66 |
\item[-] Closest-Pair
|
lindenmannm@3
|
67 |
\item[-] Segmentschnitt
|
lindenmannm@3
|
68 |
\end{itemize}
|
lindenmannm@3
|
69 |
\end{itemize}
|
lindenmannm@3
|
70 |
|
lindenmannm@3
|
71 |
\subsection{Formulierung des Divide and Conquer Prinzips}
|
lindenmannm@3
|
72 |
D\&C Verfahren zur Lösung eines Problems der Größe $n$
|
lindenmannm@3
|
73 |
\begin{itemize}
|
lindenmannm@3
|
74 |
\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
|
75 |
\item[2.] Conquer\\Löse die $k$ Teilprobleme auf dieselbe Art (rekursiv)
|
lindenmannm@3
|
76 |
\item[3.] Merge\\Füge die berechneten Teillösungen zu einer Gesamtlösung zusammen
|
lindenmannm@3
|
77 |
\end{itemize}
|
lindenmannm@3
|
78 |
|
lindenmannm@3
|
79 |
\subsection{Quicksort}\label{ch:qs}
|
lindenmannm@3
|
80 |
Wähle beliebiges Pivot Element $v$ (meist das letzte Element in der
|
lindenmannm@3
|
81 |
Input-Folge!) und sortiere alle Elemente aus der Menge, die größer sind als $v$
|
lindenmannm@3
|
82 |
rechts von $v$ ein, die anderen links. Verfahre im selben Muster mit den neuen
|
lindenmannm@3
|
83 |
Teilmengen links und rechts des Pivot Elements. Wenn die zu sortierende Folge
|
lindenmannm@3
|
84 |
$F$ nur ein Element beinhaltet, gebe $F$ zurück.
|
lindenmannm@3
|
85 |
\subsubsection{Algorithmus}
|
lindenmannm@3
|
86 |
\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus Quicksort,
|
lindenmannm@3
|
87 |
captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
|
lindenmannm@3
|
88 |
basicstyle=\footnotesize]{./code/quicksort.code}
|
lindenmannm@3
|
89 |
|
lindenmannm@3
|
90 |
\subsubsection{Analyse}
|
lindenmannm@3
|
91 |
$T(n)$ - maximale Anzahl von Schritten, um ein Problem der Größe $n$ zu lösen.
|
lindenmannm@3
|
92 |
\[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
|
93 |
Best Case: $k=2, n_1=n_2=\frac{n}{2}$\\
|
lindenmannm@3
|
94 |
Divide- und Mergeaufwand: $DM(n)$\\
|
lindenmannm@3
|
95 |
$T(1)=a$\\
|
lindenmannm@3
|
96 |
$T(n)=2T(\frac{n}{2})+DM(n)$
|
lindenmannm@3
|
97 |
|
lindenmannm@3
|
98 |
\subsection{Nächste Paare}
|
lindenmannm@3
|
99 |
Eingabe: $n$ Punkte in Ebene\\
|
lindenmannm@3
|
100 |
Ausgabe: Punkt-Paar $q,r$ mit geringstem Abstand\\
|
lindenmannm@3
|
101 |
Abstand: $d(q,r)$ bechreibt Abstand zwischen Punkten $q$ und $r$
|
lindenmannm@3
|
102 |
\subsubsection{Algorithmus}
|
lindenmannm@3
|
103 |
\begin{itemize}
|
lindenmannm@3
|
104 |
\item[$\bullet$] sortiere Punktmenge nach x-Koordinate
|
lindenmannm@3
|
105 |
\item[$\bullet$] Teile Punktmenge in der Mitte L in die Mengen Q und R
|
lindenmannm@3
|
106 |
\item[$\bullet$] Löse rekursiv auf Q und R
|
lindenmannm@3
|
107 |
\item[$\bullet$] Sortiere Punkte nach y-Koordinate
|
lindenmannm@3
|
108 |
\item[$\bullet$] Teste alle Paare, deren Abstand in der
|
lindenmannm@3
|
109 |
Sortierung kleiner als 16 ist (siehe unten)
|
lindenmannm@3
|
110 |
\item[$\bullet$] Füge zusammen
|
lindenmannm@3
|
111 |
\end{itemize}
|
lindenmannm@3
|
112 |
|
lindenmannm@3
|
113 |
$\delta=$ Minimum der Teillösungen\\
|
lindenmannm@3
|
114 |
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
|
115 |
\textbf{Problem:} alle Punkte können innerhalb der $\delta$-Zone liegen\\
|
lindenmannm@3
|
116 |
\textbf{Lösung:}\begin{itemize}
|
lindenmannm@3
|
117 |
\item[$\bullet$] Sortiere Punkte in $\delta$ Zone nach $y$-Abstand
|
lindenmannm@3
|
118 |
\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
|
119 |
\end{itemize}
|
lindenmannm@3
|
120 |
|
lindenmannm@3
|
121 |
Dies kann für $c=15$ bewiesen werden (vgl. Abbildung \ref{cl_pair}):
|
lindenmannm@3
|
122 |
\begin{itemize}
|
lindenmannm@3
|
123 |
\item[$\bullet$] Seien min. 15 Punkte zwischen $q$ und $r$
|
lindenmannm@3
|
124 |
\item[$\bullet$] Dann sind mindestens 3 Reihen Quadrate zwischen $q,r$, weil in jedem Quadrat höchstens ein Punkt ist.
|
lindenmannm@3
|
125 |
\item[$\rightarrow$] Dann muss $d(q,r)$ mindestens $\frac{3}{2}\delta > \delta$ sein.
|
lindenmannm@3
|
126 |
\end{itemize}
|
lindenmannm@3
|
127 |
|
lindenmannm@3
|
128 |
\begin{figure}[H]
|
lindenmannm@3
|
129 |
\centering
|
lindenmannm@3
|
130 |
\includegraphics[scale=0.5]{img/cl_pair}
|
lindenmannm@3
|
131 |
\caption{Nächste Paare: Prüf Distanz}
|
lindenmannm@3
|
132 |
\label{cl_pair}
|
lindenmannm@3
|
133 |
\end{figure}
|
lindenmannm@3
|
134 |
|
lindenmannm@3
|
135 |
\subsubsection{Analyse}
|
lindenmannm@3
|
136 |
\[T(n)=\begin{cases}n\leq3&a \\ n>3&2T(\frac{n}{2})+an\end{cases}\]
|
lindenmannm@3
|
137 |
\[T(n)\leq an \log n \]
|
lindenmannm@3
|
138 |
|
lindenmannm@3
|
139 |
\subsection{Segmentschnitt}
|
lindenmannm@3
|
140 |
Eingabe: Menge S bestehend aus vertikalen Segmenten und Endpunkten vn horizontalen Segmenten\\
|
lindenmannm@3
|
141 |
Ausgabe: Alle Schnittpunkte von vertikalen Segmenten mit horizontalen Segmenten, von denen mindesens ein Endpunkt in S ist
|
lindenmannm@3
|
142 |
|
lindenmannm@3
|
143 |
\subsubsection{Algorithmus}
|
lindenmannm@3
|
144 |
\textbf{Divide \& Conquer:}\\Fallunterscheidung
|
lindenmannm@3
|
145 |
\begin{itemize}
|
lindenmannm@3
|
146 |
\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
|
147 |
\item[2.] else: S enthält keine Schnitte
|
lindenmannm@3
|
148 |
\end{itemize}
|
lindenmannm@3
|
149 |
|
lindenmannm@3
|
150 |
\textbf{Merge}\\
|
lindenmannm@3
|
151 |
Bilde L(S), R(S) und V(S) (Definition am Beispiel $i=1,2$ berechnet: $S=S_1\cup S_2$):
|
lindenmannm@3
|
152 |
\begin{itemize}
|
lindenmannm@3
|
153 |
\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
|
154 |
\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
|
155 |
\item[$\bullet$] V(S): y-Intervalle der vertikalen Segmente in S\\$=V(S_1)\cup V(S_2)$
|
lindenmannm@3
|
156 |
\end{itemize}
|
lindenmannm@3
|
157 |
L,R sortiert nach steigender y-Koordinate\\
|
lindenmannm@3
|
158 |
V sortiert nach steigendem unteren Endpunkt\\
|
lindenmannm@3
|
159 |
\medskip
|
lindenmannm@3
|
160 |
|
lindenmannm@3
|
161 |
\textbf{Basisfälle}\\
|
lindenmannm@3
|
162 |
S enthält nur ein Element s. Fallunterscheidung:
|
lindenmannm@3
|
163 |
\begin{itemize}
|
lindenmannm@3
|
164 |
\item[1.] $s=(x,y)$ ist ein linker Endpunkt:\\$L(S)=\{y\},\qquad R(S)=\emptyset,\qquad V(S)=\emptyset$
|
lindenmannm@3
|
165 |
\item[2.] $s=(x,y)$ ist ein rechter Endpunkt:\\$L(S)=\emptyset,\qquad R(S)=\{y\},\qquad V(S)=\emptyset$
|
lindenmannm@3
|
166 |
\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
|
167 |
\end{itemize}
|
lindenmannm@3
|
168 |
|
lindenmannm@3
|
169 |
\subsubsection{Analyse}
|
lindenmannm@3
|
170 |
Eingabe wird Anfangs sortiert und in Array gespeichert
|
lindenmannm@3
|
171 |
\[T(n)=2T(\frac{n}{2}+an+\text{Größe der Ausgabe}\]
|
lindenmannm@3
|
172 |
\[T(1)=O(1)\]
|
lindenmannm@3
|
173 |
\[O(n \log n + k \mid k=\#Schnittpunkte\]
|
lindenmannm@3
|
174 |
|
lindenmannm@3
|
175 |
\subsection{Polynomprodukt und Fast Fourier-Transformation (TODO)}
|
lindenmannm@3
|
176 |
%TODO
|
lindenmannm@3
|
177 |
|
lindenmannm@3
|
178 |
\newpage
|
lindenmannm@3
|
179 |
\section{Randomisierung}
|
lindenmannm@3
|
180 |
\begin{itemize}
|
lindenmannm@3
|
181 |
\item Klassen von randomisierten Algorithmen
|
lindenmannm@3
|
182 |
\begin{itemize}
|
lindenmannm@3
|
183 |
\item \textbf{Las Vegas}: \underline{immer} Korrekt, erwartete Laufzeit
|
lindenmannm@3
|
184 |
(randomisierter Qicksort)
|
lindenmannm@3
|
185 |
\item \textbf{Monte Carlo}: \underline{wahrscheinlich} (MC:mostly correct)
|
lindenmannm@3
|
186 |
Korrekt, garantierte Laufzeit (randomisierter Primzahltest)
|
lindenmannm@3
|
187 |
\end{itemize}
|
lindenmannm@3
|
188 |
\item Randomisierter Quicksort
|
lindenmannm@3
|
189 |
\item Randomisierter Primzahltest
|
lindenmannm@3
|
190 |
\item Kryptographie
|
lindenmannm@3
|
191 |
\end{itemize}
|
lindenmannm@3
|
192 |
\subsection{Randomisierter Quicksort}
|
lindenmannm@3
|
193 |
Refer to \ref{ch:qs} for basic description of the algorithm.\\
|
lindenmannm@3
|
194 |
Problem von Quicksort: bisher nimmt Quicksort immer das letzte Element in der
|
lindenmannm@3
|
195 |
Folge $\implies$ Worst-Case: sortierte Folge als Eingabe ($\Theta(n^2)$).
|
lindenmannm@3
|
196 |
Ziel: keine quadratische Laufzeit.\\
|
lindenmannm@3
|
197 |
Lösung: randomisierte Auswahl des Pivotelements an Stelle $i$. Anschließend
|
lindenmannm@3
|
198 |
tauschen von Position $i$ und $r$ (mit $r$=rechte Grenze des zu sortierenden
|
lindenmannm@3
|
199 |
Segments).
|
lindenmannm@3
|
200 |
\subsubsection{Analyse}
|
lindenmannm@3
|
201 |
\textbf{Analyse 1: erwartete Laufzeit}\\
|
lindenmannm@3
|
202 |
Mit Wahrscheinlichkeit $\frac{1}{n}$ wird das $i$-kleinste Element $S_i$
|
lindenmannm@3
|
203 |
gewählt wobei $n$ zu sortierenden Elemente vorhanden sind. Abhängig von der
|
lindenmannm@3
|
204 |
Wahl von $S_i$ ergeben sich Teilprobleme der Größe $i-1$ und $n-i$. Damit
|
lindenmannm@3
|
205 |
ergibt sich für die Laufzeit $T(n)$.
|
lindenmannm@3
|
206 |
\[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
|
207 |
\[\frac{1}{n}(T(n-1)+T(0))+\Theta(n))\mid
|
lindenmannm@3
|
208 |
\Theta(n)\text{ für partition}\]
|
lindenmannm@3
|
209 |
\[=\frac{1}{n}\sum_{k=1}^n(T(k-1)+T(n-k))+\Theta(n)\]
|
lindenmannm@3
|
210 |
\[\frac{2}{n}\sum_{k=1}^nT(k-1)+\Theta(n)\]
|
lindenmannm@3
|
211 |
\[=O(n \log n)\]
|
lindenmannm@3
|
212 |
\textbf{Analys 2: Erwartete Anzahl der Vergleiche}\\
|
lindenmannm@3
|
213 |
$x_{ij}=
|
lindenmannm@3
|
214 |
\begin{cases}
|
lindenmannm@3
|
215 |
1&\text{falls }S_i\text{ mit }S_j\text{ verglichen wird}\\
|
lindenmannm@3
|
216 |
0&\text{sonst}
|
lindenmannm@3
|
217 |
\end{cases}$
|
lindenmannm@3
|
218 |
\[E\left[\sum_{i=1}^n\sum_{j>1}x_{ij}\right]=\sum_{i=1}^n\sum_{j>1}E[x_{ij}]\]
|
lindenmannm@3
|
219 |
$p_{ij} =$ Wahrscheinlichkeit $S_i$ wird mit $S_j$ verglichen
|
lindenmannm@3
|
220 |
\[E[x_{ij}=1\cdot p_{ij}+0\cdot(1-p_{ij}=p_{ij}\]
|
lindenmannm@3
|
221 |
\subsection{Randomisierter Primzahltest (TODO)}
|
lindenmannm@3
|
222 |
%TODO schnelle exponentiation
|
lindenmannm@3
|
223 |
\subsection{RSA (TODO)}
|
lindenmannm@3
|
224 |
%TODO
|
lindenmannm@3
|
225 |
%erw. Euklid
|
lindenmannm@3
|
226 |
\subsection{Treaps (TODO)}
|
lindenmannm@3
|
227 |
%TODO haben wir nicht so im detail gemacht wie Elsässer!
|
lindenmannm@3
|
228 |
\subsection{Hashing (TODO)}
|
lindenmannm@3
|
229 |
%TODO
|
lindenmannm@3
|
230 |
|
lindenmannm@3
|
231 |
\newpage
|
lindenmannm@3
|
232 |
\section{Amortisierte Analyse (TODO)}
|
lindenmannm@3
|
233 |
%TODO
|
lindenmannm@3
|
234 |
\subsection{Binomial Heaps (TODO)}
|
lindenmannm@3
|
235 |
%TODO
|
lindenmannm@3
|
236 |
\subsection{Fibonacci Heaps (TODO)}
|
lindenmannm@3
|
237 |
%TODO
|
lindenmannm@3
|
238 |
\subsection{Union Find (TODO)}
|
lindenmannm@3
|
239 |
%TODO
|
lindenmannm@3
|
240 |
|
lindenmannm@3
|
241 |
\newpage
|
lindenmannm@3
|
242 |
\section{Greedy}
|
lindenmannm@3
|
243 |
Momentan beste Teillösung wählen. Die Summe dieser optimalen Teillösung ergibt
|
lindenmannm@3
|
244 |
die gesamt Lösung. Möglicher Zustand der Gesamtlösung:
|
lindenmannm@3
|
245 |
\begin{itemize}
|
lindenmannm@3
|
246 |
\item Wir erhalten die optimale Gesamtlösung.
|
lindenmannm@3
|
247 |
\item Wir erhalten eine Lösung, die zwar nicht immer optimal ist, aber vom
|
lindenmannm@3
|
248 |
Optimum stets nur wenig abweicht.
|
lindenmannm@3
|
249 |
\item Die berechnete Lösung kann beliebig schlecht werden.
|
lindenmannm@3
|
250 |
\end{itemize}
|
lindenmannm@3
|
251 |
\underline{Beispiele:}
|
lindenmannm@3
|
252 |
\begin{itemize}
|
lindenmannm@3
|
253 |
\item Münzwechselproblem\\\textbf{Ziel:} Bezahlung eines Betrages in möglichst
|
lindenmannm@3
|
254 |
wenig Münzen und Banknoten.\\\textbf{Lösung (Greedy):} Wähle die maximale
|
lindenmannm@3
|
255 |
Anzahl von Banknoten und Münzen mit jeweils größtmöglichem Wert, bis der
|
lindenmannm@3
|
256 |
gewünschte Betrag erreicht ist. (Dies führt nur für bestimmte Werte der
|
lindenmannm@3
|
257 |
Zahlungsmittel zur optimalen Gesamtlösung!)
|
lindenmannm@3
|
258 |
\item Handlungsreisenden-Problem (Traveling Sales Man Problem,
|
lindenmannm@3
|
259 |
TSP)\\\textbf{Ziel:} Finden der billigsten Rundreise, diealle Orte genau
|
lindenmannm@3
|
260 |
einmal besucht.\\\textbf{Lösung (Greedy):} Gehe immer den günstigsten Weg vom
|
lindenmannm@3
|
261 |
aktuellen Knoten zu einem noch nicht besuchten Knoten. Wenn alle besucht
|
lindenmannm@3
|
262 |
wurden, kehre zum Anfang zurück. (Mit Greedy keine optimale Gesamtlösung!)
|
lindenmannm@3
|
263 |
\item Aktivitäten Auswahlproblem\\\textbf{Ziel:} möglichst viele Anfragen
|
lindenmannm@3
|
264 |
erfüllen. (Muss nicht bedeuten, dass die Ressource optimal
|
lindenmannm@3
|
265 |
genutzt wird!)\\\textbf{Lösung (Greedy):} Nimm die Anfrage, die am frühesten
|
lindenmannm@3
|
266 |
fertig ist. (optimale Gesamtlösung!)\\\textbf{Analyse:} $\Theta(n)$
|
lindenmannm@3
|
267 |
\end{itemize}
|
lindenmannm@3
|
268 |
|
lindenmannm@3
|
269 |
\subsection{Kürzeste (billigste) Wege}
|
lindenmannm@3
|
270 |
Pfad $P=$ Folge von Knoten.
|
lindenmannm@3
|
271 |
Kosten eines Pfades:\[c(P)=\sum_{i=0}^{P.length-1}c(v_i,v_{i+1}\]
|
lindenmannm@3
|
272 |
Entfernung von $v$ nach $w$ sind die Kosten des
|
lindenmannm@3
|
273 |
günstigsten Pfades:\[dist(v,w)=inf{c(P)\mid P\text{= Weg von v nach
|
lindenmannm@3
|
274 |
w}}\]
|
lindenmannm@3
|
275 |
Kosten eines unerreichbaren Knoten sind definiert als $\infty$. Kosten eines
|
lindenmannm@3
|
276 |
Pfades in einem negativen Zyklus: $-\infty$. Es können also nur Graphen ohne
|
lindenmannm@3
|
277 |
negative Zyklen sinnvoll betrachtet werden!
|
lindenmannm@3
|
278 |
\subsubsection{Single Source Shortest Paths}
|
lindenmannm@3
|
279 |
Kürzeste/Günstigste Pfade von einem Knoten $s$ zu allen anderen Knoten. Hierfür
|
lindenmannm@3
|
280 |
nutzt man die Dreiecksungleichung über $dist(u,v)\mid (u,v)\in E$ und $s\in V$:
|
lindenmannm@3
|
281 |
\[dist(s,v)\leq dist(s,u)+dist(u,v)\]
|
lindenmannm@3
|
282 |
\textbf{Greedy-Ansatz}
|
lindenmannm@3
|
283 |
\begin{itemize}
|
lindenmannm@3
|
284 |
\item Überschätze die dist-Funktion \[dist(s,v)=\begin{cases}0&\text{ falls }
|
lindenmannm@3
|
285 |
v=s\\\infty&\text{ falls }v\neq s\end{cases}\]
|
lindenmannm@3
|
286 |
\item Solange eine Kante $e=(u,v)$ existiert mit
|
lindenmannm@3
|
287 |
$dist(s,v)>dist(s,u)+c(u,v)$ setze $dist(s,v)=dist(s,u)+c(u,v)$
|
lindenmannm@3
|
288 |
\end{itemize}
|
lindenmannm@3
|
289 |
Durch die Überschätzung kann die Dreicksungleichung nur noch für Knoten $s$ und
|
lindenmannm@3
|
290 |
seine direkten Nachfolger verletzt werden!\\Alle folgenden Verfahren basieren
|
lindenmannm@3
|
291 |
auf diesem Prinzip!\\
|
lindenmannm@3
|
292 |
%Elsässer führt einige Lemmas ein und beweist sie - diese beziehen sich auf den
|
lindenmannm@3
|
293 |
% ersten optimimierten Algorithmus und diesen erachte ich in Relation zu
|
lindenmannm@3
|
294 |
% Dijkstra als irrelevant!
|
lindenmannm@3
|
295 |
\textbf{Effiziente Implementierungen}
|
lindenmannm@3
|
296 |
Diese sind im Allgemeinen nicht bekannt, jedoch für wichtige Spezialfälle.
|
lindenmannm@3
|
297 |
\begin{itemize}
|
lindenmannm@3
|
298 |
\item Nicht-negative Netzwerke: \underline{Dijkstra}
|
lindenmannm@3
|
299 |
\item Netzwerke ohne negative Zyklen: \underline{Bellman-Ford}
|
lindenmannm@3
|
300 |
\item Azyklische Netzwerke
|
lindenmannm@3
|
301 |
\end{itemize}
|
lindenmannm@3
|
302 |
\underline{Dijkstra}
|
lindenmannm@3
|
303 |
\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
|
lindenmannm@3
|
304 |
Dijkstra, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
|
lindenmannm@3
|
305 |
basicstyle=\footnotesize]{./code/dijkstra.code}
|
lindenmannm@3
|
306 |
Dijkstra Beispiel:
|
lindenmannm@3
|
307 |
\begin{figure}
|
lindenmannm@3
|
308 |
\centering
|
lindenmannm@3
|
309 |
\includegraphics[scale=0.6]{img/dijkstraExT}
|
lindenmannm@3
|
310 |
\caption{Tree for Dijkstra Example}
|
lindenmannm@3
|
311 |
\label{fig:dijExT}
|
lindenmannm@3
|
312 |
\end{figure}
|
lindenmannm@3
|
313 |
\begin{table}[ht]
|
lindenmannm@3
|
314 |
\centering
|
lindenmannm@3
|
315 |
\begin{tabular}{|c c c c c c c|c|}
|
lindenmannm@3
|
316 |
\hline
|
lindenmannm@3
|
317 |
\multicolumn{7}{|c|}{DIST[v]} & \\
|
lindenmannm@3
|
318 |
\hline
|
lindenmannm@3
|
319 |
s & a & b & c & d & e & f & U\\\hline\hline
|
lindenmannm@3
|
320 |
0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & s,a,b,c,d,e,f\\
|
lindenmannm@3
|
321 |
0* & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & a,b,c,d,e,f\\
|
lindenmannm@3
|
322 |
0* & 6 & 7 & 5* & $\infty$ & $\infty$ & $\infty$ & a,b,d,e,f\\
|
lindenmannm@3
|
323 |
0* & 6* & 7 & 5* & $\infty$ & $\infty$ & 14 & b,d,e,f\\
|
lindenmannm@3
|
324 |
0* & 6* & 7* & 5* & 9 & 10 & 14 & d,e,f\\
|
lindenmannm@3
|
325 |
0* & 6* & 7* & 5* & 9* & 10 & 11 & e,f\\
|
lindenmannm@3
|
326 |
0* & 6* & 7* & 5* & 9* & 10* & 11 & f\\
|
lindenmannm@3
|
327 |
0* & 6* & 7* & 5* & 9* & 10* & 11* & $\emptyset$\\\hline
|
lindenmannm@3
|
328 |
\end{tabular}
|
lindenmannm@3
|
329 |
\caption{Dijkstra Example}\label{tab:dijEx}
|
lindenmannm@3
|
330 |
\end{table}
|
lindenmannm@3
|
331 |
Komplexität:
|
lindenmannm@3
|
332 |
\[O(n\cdot(T_{insert}+T_{Empty}+T_{DeleteMin})+m\cdot T_{DecreaseKey}+m+n)\]
|
lindenmannm@3
|
333 |
Implementierung mit Fibonaci-Heaps:\\
|
lindenmannm@3
|
334 |
$T_{Insert}:O(1)$\\
|
lindenmannm@3
|
335 |
$T_{DeleteMin}:O(\log n)$ (amortisiert)\\
|
lindenmannm@3
|
336 |
$T_{DecreaseKey}:O(1)$ (amortisiert)
|
lindenmannm@3
|
337 |
\[O(n\log n+m)\]
|
lindenmannm@3
|
338 |
\underline{Bellman-Ford}
|
lindenmannm@3
|
339 |
\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
|
lindenmannm@3
|
340 |
Belman-Ford, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
|
lindenmannm@3
|
341 |
basicstyle=\footnotesize]{./code/BelmanFord.code}
|
lindenmannm@3
|
342 |
\underline{Azyklische Netzwerke}
|
lindenmannm@3
|
343 |
\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus für
|
lindenmannm@3
|
344 |
Azyklische Netzwerke, captionpos=b, numbers=left, numberstyle=\tiny,
|
lindenmannm@3
|
345 |
numbersep=5pt, basicstyle=\footnotesize]{./code/AzyklischeNetzwerke.code}
|
lindenmannm@3
|
346 |
\subsection{Spannbäume minimalen Gewichts}
|
lindenmannm@3
|
347 |
Ungerichteter Graph $G=(V,E)$, Kostenfunktion $c:E\rightarrow R$.\\Sei
|
lindenmannm@3
|
348 |
$T\subseteq E$ ein Baum (zusammenhängender azyklischer Teilgraph) Kosten von T:
|
lindenmannm@3
|
349 |
$c(T)=\sum_{(u,v)\in T}c(u,v)$.\\Ein minimaler Spannbaum ist ein Baum
|
lindenmannm@3
|
350 |
$T\subseteq E$, der alle Knoten in $V$ verbindet minimale Kosten hat.
|
lindenmannm@3
|
351 |
\subsubsection{Das Wachsen von min. Spannbäumen}
|
lindenmannm@3
|
352 |
\textbf{Invariante:} Verwalte Menge $A\subseteq E$, die Teilmenge eines
|
lindenmannm@3
|
353 |
minimalen Spannbaums ist.\\
|
lindenmannm@3
|
354 |
\textbf{Definition:} Eine Kante $(u,v)\in E\backslash A$ ist sicher für $A$, wenn
|
lindenmannm@3
|
355 |
$A\cup {(u,v)}$ Teilmenge eines minimalen Spannbaums ist.
|
lindenmannm@3
|
356 |
\lstinputlisting[language=Java,label=lst:TTlookup,caption=Greedy Algorithmus für
|
lindenmannm@3
|
357 |
Spannbäume, captionpos=b, numbers=left, numberstyle=\tiny,
|
lindenmannm@3
|
358 |
numbersep=5pt, basicstyle=\footnotesize]{./code/spannbaeumeGreedy.code}
|
lindenmannm@3
|
359 |
\subsubsection{Schnitte}
|
lindenmannm@3
|
360 |
Ein Schnitt $(S,V\backslash S)$ ist eine Partition von $V$. Eine Kante $(u,v)$
|
lindenmannm@3
|
361 |
schneidet $(S,V\backslash S)$, wenn ein Endpunkt in $S$ und der andere in
|
lindenmannm@3
|
362 |
$V\backslash S$ liegt.\\Ein Schnitt "`respektiert $A$"', wenn keine Kante aus
|
lindenmannm@3
|
363 |
$A$ den Schnitt schneidet.\\Eine Kante heißt minimal bzgl. eines Schnitts, wenn
|
lindenmannm@3
|
364 |
sie den Schnitt schneidet und unter allen solchen Kanten minimale Kosten hat.
|
lindenmannm@3
|
365 |
\subsubsection{Sichere Kanten}
|
lindenmannm@3
|
366 |
\textbf{Satz:} Sei $A$ Teilmenge eines minimalen Spannbaums $T$ und
|
lindenmannm@3
|
367 |
$(S,V\backslash S)$ ein Schnitt, der $A$ respektiert. Ist $(u,v)$ eine minimale
|
lindenmannm@3
|
368 |
Kante bzgl. $(S,V\S)$, dann ist $(u,v)$ sicher für $A$.\\
|
lindenmannm@3
|
369 |
\textbf{Beweis}: \begin{itemize}
|
lindenmannm@3
|
370 |
\item[1. Fall] $(u,v)\in T$ : ok
|
lindenmannm@3
|
371 |
\item[2. Fall] $(u,v)\not\in T$ : Wir konstruieren minimalen Spannbaum $T'$
|
lindenmannm@3
|
372 |
mit $(u,v)\in T'$ und $A\subseteq T'$.
|
lindenmannm@3
|
373 |
\end{itemize}
|
lindenmannm@3
|
374 |
\subsubsection{Der Graph $G_A$}
|
lindenmannm@3
|
375 |
\[G_A=(V,A)\]
|
lindenmannm@3
|
376 |
\begin{itemize}
|
lindenmannm@3
|
377 |
\item ist ein \underline{Wald}, d.h. eine Menge von Bäumen
|
lindenmannm@3
|
378 |
\item anfangs, wenn $A=\emptyset$, ist jeder Baum ein einzelner Knoten
|
lindenmannm@3
|
379 |
\item eine sichere Kante verbindet verschiedene Bäume
|
lindenmannm@3
|
380 |
\end{itemize}
|
lindenmannm@3
|
381 |
\textbf{Korollar:} Sei $B$ ein Baum in $G_A=(V,A)$. Ist $(u,v)$ eine Kante
|
lindenmannm@3
|
382 |
minimaler Kosten, die $B$ und einen anderen Baum in $G_A$ verbindet, dann ist
|
lindenmannm@3
|
383 |
$(u,v)$ sicher für A.
|
lindenmannm@3
|
384 |
\subsubsection{Algorithmus von Kruskal}
|
lindenmannm@3
|
385 |
Wähle stets eine Kante minimaler Kosten, die zwei Bäume $B_1$ und $B_2$ in $G_A$
|
lindenmannm@3
|
386 |
verbindet.
|
lindenmannm@3
|
387 |
\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
|
lindenmannm@3
|
388 |
Kruskal, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
|
lindenmannm@3
|
389 |
basicstyle=\footnotesize]{./code/spannbaeumeKruskal.code}
|
lindenmannm@3
|
390 |
Laufzeit: $O(m\alpha(n)+m+m\log n)$
|
lindenmannm@3
|
391 |
\subsubsection{Algorithmus von Prim}
|
lindenmannm@3
|
392 |
$A$ ist immer ein einziger Baum. Starte mit einem beliebigen Wurzelknoten $w$.
|
lindenmannm@3
|
393 |
Füge in jedem Schritt eine minimale Kante hinzu, die einen Knoten in $A$ mit
|
lindenmannm@3
|
394 |
einem Knoten in $V\backslash A$ verbindet.
|
lindenmannm@3
|
395 |
\textbf{Implementierung}\\$Q$: Prioritätenwarteschlange, die alle Knoten $v\in
|
lindenmannm@3
|
396 |
V\backslash A$ enthält.\\Schlüssel von $v$: minimale Kosten einer Kante, die $v$
|
lindenmannm@3
|
397 |
mit einem Knoten aus $A$ verbindet.\\Für einen Knoten $v$ ist $p[v]$ der
|
lindenmannm@3
|
398 |
Elter-Knoten von $v$ in dem Baum.\[A={(v,p[v]):v\in V-{w}-Q}\]
|
lindenmannm@3
|
399 |
\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus von
|
lindenmannm@3
|
400 |
Prim, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
|
lindenmannm@3
|
401 |
basicstyle=\footnotesize]{./code/spannbaeumePrim.code}
|
lindenmannm@3
|
402 |
Laufzeit: $O(n\log n+m)$
|
lindenmannm@3
|
403 |
|
lindenmannm@3
|
404 |
\newpage
|
lindenmannm@3
|
405 |
\section{Bin Packing}
|
lindenmannm@3
|
406 |
\textbf{Problembeschreibung:}\\
|
lindenmannm@3
|
407 |
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
|
408 |
\subsection{Online Verfahren}
|
lindenmannm@3
|
409 |
Jedes (ankommende) Objekt muss verpackt sein, bevor das nächste
|
lindenmannm@3
|
410 |
Objekt betrachtet wird. Ein Objekt verbleibt in derjenigen Kiste,
|
lindenmannm@3
|
411 |
in die es zuerst gepackt wird.\\ Kein Online Bin Packing Verfahren
|
lindenmannm@3
|
412 |
kann stets eine optimale Lösung finden!\\ \textbf{Satz 1}: Es gibt
|
lindenmannm@3
|
413 |
Eingaben, die jeden Online Bin Packing Algorithmus zwingen,
|
lindenmannm@3
|
414 |
wenigstens $\frac{4}{3} OPT$ Bins zu verwenden, wobei $OPT$ die
|
lindenmannm@3
|
415 |
minimal mögliche Binzahl ist.\\ \textbf{Beweis} Annahme: Online Bin
|
lindenmannm@3
|
416 |
Packing Algorithmus benötigt stets weniger als $\frac{4}{3}OPT$
|
lindenmannm@3
|
417 |
Bins.\\ Es wird eine Eingabe mit $2m$ Objekten angenommen. Die
|
lindenmannm@3
|
418 |
ersten $m$ sind um $\epsilon$ kleiner als $\frac{1}{2}$, die
|
lindenmannm@3
|
419 |
zweiten $m$ um $\epsilon$ größer. Die optimale Lösung sind $m$
|
lindenmannm@3
|
420 |
Kisten, da immer ein großes mit einem kleinen Paket kombiniert
|
lindenmannm@3
|
421 |
werden kann. Nun teilt man die Analyse in zwei Zeitpunkte: nach $m$
|
lindenmannm@3
|
422 |
Objekten und nach $2m$ Objekten. Laut Annahme gilt nach nach $m$
|
lindenmannm@3
|
423 |
Objekten, dass die Anzahl der Bins $b$ nur maximal $\frac{4}{3}
|
lindenmannm@3
|
424 |
OPT$ groß sein darf. Mit $OPT=\frac{m}{2}$ gilt somit:
|
lindenmannm@3
|
425 |
$b=\frac{4}{3}\cdot\frac{m}{2}=\frac{2}{3}m$. Sei $b=b_1+b_2\mid
|
lindenmannm@3
|
426 |
b_1=\#$Bins mit einem Objekt, $b_2=\#$Bins mit zwei Objekten, so
|
lindenmannm@3
|
427 |
folgt $b_1+2b_2=m\implies b_1=m-2b_2\implies b=b_1+b_2=m-b_2$. Nach
|
lindenmannm@3
|
428 |
$2m$ Objekten ist $OPT=m$, wie zuvor beschrieben. $b_1$ Bins können
|
lindenmannm@3
|
429 |
zu diesem Zeitpunkt mit Objekten des zweiten Bereichs gefüllt
|
lindenmannm@3
|
430 |
werden, für die verbleibenden muss man neue Bins öffnen. Die Anzahl
|
lindenmannm@3
|
431 |
der neu zu öffnenden beträgt damit genau $b_2\implies \#$Bins $\geq
|
lindenmannm@3
|
432 |
b+m-b_1=m+b_2$. Die Annahme besagt $m+b_2\leq\#$Bins $<\frac{4}{3}m
|
lindenmannm@3
|
433 |
\wedge b_2<\frac{m}{3}$. Dies ist nur möglich, wenn
|
lindenmannm@3
|
434 |
$b=m-b_2>\frac{2}{3}m$ - Dies führt zu einem
|
lindenmannm@3
|
435 |
\underline{Widerspruch}, da $b$ zum Zeitpunkt 1, nach $m$ Objekten
|
lindenmannm@3
|
436 |
$<\frac{2}{3}m$ sein muss.
|
lindenmannm@3
|
437 |
|
lindenmannm@3
|
438 |
\subsubsection{Next Fit (NF)}
|
lindenmannm@3
|
439 |
Verpacke das nächste Objekt in dieselbe Kiste wie das
|
lindenmannm@3
|
440 |
vorherige, wenn es dort noch hineinpasst, sonst öffne eine neue
|
lindenmannm@3
|
441 |
Kiste und verpacke es dort.\\ \textbf{Satz 2}: (a) Für alle
|
lindenmannm@3
|
442 |
Inputfolgen $I$ gilt: $NF(I)\leq2OPT(I)$. (b) Es gibt
|
lindenmannm@3
|
443 |
Inputfolgen I mit $NF(I)\geq2OPT(I)-2$.\\ \textbf{Beweis}\\ (a)
|
lindenmannm@3
|
444 |
Betrachte zwei beliebige aufeinanderfolgende Kisten $B_{2k-1},
|
lindenmannm@3
|
445 |
B_{2k}$. Man weiß, dass die beinhalteten Objekte eine
|
lindenmannm@3
|
446 |
Summengröße $>1$ haben, sonst wären selbige in einer Kiste.
|
lindenmannm@3
|
447 |
Daraus folgt, man kann nicht mehr als die doppelte Anzahl an
|
lindenmannm@3
|
448 |
Kisten als beim Optimum erreichen!\\ (b) Inputfolge: $0.5,
|
lindenmannm@3
|
449 |
\frac{2}{n}, 0.5, \frac{2}{n}, 0.5, \frac{2}{n}, \ldots 0.5,
|
lindenmannm@3
|
450 |
\frac{2}{n}$.\\Next-Fit liefert nun immer Bins gefüllt mit $0.5
|
lindenmannm@3
|
451 |
+ \frac{2}{n}$. Darausfolgt $NF(I)=\frac{n}{2}$ und
|
lindenmannm@3
|
452 |
$OPT=\frac{n}{4}+1$ (weil $\frac{n}{2}$ mal 0.5er Objekte in
|
lindenmannm@3
|
453 |
$=\frac{n}{4}$ Kisten passen und $\frac{n}{2}$ $\frac{2}{n}$er
|
lindenmannm@3
|
454 |
Objekte in eine Kiste passen)\\ Laufzeit für Inputfolgen der
|
lindenmannm@3
|
455 |
Länge $n$: NF $O(n)$
|
lindenmannm@3
|
456 |
\subsubsection{First-Fit (FF)}
|
lindenmannm@3
|
457 |
Packe nächstes Objekt in die erste Kiste, in die es noch
|
lindenmannm@3
|
458 |
hineinpasst, wenn es eine solche Kiste gibt, sonst in eine neue
|
lindenmannm@3
|
459 |
Kiste.\\ \textbf{Beobachtung}: Zu jedem Zeitpunkt kann es
|
lindenmannm@3
|
460 |
höchstens eine Kiste geben, die weniger als halb voll ist.
|
lindenmannm@3
|
461 |
($\implies FF(I) \leq 2OPT(I)$)\\ \textbf{Satz 3}: (a) Für alle
|
lindenmannm@3
|
462 |
Inputfolgen $I$ gilt $FF(I)\leq \lceil\frac{17}{10}
|
lindenmannm@3
|
463 |
OPT(I)\rceil$. (b) Es gibt Inputfolgen $I$ mit
|
lindenmannm@3
|
464 |
$FF(I)\geq\frac{17}{10}(OPT(I)-1)$. (b') Es gibt Inputfolgen
|
lindenmannm@3
|
465 |
$I$ mit $FF(I)=\frac{10}{6}OPT(I)$.\\ \textbf{Beweis}\\ (b')
|
lindenmannm@3
|
466 |
Inputfolge der Länge $3\cdot6m$. Dabei je $6m$ Objekte der
|
lindenmannm@3
|
467 |
Größen $\frac{1}{7}+\epsilon, \frac{1}{3}+\epsilon,
|
lindenmannm@3
|
468 |
\frac{1}{2}+\epsilon$, welche in gegebener Reihenfolge in
|
lindenmannm@3
|
469 |
Gruppen eingegeben werden. FF liefert hierbei $m$ Kisten
|
lindenmannm@3
|
470 |
gefüllt mit den Objekten der Größe $\frac{1}{7}+\epsilon$
|
lindenmannm@3
|
471 |
(jeweils 6 pro Kiste) gefolgt von $\frac{6m}{2}=3m$ Kisten
|
lindenmannm@3
|
472 |
gefüllt mit Objekten der Größe $\frac{1}{3}+\epsilon$ (jeweils
|
lindenmannm@3
|
473 |
2 pro Kiste) und schlussendlich $6m$ Kisten mit je einem Objekt
|
lindenmannm@3
|
474 |
der Größe $\frac{1}{2}+\epsilon$. Das macht in der Summe $10m$
|
lindenmannm@3
|
475 |
Kisten. Die optimale Lösung packt je ein Objekt jeder Größe in
|
lindenmannm@3
|
476 |
eine Kiste und benötigt somit nur $6m$ Kisten.\\ Laufzeit für
|
lindenmannm@3
|
477 |
Inputfolgen der Länge $n$: FF $O(n^2) \rightarrow O(n \log n)$
|
lindenmannm@3
|
478 |
\subsubsection{Best-Fit (BF)}
|
lindenmannm@3
|
479 |
Verpacke das nächste Objekt in diejenige Kiste, in die es am
|
lindenmannm@3
|
480 |
besten passt (d.h. den geringsten Platz ungenutzt lässt).
|
lindenmannm@3
|
481 |
Verhalten von BF ähnlich zu FF. Laufzeit für Inputfolgen der
|
lindenmannm@3
|
482 |
Länge $n$: BF $O(n^2) \rightarrow O(n \log n)$
|
lindenmannm@3
|
483 |
\subsection{Offline Verfahren}
|
lindenmannm@3
|
484 |
\underline{NP-schwieriges Problem! Entscheidungsproblem ist NP-vollständig!}\\
|
lindenmannm@3
|
485 |
Zunächst wird die Anzahl $n$ und alle $n$ Objekte vorgegeben. Dann
|
lindenmannm@3
|
486 |
beginnt die Verpackung.\\ $n$ und $s_1, ..., s_n$ sind gegeben,
|
lindenmannm@3
|
487 |
bevor die Verpackung beginnt!\\ $\rightarrow$ \underline{Optimale
|
lindenmannm@3
|
488 |
Verpackung} kann durch erschöpfende Suche bestimmt werden. ABER:
|
lindenmannm@3
|
489 |
Benötigt exponentielle Zeit! Daher Approximimationsalgorithmen, die
|
lindenmannm@3
|
490 |
schneller sind aber dafür unter Umständen nicht optimal!\\
|
lindenmannm@3
|
491 |
Idee für Offline Approximationsalgorithmen: Sortiere die Objekte
|
lindenmannm@3
|
492 |
zunächst nach abnhemender Größe und verpacke größere Objekte zuerst!
|
lindenmannm@3
|
493 |
\subsubsection{First Fit Decreasing (FFD oder FFNI)}
|
lindenmannm@3
|
494 |
\textbf{Lemma 1}: Sei $I$ eine Folge von $n$ Objekten mit
|
lindenmannm@3
|
495 |
Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann
|
lindenmannm@3
|
496 |
haben alle von FFD in den Bins
|
lindenmannm@3
|
497 |
$B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackten Objekte eine
|
lindenmannm@3
|
498 |
Größe von höchstens $\frac{1}{3}$.
|
lindenmannm@3
|
499 |
\\ \textbf{Beweis}:
|
lindenmannm@3
|
500 |
%TODO:Elsässer hat das in seiner VL gemacht - aber hässlich lang
|
lindenmannm@3
|
501 |
\textbf{Lemma 2}: Sei $I$ eine Folge von $n$ Objekten mit
|
lindenmannm@3
|
502 |
Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann
|
lindenmannm@3
|
503 |
ist die Anzahl der Objekte, die FFD in die Kisten
|
lindenmannm@3
|
504 |
$B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackt, höchstens
|
lindenmannm@3
|
505 |
$m-1$.\\ \textbf{Beweis}: Annahme: Es gibt mehr als $m-1$
|
lindenmannm@3
|
506 |
Objekte. $x_1,\ldots,x_m$ in $I$, die FFD in extra Kisten
|
lindenmannm@3
|
507 |
verpacken. Dies führt zu einem Widerspruch.
|
lindenmannm@3
|
508 |
%TODO:Warum?
|
lindenmannm@3
|
509 |
\textbf{Satz}: Für alle Inputfolgen I
|
lindenmannm@3
|
510 |
gilt $FFD(I)\leq(4 OPT(I)+\frac{1}{3})$.\\ \textbf{Satz}:
|
lindenmannm@3
|
511 |
\begin{itemize}
|
lindenmannm@3
|
512 |
\item[1.] Für alle Inputfolgen $I$ gilt: $FFD(I)\leq \frac{11}{9} OPT(I)+4$
|
lindenmannm@3
|
513 |
\item[2.] Es gibt Inputfolgen $I$ mit: $FFD(I)=\frac{11}{9}OPT(I)$.
|
lindenmannm@3
|
514 |
\end{itemize}
|
lindenmannm@3
|
515 |
\textbf{Beweis}: %TODO
|
lindenmannm@3
|
516 |
\subsubsection{Best Fit Decreasing (BFD)}
|
lindenmannm@3
|
517 |
%TODO Nicht im Script???
|
lindenmannm@3
|
518 |
|
lindenmannm@3
|
519 |
\newpage
|
lindenmannm@3
|
520 |
\section{Dynamische Programmierung}
|
lindenmannm@3
|
521 |
\textbf{Idee:} Speichern von zwischen Ergebnissen, welche sonst mehrfach
|
lindenmannm@3
|
522 |
berechnet werden müssten.\\
|
lindenmannm@3
|
523 |
\textbf{Vorgehen:}
|
lindenmannm@3
|
524 |
\begin{itemize}
|
lindenmannm@3
|
525 |
\item Rekursive Beschreibung des Problems P
|
lindenmannm@3
|
526 |
\item Bestimmung einer Menge T, die alle Teilprobleme von P enthält, auf die
|
lindenmannm@3
|
527 |
bei der Lösung von P zugegriffen wird.
|
lindenmannm@3
|
528 |
\item Bestimmung einer Reihenfolge $T_0,\ldots T_k$ der Probleme in T, so dass
|
lindenmannm@3
|
529 |
bei der Lösung von $T_i$ nur auf Probleme $T_j$ mit $j<i$ zurückgegriffen
|
lindenmannm@3
|
530 |
wird.
|
lindenmannm@3
|
531 |
\item Sukzessive Berechnung und Speicherung von Lösungen für $T_0,\ldots T_k$.
|
lindenmannm@3
|
532 |
\end{itemize}
|
lindenmannm@3
|
533 |
Wird im Script anhand der Fibonacci Zahlen demonstriert aber ist trivial \ldots
|
lindenmannm@3
|
534 |
\subsection{Matrixkettenprodukt (TODO)}
|
lindenmannm@3
|
535 |
%TODO
|
lindenmannm@3
|
536 |
\subsection{Optimale Suchbäume (TODO)}
|
lindenmannm@3
|
537 |
%TODO
|
lindenmannm@3
|
538 |
\subsection{Editierdistanz}
|
lindenmannm@3
|
539 |
Berechne für zwei gegebene Zeichenfolgen $A$ und $B$ möglichst effizient die
|
lindenmannm@3
|
540 |
Editier-Distanz $D(A,B)$ und eine minimale Folge von Editieroperationen, die
|
lindenmannm@3
|
541 |
$A$ in $B$ überführt.\\
|
lindenmannm@3
|
542 |
\textbf{Editieroperationen:}
|
lindenmannm@3
|
543 |
\begin{itemize}
|
lindenmannm@3
|
544 |
\item Ersetzen eines Zeichens von $A$ durch ein Zeichen von $B$
|
lindenmannm@3
|
545 |
\item Löschen eines Zeichens von $A$
|
lindenmannm@3
|
546 |
\item Einfügen eines Zeichens von $B$
|
lindenmannm@3
|
547 |
\end{itemize}
|
lindenmannm@3
|
548 |
\textbf{Einheitskostenmodell:}
|
lindenmannm@3
|
549 |
\[c(a,b)=\begin{cases}1 & \text{falls } a\neq b\\0 & \text{falls } a=b\end{cases}\]
|
lindenmannm@3
|
550 |
$a=\epsilon, b=\epsilon$ möglich Dreiecksungleichung soll für $c$ im
|
lindenmannm@3
|
551 |
allgemeinen gelten:
|
lindenmannm@3
|
552 |
\[c(a,c)\leq c(a,b)+c(b,c)\]
|
lindenmannm@3
|
553 |
$\rightarrow$ ein Buchstabe wird höchstens einmal
|
lindenmannm@3
|
554 |
verändert.\\
|
lindenmannm@3
|
555 |
Rekursionsgleichung, falls $m,n\geq 1$
|
lindenmannm@3
|
556 |
\[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
|
557 |
Anfangsbedingung:\\
|
lindenmannm@3
|
558 |
\[D_{0,0}=D(\epsilon,\epsilon)=0\]
|
lindenmannm@3
|
559 |
\[D_{0,j}=D(\epsilon,B_j)=j\]
|
lindenmannm@3
|
560 |
\[D_{i,0}=D(A_i,\epsilon)=i\]
|
lindenmannm@3
|
561 |
\lstinputlisting[language=Java,label=lst:TTlookup,caption=Algorithmus zur
|
lindenmannm@3
|
562 |
Editierdistanz, captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt,
|
lindenmannm@3
|
563 |
basicstyle=\footnotesize]{./code/editierdistanz.code}
|
lindenmannm@3
|
564 |
\textbf{Spurgraph:}\\
|
lindenmannm@3
|
565 |
Übersicht über alle möglichen Spuren zur Transformation von $A$ in $B$,
|
lindenmannm@3
|
566 |
gerichtete Kanten von Knoten $(i,j)$ zu $(i+1,j)$, $(i,j+1)$ und $(i+1,j+1)$.
|
lindenmannm@3
|
567 |
Gewichtung der Kanten entspricht den Editierkosten. Kosten nehmen entlang eines
|
lindenmannm@3
|
568 |
optimalen Weges monoton zu. Jeder Weg mit monotin wachsenden Kosten von der
|
lindenmannm@3
|
569 |
linken oberen Ecke zur rechten unteren Ecke entspricht einer optimalen Spur. Zur
|
lindenmannm@3
|
570 |
Berechnung der Spur der minimalen Editieroperationen (es gibt mehrere
|
lindenmannm@3
|
571 |
Lösungen), kann folgender Algorithmus verwendet werden:
|
lindenmannm@3
|
572 |
\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
|
573 |
|
lindenmannm@3
|
574 |
\section{Suche in Texten}
|
lindenmannm@3
|
575 |
\underline{Gegeben:} Text T $t_1t_2t_3\ldots t_n\in\Sigma^n$ und
|
lindenmannm@3
|
576 |
rin Muster P $p_1p_2p_3\ldots p_m\in\Sigma^m$\\
|
lindenmannm@3
|
577 |
\underline{Gesucht:} Ein oder alle Vorkommen des Musters im Text, d.h.
|
lindenmannm@3
|
578 |
Verschiebungen $i$ mit $0\leq i\leq n-m$.\\
|
lindenmannm@3
|
579 |
\textbf{Naives Verfahren:} iteriere über den Text und suche das Muster. Aufwand:
|
lindenmannm@3
|
580 |
$m\cdot(n-m+1)$ Vergleiche $\implies \Omega(n\cdot m)$
|
lindenmannm@3
|
581 |
\textbf{Verfahren nach Knuth-Morris-Pratt (KMP):}
|
lindenmannm@3
|
582 |
Präffix=Suffix Verfahren. Daraus resultiert eine Shiftmöglichkeit des Musters
|
lindenmannm@3
|
583 |
über den Text. Der Shift geschieht um $next[j]$=Länge des längsten Präfix von
|
lindenmannm@3
|
584 |
$P$, das echtes Suffix von $P_{1\ldots j}$ ist, wobei $j=$Position des letzten
|
lindenmannm@3
|
585 |
Vergleiches.\\
|
lindenmannm@3
|
586 |
\underline{Erstellung des $next[j]$ arrays über P.}\\
|
lindenmannm@3
|
587 |
$P=0101101011$
|
lindenmannm@3
|
588 |
\begin{table}[H]
|
lindenmannm@3
|
589 |
\centering
|
lindenmannm@3
|
590 |
\begin{tabular}{c|c|c|c|c|c|c|c|c|c}
|
lindenmannm@3
|
591 |
1&2&3&4&5&6&7&8&9&10\\\hline
|
lindenmannm@3
|
592 |
0&1&0&1&1&0&1&0&1&1\\\hline
|
lindenmannm@3
|
593 |
& &0& & & & & & & \\
|
lindenmannm@3
|
594 |
& &0&1& & & & & & \\
|
lindenmannm@3
|
595 |
& & & & &0& & & & \\
|
lindenmannm@3
|
596 |
& & & & &0&1& & & \\
|
lindenmannm@3
|
597 |
& & & & &0&1&0& & \\
|
lindenmannm@3
|
598 |
& & & & &0&1&0&1& \\
|
lindenmannm@3
|
599 |
& & & & &0&1&0&1&1\\
|
lindenmannm@3
|
600 |
\end{tabular}
|
lindenmannm@3
|
601 |
\caption{next[j] Beispiel}
|
lindenmannm@3
|
602 |
\label{tab:nextJ}
|
lindenmannm@3
|
603 |
\end{table}
|
lindenmannm@3
|
604 |
$\rightarrow next[j]=[0,0,1,2,0,1,2,3,4,5]$\\
|
lindenmannm@3
|
605 |
\underline{Algorithmus:}
|
lindenmannm@3
|
606 |
\lstinputlisting[language=Java,label=lst:TTlookup,caption=KMP Algorithmus,
|
lindenmannm@3
|
607 |
captionpos=b, numbers=left, numberstyle=\tiny, numbersep=5pt, basicstyle=\footnotesize]{./code/kmp.code}
|
lindenmannm@3
|
608 |
\underline{Analyse:}
|
lindenmannm@3
|
609 |
inkrement $j$ = inkrement $i$ und dekrement $j$ = inkrement $j$!
|
lindenmannm@3
|
610 |
$\rightarrow O(n)$ hinzu kommt noch die Berechnung des next-arrays mit $O(m)$.\\
|
lindenmannm@3
|
611 |
KMP kann also mit $O(n+m)$ berechnet werden. (i.e. Untere Schranke
|
lindenmannm@3
|
612 |
$\Omega(m+n/m)$)
|
lindenmannm@3
|
613 |
|
lindenmannm@3
|
614 |
\newpage
|
lindenmannm@3
|
615 |
\begin{appendix}
|
lindenmannm@3
|
616 |
\section{Landau-Symbole}
|
lindenmannm@3
|
617 |
\begin{figure}[H]
|
lindenmannm@3
|
618 |
\centering
|
lindenmannm@3
|
619 |
\includegraphics[scale=0.45]{img/landau_sym}
|
lindenmannm@3
|
620 |
\caption{Definition der Landau Symbole}
|
lindenmannm@3
|
621 |
\label{fig:landau_sym}
|
lindenmannm@3
|
622 |
\end{figure}
|
lindenmannm@3
|
623 |
\end{appendix}
|
lindenmannm@3
|
624 |
\end{document} |