Exzerpt Algorithmentheorie WS10/11

Markus Lindenmann 20. Januar 2011

Inhaltsverzeichnis

1 Einleitung  2
1.1 Themen: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Problem-/Anwendungsbereiche: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Literatur: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Divide and Conquer  3
2.1 Formulierung des Divide and Conquer Prinzips . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2.1 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Nächste Paare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3.1 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Segmentschnitt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4.1 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.5 Polynomprodukt und Fast Fourier-Transformation . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Randomisierung  6
3.1 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4 Amortisierte Analyse  7
4.1 Binomial Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2 Fibonacci Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.3 Union Find . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5 Greedy  8
5.1 Kürzeste (billigste) Wege . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6 Bin Packing  9
6.1 Online Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6.1.1 Next Fit (NF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6.1.2 First-Fit (FF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6.1.3 Best-Fit (BF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.2 Offline Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.2.1 First Fit Decreasing (FFD oder FFNI) . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.2.2 Best Fit Decreasing (BFD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7 Dynamische Programmierung  11
A Landau-Symbole  12

1 Einleitung

Dozent: Matthias Westermann

Website: http://lak.informatik.uni-freiburg.de

Klausur: 09.03.2011 Hilfsmittel: Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt

1.1 Themen:

• Divide and Conquer

• Greedy Prinzip

• Dynamische Programmierung

• Randomisierung

• Amortisierte Analyse

1.2 Problem-/Anwendungsbereiche:

• Geometrische Algorithmen

• Algebraische Algorithmen

• Graphenalgorithmen

• Datenstrukturen

• Internet-Algorithmen

• ptimierungs-Verfahren

• Zeichenkettenverarbeitung

1.3 Literatur:

Literatur

[PW02] Peter Widmayer, Thomas O.: Algorithmen und Datenstrukturen. 4. Auflage. Spektrum Akademischer Verlag, 2002. – ISBN 978–3827410290

[THC01] Thomas H. Cormen, Robert L. Rivest und Cliford S. Charles E. Leiserson L. Charles E. Leiserson: Introduction to Algorithms. 2nd. Prentice Hall India, 2001. – ISBN 978–8120321410

2 Divide and Conquer

• Quicksort

• Formulierung und Analyse des Prinzips

• Geometrisches Devide and Conquer

- Closest-Pair

- Segmentschnitt

2.1 Formulierung des Divide and Conquer Prinzips

D&C Verfahren zur Lösung eines Problems der Größe n

1. Divide n > 2: Teile das Problem in k Teilprobleme der Größe n_{1}, … n_{k} (k ≥ 2) n ≤ c : Löse das Problem direkt

2. Conquer Löse die k Teilprobleme auf dieselbe Art (rekursiv)

3. Merge Füge die berechneten Teillösungen zu einer Gesamtlösung zusammen

2.2 Quicksort

Wähle beliebiges Pivot Element v und sortiere alle Elemente aus der Menge, die größer sind als v rechts von v ein, die anderen links. Verfahre im selben Muster mit den neuen Teilmengen links und rechts des Pivot Elements. Wenn die zu sortierende Folge F nur ein Element beinhaltet, gebe F zurück.

2.2.1 Analyse

T (n) - maximale Anzahl von Schritten, um ein Problem der Größe n zu lösen.

T (n) = \begin{cases}n ≠ c & a \\ n > c & T (n_{1} + … + T (n_{k}) + Divide- und Mergeaufwand \end{cases}

Best Case: k = 2, n_{1} = n_{2} = \frac{n}{2} Divide- und Mergeaufwand: DM(n) T (1) = a T (n) = 2T (\frac{n}{2}) + DM(n)

2.3 Nächste Paare

Eingabe: n Punkte in Ebene Ausgabe: Punkt-Paar q, r mit geringstem Abstand Abstand: d(q, r) bechreibt Abstand zwischen Punkten q und r

2.3.1 Algorithmus

• sortiere Punktmenge nach x-Koordinate

• Teile Punktmenge in der Mitte L in die Mengen Q und R

• Löse rekursiv auf Q und R

• Sortiere Punkte nach y-Koordinate • Teste alle Paare, deren Abstand in der Sortierung kleiner als 16 ist (siehe unten)

• Füge zusammen

δ = Minimum der Teillösungen Gibt es q ∈ Q und r ∈ R mit d(q, r) < δ, dann sind sowohl q als auch r höchstens δ von L (Mitte) entfernt. Problem: alle Punkte können innerhalb der δ-Zone liegen Lösung:

• Sortiere Punkte in δ Zone nach y-Abstand

• Liegen in dieser Sortierung mehr als c Punkte zwischen q und r, dann kann (q, r) nicht nächstes Paar sein

Dies kann für c = 15 bewiesen werden (vgl. Abbildung 1):

• Seien min. 15 Punkte zwischen q und r

• Dann sind mindestens 3 Reihen Quadrate zwischen q, r, weil in jedem Quadrat höchstens ein Punkt ist.

→ Dann muss d(q, r) mindestens \frac{3}{2}δ > δ sein.

Abbildung 1: Nächste Paare: Prüf Distanz

2.3.2 Analyse

T (n) = \begin{cases}n ≤ 3 & a \\ n > 3 & 2T (\frac{n}{2}) + an \end{cases}

T (n) ≤ an log n

2.4 Segmentschnitt

Eingabe: Menge S bestehend aus vertikalen Segmenten und Endpunkten vn horizontalen Segmenten Ausgabe: Alle Schnittpunkte von vertikalen Segmenten mit horizontalen Segmenten, von denen mindesens ein Endpunkt in S ist 2.4.1 Algorithmus

Divide & Conquer: Fallunterscheidung

1. |S| > 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. else: S enthält keine Schnitte

Merge Bilde L(S), R(S) und V(S) (Definition am Beispiel i = 1, 2 berechnet: S = S_{1} ∪ S_{2}):

• L(S): y-Koordinate aller linken Endpunkte in S, deren rechter Partner nicht in S = L(S_{2}) ∪ (L(S_{1}) − R(S_{2}))

• R(S): y-Koordinate aller rechten Endpunkte in S, deren linker Partner nicht in S = R(S_{1}) ∪ (R(S_{2}) − L(S_{1}))

• V(S): y-Intervalle der vertikalen Segmente in S = V (S_{1}) ∪ V (S_{2})

L,R sortiert nach steigender y-Koordinate V sortiert nach steigendem unteren Endpunkt

Basisfälle S enthält nur ein Element s. Fallunterscheidung:

1. s = (x, y) ist ein linker Endpunkt:

L(S) = {y},  R(S) = ∅,  V (S) = ∅

2. s = (x, y) ist ein rechter Endpunkt:

L(S) = ∅,  R(S) = {y},  V (S) = ∅

3. s = (x, y_{1}, y_{2}) ist ein vertikales Segment:

L(S) = ∅,  R(S) = ∅,  V (S) = {[y_{1}, y_{2}]}

2.4.2 Analyse

Eingabe wird Anfangs sortiert und in Array gespeichert

T (n) = 2T (\frac{n}{2} + an + Größe der Ausgabe
T (1) = O(1)
O(n log n + k | k = #Schnittpunkte

2.5 Polynomprodukt und Fast Fourier-Transformation

3 Randomisierung

3.1 Hashing

4 Amortisierte Analyse

4.1 Binomial Heaps 4.2 Fibonacci Heaps 4.3 Union Find

5 Greedy

5.1 Kürzeste (billigste) Wege

6 Bin Packing

Problembeschreibung: Man hat n Objekte verschiedener Größe mit 0 < s_{i} ≤ 1 | 1 ≤ i ≤ n. Gesucht ist die kleinst mögliche Anzahl an Kisten (Bins) der Größe 1, mit der alle Objekte verpackt werden können.

6.1 Online Verfahren

Jedes (ankommende) Objekt muss verpackt sein, bevor das nächste Objekt betrachtet wird. Ein Objekt verbleibt in derjenigen Kiste, in die es zuerst gepackt wird. Kein Online Bin Packing Verfahren kann stets eine optimale Lösung finden! Satz 1: Es gibt Eingaben, die jeden Online Bin Packing Algorithmus zwingen, wenigstens \frac{4}{3}OP T Bins zu verwenden, wobei OP T die minimal mögliche Binzahl ist. Beweis Annahme: Online Bin Packing Algorithmus benötigt stets weniger als \frac{4}{3}OP T Bins. Es wird eine Eingabe mit 2m Objekten angenommen. Die ersten m sind um ϵ kleiner als \frac{1}{2}, die zweiten m um ϵ größer. Die optimale Lösung sind m Kisten, da immer ein großes mit einem kleinen Paket kombiniert werden kann. Nun teilt man die Analyse in zwei Zeitpunkte: nach m Objekten und nach 2m Objekten. Laut Annahme gilt nach nach m Objekten, dass die Anzahl der Bins b nur maximal \frac{4}{3}OP T groß sein darf. Mit OP T = \frac{m}{2} gilt somit: b = \frac{4}{3} · \frac{m}{2} = \frac{2}{3}m. Sei b = b_{1} + b_{2} | b_{1} = #Bins mit einem Objekt, b_{2} = #Bins mit zwei Objekten, so folgt b_{1} + 2b_{2} = m ⟹ b_{1} = m − 2b_{2} ⟹ b = b_{1} + b_{2} = m − b_{2}. Nach 2m Objekten ist OP T = m, wie zuvor beschrieben. b_{1} Bins können zu diesem Zeitpunkt mit Objekten des zweiten Bereichs gefüllt werden, für die verbleibenden muss man neue Bins öffnen. Die Anzahl der neu zu öffnenden beträgt damit genau b_{2} ⟹ #Bins ≥ b + m − b_{1} = m + b_{2}. Die Annahme besagt m + b_{2} ≤ #Bins < \frac{4}{3}m ∧ b_{2} < \frac{m}{3}. Dies ist nur möglich, wenn b = m − b_{2} > \frac{2}{3}m - Dies führt zu einem \underline{Widerspruch}, da b zum Zeitpunkt 1, nach m Objekten < \frac{2}{3}m sein muss.

6.1.1 Next Fit (NF)

Verpacke das nächste Objekt in dieselbe Kiste wie das vorherige, wenn es dort noch hineinpasst, sonst öffne eine neue Kiste und verpacke es dort. Satz 2: (a) Für alle Inputfolgen I gilt: NF (I) ≤ 2OP T (I). (b) Es gibt Inputfolgen I mit NF (I) ≥ 2OP T (I)− 2. Beweis

(a) Betrachte zwei beliebige aufeinanderfolgende Kisten B_{2k−1}, B_{2k}. Man weiß, dass die beinhalteten Objekte eine Summengröße > 1 haben, sonst wären selbige in einer Kiste. Daraus folgt, man kann nicht mehr als die doppelte Anzahl an Kisten als beim Optimum erreichen!

(b) Inputfolge: 0.5, \frac{2}{n}, 0.5, \frac{2}{n}, 0.5, \frac{2}{n}, … 0.5, \frac{2}{n}. Next-Fit liefert nun immer Bins gefüllt mit 0.5 + \frac{2}{n}. Darausfolgt NF (I) = \frac{n}{2} und OP T = \frac{n}{4} + 1 (weil \frac{n}{2} mal 0.5er Objekte in = \frac{n}{4} Kisten passen und \frac{n}{2} \frac{2}{n}er Objekte in eine Kiste passen) Laufzeit für Inputfolgen der Länge n: NF O(n)

6.1.2 First-Fit (FF)

Packe nächstes Objekt in die erste Kiste, in die es noch hineinpasst, wenn es eine solche Kiste gibt, sonst in eine neue Kiste. Beobachtung: Zu jedem Zeitpunkt kann es höchstens eine Kiste geben, die weniger als halb voll ist. ( ⟹ F F (I) ≤ 2OP T (I)) Satz 3: (a) Für alle Inputfolgen I gilt F F (I) ≤ ⌈\frac{17}{10}OP T (I)⌉. (b) Es gibt Inputfolgen I mit F F (I) ≥ \frac{17}{10}(OP T (I) − 1). (b’) Es gibt Inputfolgen I mit F F (I) = \frac{10}{6}OP T (I). Beweis (b’) Inputfolge der Länge 3 · 6m. Dabei je 6m Objekte der Größen \frac{1}{7} + ϵ, \frac{1}{3} + ϵ, \frac{1}{2} + ϵ, welche in gegebener Reihenfolge in Gruppen eingegeben werden. FF liefert hierbei m Kisten gefüllt mit den Objekten der Größe \frac{1}{7} + ϵ (jeweils 6 pro Kiste) gefolgt von \frac{6m}{2} = 3m Kisten gefüllt mit Objekten der Größe \frac{1}{3} + ϵ (jeweils 2 pro Kiste) und schlussendlich 6m Kisten mit je einem Objekt der Größe \frac{1}{2} + ϵ. Das macht in der Summe 10m Kisten. Die optimale Lösung packt je ein Objekt jeder Größe in eine Kiste und benötigt somit nur 6m Kisten. Laufzeit für Inputfolgen der Länge n: FF O(n^{2}) → O(n log n)

6.1.3 Best-Fit (BF)

Verpacke das nächste Objekt in diejenige Kiste, in die es am besten passt (d.h. den geringsten Platz ungenutzt lässt). Verhalten von BF ähnlich zu FF. Laufzeit für Inputfolgen der Länge n: BF O(n^{2}) → O(n log n)

6.2 Offline Verfahren

NP-schwieriges Problem! Entscheidungsproblem ist NP-vollständig! Zunächst wird die Anzahl n und alle n Objekte vorgegeben. Dann beginnt die Verpackung. n und s_{1}, ..., s_{n} sind gegeben, bevor die Verpackung beginnt! → \underline{Optimale Verpackung} kann durch erschöpfende Suche bestimmt werden. ABER: Benötigt exponentielle Zeit! Daher Approximimationsalgorithmen, die schneller sind aber dafür unter Umständen nicht optimal! Idee für Offline Approximationsalgorithmen: Sortiere die Objekte zunächst nach abnhemender Größe und verpacke größere Objekte zuerst!

6.2.1 First Fit Decreasing (FFD oder FFNI)

Lemma 1: Sei I eine Folge von n Objekten mit Größen s_{1} ≥ s_{2} ≥ … ≥ s_{n} und sei m = OP T (I). Dann haben alle von FFD in den Bins B_{m+1}, B_{m+2}, …, B_{F F D(I)} verpackten Objekte eine Größe von höchstens \frac{1}{3}. Beweis: $$$TODO:Elsässer hat das in seiner VL gemacht - aber hässlich lang$$$ Lemma 2: Sei I eine Folge von n Objekten mit Größen s_{1} ≥ s_{2} ≥ … ≥ s_{n} und sei m = OP T (I). Dann ist die Anzahl der Objekte, die FFD in die Kisten B_{m+1}, B_{m+2}, …, B_{F F D(I)} verpackt, höchstens m − 1. Beweis: Annahme: Es gibt mehr als m − 1 Objekte. x_{1}, …, x_{m} in I, die FFD in extra Kisten verpacken. Dies führt zu einem Widerspruch. $$$TODO:Warum?$$$ Satz: Für alle Inputfolgen I gilt F F D(I) ≤ (4OP T (I) + \frac{1}{3}). Satz:

1. Für alle Inputfolgen I gilt: F F D(I) ≤ \frac{11}{9}OP T (I) + 4

2. Es gibt Inputfolgen I mit: F F D(I) = \frac{11}{9}OP T (I).

Beweis: $$$TODO$$$

6.2.2 Best Fit Decreasing (BFD)

Nicht im Script???

7 Dynamische Programmierung

11

A Landau-Symbole

Abbildung 2: Definition der Landau Symbole