Exzerpt Algorithmentheorie WS10/11

Markus Lindenmann 18. Februar 2011

Inhaltsverzeichnis

1 Einleitung  3
1.1 Themen: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Problem-/Anwendungsbereiche: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Literatur: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Divide and Conquer  4
2.1 Formulierung des Divide and Conquer Prinzips . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.1 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Nächste Paare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3.1 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4 Segmentschnitt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4.1 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4.2 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.5 Polynomprodukt und Fast Fourier-Transformation (TODO) . . . . . . . . . . . . . . . . . . . 6
3 Randomisierung  7
3.1 Randomisierter Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.1 Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Randomisierter Primzahltest (TODO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3 RSA (TODO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.4 Treaps (TODO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.5 Hashing (TODO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4 Amortisierte Analyse (TODO)  8
4.1 Binomial Heaps (TODO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 Fibonacci Heaps (TODO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.3 Union Find (TODO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5 Greedy  9
5.1 Kürzeste (billigste) Wege . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.1.1 Single Source Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.2 Spannbäume minimalen Gewichts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.2.1 Das Wachsen von min. Spannbäumen . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.2.2 Schnitte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2.3 Sichere Kanten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2.4 Der Graph G_{A} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2.5 Algorithmus von Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2.6 Algorithmus von Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

6 Bin Packing  14
6.1 Online Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.1.1 Next Fit (NF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.1.2 First-Fit (FF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.1.3 Best-Fit (BF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.2 Offline Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.2.1 First Fit Decreasing (FFD oder FFNI) . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.2.2 Best Fit Decreasing (BFD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7 Dynamische Programmierung  16
7.1 Matrixkettenprodukt (TODO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.2 Optimale Suchbäume (TODO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.3 Editierdistanz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
8 Suche in Texten  17
A Landau-Symbole  19

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

• Optimierungs-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 (meist das letzte Element in der Input-Folge!) und sortiere alle Elemente aus der Menge, die größer sind als v rechts von v ein, die anderen links. Verfahre im selben Muster mit den neuen Teilmengen links und rechts des Pivot Elements. Wenn die zu sortierende Folge F nur ein Element beinhaltet, gebe F zurück.

2.2.1 Algorithmus

1 Input : u n s o r t i e r t e r Bereich [ p , r ] in Array A
2 Output : s o r t i e r t e r Bereich [ p , r ] in Array A
3 i f r > p then
4  wähle Pivotelement x = A[ r ]
5  m = p a r t i t i o n (A, p , r )
6  /∗ T e i l e A b z g l . x auf :
7  ∗ A[ p ] , …,A[m−1] <= x <= A[m+ 1 ] , …,A[ r ]
8  ∗/
9 Quicksort (A, p , m − 1)
10 Quicksort (A, m + 1 , r )

Listing 1: Algorithmus Quicksort

2.2.2 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 (TODO)

3 Randomisierung

• Klassen von randomisierten Algorithmen

– Las Vegas: \underline{immer} Korrekt, erwartete Laufzeit (randomisierter Qicksort)

– Monte Carlo: \underline{wahrscheinlich} (MC:mostly correct) Korrekt, garantierte Laufzeit (randomisierter Primzahltest)

• Randomisierter Quicksort

• Randomisierter Primzahltest

• Kryptographie

3.1 Randomisierter Quicksort

Refer to 2.2 for basic description of the algorithm. Problem von Quicksort: bisher nimmt Quicksort immer das letzte Element in der Folge ⟹ Worst-Case: sortierte Folge als Eingabe (Θ(n^{2})). Ziel: keine quadratische Laufzeit. Lösung: randomisierte Auswahl des Pivotelements an Stelle i. Anschließend tauschen von Position i und r (mit r=rechte Grenze des zu sortierenden Segments).

3.1.1 Analyse

Analyse 1: erwartete Laufzeit Mit Wahrscheinlichkeit \frac{1}{n} wird das i-kleinste Element S_{i} gewählt wobei n zu sortierenden Elemente vorhanden sind. Abhängig von der Wahl von S_{i} ergeben sich Teilprobleme der Größe i − 1 und n − i. Damit ergibt sich für die Laufzeit T (n).

T (n) = \frac{1}{n}(T (0) + T (n − 1)) + \frac{1}{n}(T (1) + T (n − 2)) + … + \frac{1}{n}(T (k − 1) + T (n − k)) + … +

\frac{1}{n}(T (n − 1) + T (0)) + Θ(n)) | Θ(n) für partition

= \frac{1}{n} ∑_{k=1}^{n}(T (k − 1) + T (n − k)) + Θ(n)

\frac{2}{n} ∑_{k=1}^{n} T (k − 1) + Θ(n)

= O(n log n)

Analys 2: Erwartete Anzahl der Vergleiche

x_{ij} = \begin{cases}1 & falls S_{i} mit S_{j} verglichen wird \\ 0 & sonst \end{cases}

E [∑_{i=1}^{n} ∑_{j>1} x_{ij}] = ∑_{i=1}^{n} ∑_{j>1} E[x_{ij}]

p_{ij} = Wahrscheinlichkeit S_{i} wird mit S_{j} verglichen

E[x_{ij} = 1 · p_{ij} + 0 · (1 − p_{ij} = p_{ij}

3.2 Randomisierter Primzahltest (TODO)

3.3 RSA (TODO)

3.4 Treaps (TODO)

3.5 Hashing (TODO)

4 Amortisierte Analyse (TODO)

4.1 Binomial Heaps (TODO) 4.2 Fibonacci Heaps (TODO) 4.3 Union Find (TODO)

5 Greedy

Momentan beste Teillösung wählen. Die Summe dieser optimalen Teillösung ergibt die gesamt Lösung. Möglicher Zustand der Gesamtlösung:

• Wir erhalten die optimale Gesamtlösung.

• Wir erhalten eine Lösung, die zwar nicht immer optimal ist, aber vom Optimum stets nur wenig abweicht.

• Die berechnete Lösung kann beliebig schlecht werden.

\underline{Beispiele:}

• Münzwechselproblem Ziel: Bezahlung eines Betrages in möglichst wenig Münzen und Banknoten. Lösung (Greedy): Wähle die maximale Anzahl von Banknoten und Münzen mit jeweils größtmöglichem Wert, bis der gewünschte Betrag erreicht ist. (Dies führt nur für bestimmte Werte der Zahlungsmittel zur optimalen Gesamtlösung!)

• Handlungsreisenden-Problem (Traveling Sales Man Problem, TSP)

Ziel: Finden der billigsten Rundreise, diealle Orte genau einmal besucht. Lösung (Greedy): Gehe immer den günstigsten Weg vom aktuellen Knoten zu einem noch nicht besuchten Knoten. Wenn alle besucht wurden, kehre zum Anfang zurück. (Mit Greedy keine optimale Gesamtlösung!)

• Aktivitäten Auswahlproblem Ziel: möglichst viele Anfragen erfüllen. (Muss nicht bedeuten, dass die Ressource optimal genutzt wird!) Lösung (Greedy): Nimm die Anfrage, die am frühesten fertig ist. (optimale Gesamtlösung!) Analyse: Θ(n)

5.1 Kürzeste (billigste) Wege

Pfad P = Folge von Knoten. Kosten eines Pfades:

c(P) = ∑_{i=0}^{P.length−1} c(v_{i}, v_{i+1}

Entfernung von v nach w sind die Kosten des günstigsten Pfades:

dist(v, w) = infc(P) | P = Weg von v nach w

Kosten eines unerreichbaren Knoten sind definiert als ∞. Kosten eines Pfades in einem negativen Zyklus: −∞. Es können also nur Graphen ohne negative Zyklen sinnvoll betrachtet werden!

5.1.1 Single Source Shortest Paths

Kürzeste/Günstigste Pfade von einem Knoten s zu allen anderen Knoten. Hierfür nutzt man die Dreiecksungleichung über dist(u, v) | (u, v) ∈ E und s ∈ V:

dist(s, v) ≤ dist(s, u) + dist(u, v)

Greedy-Ansatz

• Überschätze die dist-Funktion

dist(s, v) = \begin{cases}0 & falls v = s \\ ∞ & falls v ≠ s \end{cases}

Abbildung 2: Tree for Dijkstra Example

• Solange eine Kante e = (u, v) existiert mit dist(s, v) > dist(s, u) + c(u, v) setze dist(s, v) = dist(s, u) + c(u, v)

Durch die Überschätzung kann die Dreicksungleichung nur noch für Knoten s und seine direkten Nachfolger verletzt werden! Alle folgenden Verfahren basieren auf diesem Prinzip! Effiziente Implementierungen Diese sind im Allgemeinen nicht bekannt, jedoch für wichtige Spezialfälle.

• Nicht-negative Netzwerke: \underline{Dijkstra}

• Netzwerke ohne negative Zyklen: \underline{Bellman-Ford}

• Azyklische Netzwerke

\underline{Dijkstra}

1 DIST [ s ]=0;
2 I n s e r t (U, 0 , s ) ;
3 f o r a l l ( v :V\{ s }) {
4  DIST [ v]= i n f t y ;
5  I n s e r t (U, i n f t y , v ) ;
6 }
7 while ! Empty(U) {
8  (d , u)=DeleteMin (U) ;
9  f o r a l l ( e=(u , v ) : E) {
10  i f (DIST [ v]>DIST [ u]+c (u , v ) ) {
11  DIST [ v]=DIST [ u]+c (u , v ) ;
12  DecreaseKey (U, v , DIST [ v ] ) ;
13 }}}

Listing 2: Algorithmus von Dijkstra

Dijkstra Beispiel: Komplexität:

O(n · (T_{insert} + T_{Empty} + T_{DeleteMin}) + m · T_{DecreaseKey} + m + n)

Implementierung mit Fibonaci-Heaps: T_{Insert} : O(1) T_{DeleteMin} : O(log n) (amortisiert) T_{DecreaseKey} : O(1) (amortisiert)

O(n log n + m)

Bellman-Ford

1 DIST [ s ]=0; 2 Z [ s ]=0; 3 f o r a l l ( v :V\{ s }) {

DIST[v]

s a b c d e f U
0 ∞ ∞ ∞ ∞ ∞ ∞ s,a,b,c,d,e,f
0* ∞ ∞ ∞ ∞ ∞ ∞ a,b,c,d,e,f
0* 6 7 5* ∞ ∞ ∞  a,b,d,e,f
0* 6* 7 5* ∞ ∞ 14  b,d,e,f
0* 6* 7* 5* 9 10 14  d,e,f
0* 6* 7* 5* 9* 10 11  e,f
0* 6* 7* 5* 9* 10* 11  f
0* 6* 7* 5* 9* 10* 11*  ∅

Tabelle 1: Dijkstra Example

4  DIST [ v]= i n f t y ;
5  Z [ v ]=0;
6 }
7 U={s } ;
8 while ( !U. Empty) {
9  Wähle und s t r e i c h e Knoten u am Kopf von U;
10  Z [ u]=Z [ u ]+1;
11  i f Z [ u]>n
12  return " n e g a t i v e r ␣ Zyklus " ;
13  f o r a l l ( e=(u , v ) : E) {
14  i f (DIST [ v]>DIST [ u]+c (u , v ) ) {
15  DIST [ v]=DIST [ u]+c (u , v ) ;
16  U=[U, { v } ] ;
17 }}}

Listing 3: Algorithmus von Belman-Ford

Azyklische Netzwerke

1 S o r t i e r e G=(V, E, c ) t o p o l o g i s c h ;
2 DIST [ s ]=0;
3 f o r a l l ( v :V\{ s }){
4  DIST [ v]= i n f t y ;
5 }
6 U={v | v :V mit num( v)<n } ;
7 while ( !U. Empty) {
8  Wähle und s t r e i c h e Knoten u :U mit kleinstem num−Wert ;
9  f o r a l l ( e=(u , v ) : E) {
10  i f (DIST [ v]>DIST [ u]+c (u , v ) ) {
11  DIST [ v]=DIST [ u]+c (u , v ) ;
12 }}}

Listing 4: Algorithmus für Azyklische Netzwerke

5.2 Spannbäume minimalen Gewichts

Ungerichteter Graph G = (V, E), Kostenfunktion c : E → R. Sei T ⊆ E ein Baum (zusammenhängender azyklischer Teilgraph) Kosten von T: c(T) = ∑_{(u,v)∈T} c(u, v). Ein minimaler Spannbaum ist ein Baum T ⊆ E, der alle Knoten in V verbindet minimale Kosten hat.

5.2.1 Das Wachsen von min. Spannbäumen

Invariante: Verwalte Menge A ⊆ E, die Teilmenge eines minimalen Spannbaums ist. Definition: Eine Kante (u, v) ∈ E\A ist sicher für A, wenn A∪(u, v) Teilmenge eines minimalen Spannbaums ist.

1 Algorithmus Generischer −MST(G, c ) ;
2 A = EmptySet ;
3 while (A i s t kein Spannbaum ) {

4  Finde s i c h e r e Kante (u , v ) f ü r A;
5  A = [A, {(u , v ) } ] ;
6 }

Listing 5: Greedy Algorithmus für Spannbäume

5.2.2 Schnitte

Ein Schnitt (S, V \S) ist eine Partition von V. Eine Kante (u, v) schneidet (S, V \S), wenn ein Endpunkt in S und der andere in V \S liegt. Ein Schnitt „respektiert A“, wenn keine Kante aus A den Schnitt schneidet. Eine Kante heißt minimal bzgl. eines Schnitts, wenn sie den Schnitt schneidet und unter allen solchen Kanten minimale Kosten hat.

5.2.3 Sichere Kanten

Satz: Sei A Teilmenge eines minimalen Spannbaums T und (S, V \S) ein Schnitt, der A respektiert. Ist (u, v) eine minimale Kante bzgl. (S, V §), dann ist (u, v) sicher für A. Beweis:

1. Fall (u, v) ∈ T : ok

2. Fall (u, v) ∉ T : Wir konstruieren minimalen Spannbaum T′ mit (u, v) ∈ T′ und A ⊆ T′.

5.2.4 Der Graph G_{A}

G_{A} = (V, A)

• ist ein \underline{Wald}, d.h. eine Menge von Bäumen

• anfangs, wenn A = ∅, ist jeder Baum ein einzelner Knoten

• eine sichere Kante verbindet verschiedene Bäume

Korollar: Sei B ein Baum in G_{A} = (V, A). Ist (u, v) eine Kante minimaler Kosten, die B und einen anderen Baum in G_{A} verbindet, dann ist (u, v) sicher für A.

5.2.5 Algorithmus von Kruskal

Wähle stets eine Kante minimaler Kosten, die zwei Bäume B_{1} und B_{2} in G_{A} verbindet.

1 A = EmptySet ;
2 f o r a l l ( v :V)
3  Bv={v } ;
4 Erzeuge e i n e L i s t e L der Kanten in E, welche gemäß
5 nicht −f a l l e n d e n Kantenkosten s o r t i e r t i s t ;
6 f o r a l l (u , v ) : L {
7  B1=FIND( u ) ;
8  B2=FIND( v ) ;
9  i f (B1!=B2)
10  A=[A, { ( u , v ) } ] ;
11  UNION(B1 , B2 , B1 ) ;
12 }

Listing 6: Algorithmus von Kruskal

Laufzeit: O(mα(n) + m + m log n)

5.2.6 Algorithmus von Prim

A ist immer ein einziger Baum. Starte mit einem beliebigen Wurzelknoten w. Füge in jedem Schritt eine minimale Kante hinzu, die einen Knoten in A mit einem Knoten in V \A verbindet. Implementierung Q: Prioritätenwarteschlange, die alle Knoten v ∈ V \A enthält. Schlüssel von v: minimale Kosten einer Kante, die v mit einem Knoten aus A verbindet. Für einen Knoten v ist p[v] der Elter-Knoten von v in dem Baum.

A = (v, p[v]) : v ∈ V − w − Q

1 f o r a l l ( v :V)
2  I n s e r t (Q, i n f t y , v ) ;
3 Wähle einen Knoten w:V a l s Wurzel ;
4 DecreaseKey (Q, 0 , w) ;
5 p [w]= n i l ;
6 while ( ! Empty(Q) ) {
7  (d , u)=DeleteMin (Q) ;
8  f o r a l l ( ( u , v ) : E)
9  i f ( v :Q && c (u , v)<v . Key) {
10  DecreaseKey (Q, c (u , v ) , v ) ;
11  p [ v]=u ;
12  }

Listing 7: Algorithmus von Prim

Laufzeit: O(n log n + m)

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: 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. 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:

6.2.2 Best Fit Decreasing (BFD)

7 Dynamische Programmierung

Idee: Speichern von zwischen Ergebnissen, welche sonst mehrfach berechnet werden müssten. Vorgehen:

• Rekursive Beschreibung des Problems P

• Bestimmung einer Menge T, die alle Teilprobleme von P enthält, auf die bei der Lösung von P zugegriffen wird.

• Bestimmung einer Reihenfolge T_{0}, … T_{k} der Probleme in T, so dass bei der Lösung von T_{i} nur auf Probleme T_{j} mit j < i zurückgegriffen wird.

• Sukzessive Berechnung und Speicherung von Lösungen für T_{0}, … T_{k}. Wird im Script anhand der Fibonacci Zahlen demonstriert aber ist trivial …

7.1 Matrixkettenprodukt (TODO) 7.2 Optimale Suchbäume (TODO) 7.3 Editierdistanz

Berechne für zwei gegebene Zeichenfolgen A und B möglichst effizient die Editier-Distanz D(A, B) und eine minimale Folge von Editieroperationen, die A in B überführt. Editieroperationen:

• Ersetzen eines Zeichens von A durch ein Zeichen von B

• Löschen eines Zeichens von A

• Einfügen eines Zeichens von B Einheitskostenmodell:

c(a, b) = \begin{cases}1 & falls a ≠ b \\ 0 & falls a = b \end{cases}

a = ϵ, b = ϵ möglich Dreiecksungleichung soll für c im allgemeinen gelten:

c(a, c) ≤ c(a, b) + c(b, c)

→ ein Buchstabe wird höchstens einmal verändert. Rekursionsgleichung, falls m, n ≥ 1

D_{m,n} = min \begin{cases}D_{m−1,n−1} + c(a_{m}, b_{n}) \\ D_{m−1,n} + 1 \\ D_{m,n−1} + 1 \end{cases} \}

Anfangsbedingung:

D_{0,0} = D(ϵ, ϵ) = 0
D_{0,j} = D(ϵ, B_{j}) = j
D_{i,0} = D(A_{i}, ϵ) = i

1 Input : Zwei Zeichenketten A und B
2 Output : Matrix D=(Dij )
3 D[ 0 , 0 ] : = 0
4 for i := 1 to m do D[ i , 0 ] = i
5 for j := 1 to n do D[ 0 , j ] = j
6 for i := 1 to m do
7  for j := 1 to n do
8  D[ i , j ] := min (D[ i − 1 , j ] + 1 ,
9  D[ i , j − 1 ] + 1 ,
10  D[ i −1, j −1]+c ( ai , bj ) )

Listing 8: Algorithmus zur Editierdistanz

Spurgraph: Übersicht über alle möglichen Spuren zur Transformation von A in B, gerichtete Kanten von Knoten (i, j) zu (i + 1, j), (i, j + 1) und (i + 1, j + 1). Gewichtung der Kanten entspricht den Editierkosten. Kosten nehmen entlang eines optimalen Weges monoton zu. Jeder Weg mit monotin wachsenden Kosten von der linken oberen Ecke zur rechten unteren Ecke entspricht einer optimalen Spur. Zur Berechnung der Spur der minimalen Editieroperationen (es gibt mehrere Lösungen), kann folgender Algorithmus verwendet werden:

1 Input : Berechnete Matrix D
2 Output : Sequenz der E d i t i e r o p e r a t i o n e n
3 i f i==0 & j==0 then return
4 i f i !=0 and D[ i , j ]==D[ i −1, j ]+1
5  then E d i t i e r o p e r a t i o n e n ( i −1, j )
6  " l ö s c h e ␣a [ i ] "
7 else i f j !=0 and D[ i , j ]==D[ i , j −1]+1
8  then E d i t i e r o p e r a t i o n e n ( i , j −1)
9  " füge ␣b [ j ] ␣ e i n "
10 else /∗ D[ i , j ]=D[ i −1, j −1 ]+c ( a [ i ] , b [ j ] ) ∗/
11  E d i t i e r o p e r a t i o n e n ( i −1, j −1)
12  " e r s e t z e ␣a [ i ] ␣ durch ␣b [ j ] "

Listing 9: Algorithmus zum Spurgraphen

8 Suche in Texten

\underline{Gegeben:} Text T t_{1}t_{2}t_{3} … t_{n} ∈ Σ^{n} und rin Muster P p_{1}p_{2}p_{3} … p_{m} ∈ Σ^{m} \underline{Gesucht:} Ein oder alle Vorkommen des Musters im Text, d.h. Verschiebungen i mit 0 ≤ i ≤ n − m. Naives Verfahren: iteriere über den Text und suche das Muster. Aufwand: m · (n − m + 1) Vergleiche ⟹ Ω(n·m) Verfahren nach Knuth-Morris-Pratt (KMP): Präffix=Suffix Verfahren. Daraus resultiert eine Shiftmöglichkeit des Musters über den Text. Der Shift geschieht um next[j]=Länge des längsten Präfix von P, das echtes Suffix von P_{1...j} ist, wobei j =Position des letzten Vergleiches. Erstellung des next[j] arrays über P. P = 0101101011

1 2 3 4 5 6 7 8 9 10
0 1 0 1 1 0 1 0 1 1

0

0 1

0

0 1
0 1 0
0 1 0 1
0 1 0 1 1

Tabelle 2: next[j] Beispiel

→ next[j] = [0, 0, 1, 2, 0, 1, 2, 3, 4, 5] Algorithmus:

1 KMP := proc (T : : s t r i n g , P : : s t r i n g )
2 # Input : Text T und Muster P
3 # Output : L i s t e L mit Verschiebungen i ,
4 #  an denen P in T vorkommt
5  n := length (T) ; m := length (P ) ;
6  L := [ ] ; next := KMPnext(P ) ;
7  j := 0 ;
8  for i from 1 to n do
9  w h i l e j >0and T[ i ]!=P[ j +1]
10  do j := next [ j ] od ;
11  i f T[ i ] = P[ j +1] then j := j+1 f i ;
12  i f j = m then
13  L := [ L [ ] , i−m] ;
14  j := next [ j ]
15  f i ;
16  od ;
17  RETURN (L ) ;
18 end ;

19

20 KMPnext := proc (P : : s t r i n g )
21 #Input : Muster P
22 #Output : next−Array f ü r P
23  m := length (P ) ;
24  next := array ( 1 . .m) ;
25  next [ 1 ] := 0 ;
26  j := 0 ;
27  for i from 2 to m do
28  while j > 0 and P[ i ] <> P[ j +1]
29  do j := next [ j ] od ;
30  i f P[ i ] = P[ j +1] then j := j+1 f i ;
31  next [ i ] := j
32  od ;
33  RETURN ( next ) ;
34 end ;

Listing 10: KMP Algorithmus

\underline{Analyse:} inkrement j = inkrement i und dekrement j = inkrement j! → O(n) hinzu kommt noch die Berechnung des next-arrays mit O(m). KMP kann also mit O(n + m) berechnet werden. (i.e. Untere Schranke Ω(m + n/m))

A Landau-Symbole

Abbildung 3: Definition der Landau Symbole