Algorithmen und Komplexitätstheorie

Universität Bonn

Algorithmen & Komplexitätstheorie

Nach den Vorlesungen von
Prof. Dr. T. Lengauer

Skript
von:
Kai Lingemann
und
Christoph Vogt

 November 2000

Vorwort
Allgemeines

Dieses Dokument, erstellt mit LATEX, hat das Ziel, den Leser bei der Vorbereitung für die Informatik- Diplomprüfung, Bereich Theorie (A), bei Prof. Dr. T. Lengauer zu unterstützen.

Wir haben sowohl die Vorlesung als auch die angegebene Literatur um von uns erarbeitete Gedanken erweitert. Diese sind beidseitig eingerückt und daher leicht vom restlichen Text zu unterscheiden. Wir übernehmen natürlich keine Garantie für die Richtigkeit oder Vollständigkeit unserer Überlegungen oder des aufgeführten Stoffes. Wir empfehlen außerdem den Besuch der Vorlesungen Prof. Lengauers, d.h. es ist unserer Meinung nach nicht ratsam, dieses Skript als alleinige Prüfungsvorbereitung zu verwenden. Trotz des hohen Schwierigkeitsgrades halten wir die Vorlesungen für eine gute Wahl, was den A-Bereich anbetrifft, da die Vorlesungen von Prof. Lengauer meist sehr praxisorientiert sind (für eine A-Vorlesung). Die vorgestellten Konzepte finden durchaus auch in der Praxis Verwendung.

Prof. Lengauer selbst ist in keiner Weise an der Erstellung dieses Skriptes beteiligt. Ihn auf eventuelle Fehler hinzuweisen ist unnötig und sinnlos. Alle noch vorhandenen Fehler sind uns zuzuschreiben.

Zu den Vorlesungen

Dieses Skript basiert zum einen auf der Literatur zu "Algorithmen\ und dieser Vorlesung selber sowie den Literaturangaben zu der Vorlesung "Komplexitätstheorie\ und dieser Vorlesung selber.
Die Vorlesung "Algorithmen\ wurde im SS 1999 gehalten. Die Basis für den größten Teil der Vorlesung bildete dabei ein neues Werk von Mehlhorn und Näher. Diese haben eine Bibliothek (LEDA) ins Leben gerufen, die umfangreiche und effiziente Algorithmen bereithält. Ausgiebige Hinweise, Links und Ressourcen finden sich auf der Homepage von Prof. Lengauer¹.

Die Vorlesung "Komplexitätstheorie\ wurde von Prof. Lengauer im SS 2000 wieder gelesen; er hat dazu die benutzte Literatur modifiziert, die Vorlesung basiert nun nicht mehr ausschließlich auf dem Reischuk sondern mehr auf Papadimitriou. Die Vorlesung, und damit auch unsere Ausarbeitung, ist also nicht mehr kompatibel und vergleichbar in Hinsicht zu früheren Prüfungen! Auch zu dieser Vorlesung finden sich reichliche Ressourcen auf der Homepage von Prof. Lengauer. Prof. Lengauer hat dabei die Vorlesung so konzipiert, daß sie als "roter Faden\ für eine Lektüre des Buches dient. Die Konsequenz hierbei ist, daß für eine Prüfung eine Abschätzung erfolgen muß, welche Teile des Buches wichtig bzw. relevant sind und welche eben nicht. Auch wir haben uns hier zu einigen Kürzungen entschlossen, insbesondere im Bereich der Logik².

Bei der Nutzung des Skriptes sollte man sich diese Tatsachen stets vor Augen halten!

Gliederung

Die Gliederung dieses Dokuments richtet sich in erster Linie nach der Vorlesung bzw. der Literatur. Dies erleichtert es, die entsprechenden Stellen aufzufinden und nachzulesen. Wir haben jedoch an einigen Stellen den Stoff innerhalb eines Abschnittes neu gegliedert, um ein leichteres Verständnis zu ermöglichen.

Einige Aspekte des behandelten Stoffes haben wir in einen Appendix verschoben, es handelt sich hier um Stoff, der als Basis für eine gewisse Thematik dient und nicht explizit in der Vorlesung behandelt wurde. Dies ist jedoch die Ausnahme und bezieht sich nicht auf Relevantes sondern auf Definitionen, die als Basis für z.B. eine Datenstruktur dienen.

Vorbereitung

Wir halten die A-Prüfung bei Prof. Lengauer für eine der anspruchsvollsten Prüfungen überhaupt! Man sollte keinesfalls den Fehler begehen und diese Prüfung unterschätzen. Selbst eine mehrmonatige intensive Vorbereitung ist keine Garantie für eine gute Note. Vielmehr ist eine optimale Vorbereitung das, was Prof. Lengauer erwartet. Dementsprechend ist es nahezu nicht möglich, eine 1.0 bei ihm zu erreichen; er setzt dazu einiges an Wissen voraus, das über den Stoff der Vorlesung hinausgeht. Dieses Skript soll deshalb nicht als "Lerntext" verstanden werden, der es ermöglicht, ohne Vorkenntnisse den Stoff auswendig zu lernen und die Prüfung (gut) zu bestehen. Es entstand aus der Motivation, die Erkenntnisse, die sich nach einem intensiven Durcharbeiten des Stoffes ergaben, festzuhalten und sie zu konservieren. Das Ziel war es, für den Zeitpunkt des Auswendiglernens eine optimale Stütze zu haben, damit es nicht nötig ist, sich alle Zusammenhänge erneut herleiten zu müssen.

Nutzung

Um zukünftigen Generationen etwas "Wertvolles\ zu hinterlassen, haben wir uns entschlossen dieses Skript zu veröffentlichen. Dazu möchten wir aber auch noch einige Aspekte betonen:

1. Die Nutzung erfolgt auf eigene Gefahr. Wir übernehmen keinerlei Garantie für die Vollständigkeit des Stoffes oder gar die Korrektheit des vorhandenen Stoffes. Tritt eine inhaltliche Diskrepanz zwischen Literatur oder ähnlich guten Quellen und unserem Skript auf, ist in der Regel das Skript zu bemängeln.
    
2. Wir wünschen uns eine freie Nutzung des Skripts. Das heißt im Speziellen, daß wir keine Ansprüche irgendeiner Art erheben. Im Generellen wünschen wir uns außerdem, daß auch nachfolgende Nutzer dieses Skripts keinen kommerziellen Nutzen irgendeiner Art aus diesem Skript ziehen.
    
3. Wir wären erfreut darüber, würde sich jemand finden, der dieses Skript perfektioniert. Insbesondere der Komplexitätstheorie-Teil ist "suboptimal\. Für eine eventuelle Überarbeitung haben wir noch einige Vorschläge:

• Es sollte klargemacht werden, worin eventuelle Änderungen bestehen; z.B. durch geeignete Kommentare in einem Vorwort. Dies soll es Nutzern gestatten, sich über den Stand des Skriptes zu informieren und zu sehen, welche Version vorliegt.
  
   
• Die überarbeitete Version sollte wieder frei und kostenlos zugänglich für alle Interessenten sein, also den hier geschilderten Punkten sinngemäss folgen.
  
   
• Wir möchten nicht, daß zu diesem Skript beitragende Autoren in ihrer Erwähnung übergangen werden.
  
   
• Der LATEX{"Sourcecode\ ist von uns, unter den angegebenen Email-Adressen, erhältlich. Nachfolgende Autoren sollten ihn ebenfalls verfügbar halten.
  
   
• Zukünftige Coautoren möchten wir bitten, uns nach einer Überarbeitung eine Version des Skriptes zukommen zu lassen.

Inhaltsverzeichnis

I Algorithmen 1

1 Graphen    ....   3
1.1 Grundlegende Notationen    ....  3

1.2 Speicherung von Graphen    ....  4
1.2.1 Adjazenzmatrix     ....  4
1.2.2 Knoten-Kanten{Inzidenzmatrix     ....   5
1.2.3 Adjazenzliste     ....  5

1.3 Graphenisomorphie    ....   5
1.4 Planarität     ....   5
1.5 Büme     ....  6

1.6 Zusammenhang     ....  6
1.6.1 Schwacher Zusammenhang    ....   6
1.6.2 Starker Zusammenhang     ....  7
1.6.3 Zweifacher Zusammenhang    ....  7
1.6.4 k-facher Zusammenhang     ....  8

1.7 Depth-First-Search    ....  8
1.7.1 Laufzeit    ....  10
1.7.2 Struktur des DFS    ....  10
1.7.3 Anwendung des DFS     ....  11

1.8 kürzeste Wege in Graphen    ....  14
1.8.1 Historie     ....  14
1.8.2 Beschreibung des Problems    ....  14
1.8.3 Ein generischer Algorithmus    ....  16
1.8.4 Single-Pair     ....  21
1.8.5 Bellmann-Ford-Algorithmus     ....   21
1.8.6 All Pairs    ....  23
1.8.7 Kürzeste Wege mit Adjazenzmatrizen    ....  24

1.9 Minimale Spannbäume    ....  27
1.9.1 Generischer Algorithmus    ....  28
1.9.2 Algorithmus von Boruvka     ....  29
1.9.3 Algorithmus von Prim    ....  29
1.9.4 Algorithmus von Kruskal     ....   29
1.10 Matching in Graphen    ....  30
1.10.1 Bipartite Graphen     ....  33
1.10.2 Ein "Checker" für Maximum Matchings    ....  35

1.11 Netzwerkflüsse    ....  36
1.11.1 Residuales Netzwerk    ....  38

2 Geometrie    ....   44
2.1 Konvexe Hülle    ....   44
2.1.1 Deterministische Konstruktion (per SweepLine)     ....   44
2.1.2 Zufällige inkrementelle Konstruktion    ....  46
2.1.3 Breite einer Punktemenge    ....  46

2.2 Triangulierungen     ....   47
2.2.1 Einige Grundbegriffe      ....    47
2.2.2 Triangulierung per Plane Sweep     ....   48

2.3 Die Delaunay-Triangulierung     ....   48
2.3.1 Der Flipping Algorithmus     ....   48
2.3.2 Voronoi-Diagramme     ....   48

2.4 Segmentschnitte     ....   49
2.4.1 Problembeschreibung      ....   49
2.4.2 Test auf Linienschnitte     ....   50
2.4.3 SweepLine{Algorithmus zu Segmentschnitten      ....   50

II Komplexitätstheorie     ....    51

3 Einleitung      ....   53
3.1 Historie & Motivation     ....    53
3.1.1 Messen von Ressourcen     ....    54

4 Turingmaschinen 56
4.1 Allgemeines     ....    56

4.2 Turingmaschinen als Algorithmen     ....    57
4.3 Linearer Speedup      ....    59

4.4 Aufwand beim Akzeptieren der Palindromsprachen     ....    59
4.4.1 Zeitabschätzung für 1-String Akzeptoren      ....    59
4.4.2 Speicherplatz der Palindromsprache     ....    61

4.5 Die Registermaschine (Random Access Machine)      ....    61
4.5.1 Einführung der RAM      ....    61
4.5.2 Mächtigkeit der RAM      ....     62

4.6 Nichtdeterminismus     ....     63
4.6.1 Intuition     ....    64

5 Unentscheidbarkeit 66
5.1 Halteproblem      ....    66
5.2 Abgeschlossenheit      ....    67
5.3 Rekursive Trennbarkeit     ....     68

6 Aussagenlogik 69
6.1 Erfüllbarkeit & Wahrheit     ....    70
6.2 Logik{Funktionen     ....    70

7 Logik erster Stufe 72
7.1 Syntax      ....    72
7.2 Semantik     ....     73
7.3 Modelle für die Zahlentheorie      ....     73
7.4 Gültige Sätze     ....    73

7.5 Konsistenz der Logik erster Ordnung     ....    74
7.5.1 Mechanisierte Beweistechniken     ....    74
7.5.2 Gödelscher Vollständigkeitssatz     ....    75
7.5.3 Konsequenzen aus Gödels Vollständigkeitssatz     ....    76
7.5.4 Verbindung zwischen Logik & Komplexität bei Graphen     ....    76
7.5.5 Logik 2. Ordnung      ....    77

8 Unentscheidbarkeit in der Logik 79
8.1 Berechnung als zahlentheoretisches Konzept      ....    79

9 Beziehungen zwischen Komplexitätsklassen 81
9.1 Komplexitätsklassen      ....    81
9.1.1 Komplexitätsklassen      ....    82
9.1.2 Komplemente nichtdeterministischer Klassen     ....    82

9.2 Hierarchiesätze     ....    82
9.3 Erreichbarkeitsmethode      ....    83
9.3.1 Nichtdeterministischer Platz     ....    84

10 Reduktion und Vollständigkeit 86
10.1 Reduktion     ....    86

10.2 Vollständigkeit     ....     88
10.2.1 Die Tabellenmethode     ....    88

10.3 Charakterisierung mittels Logik      ....    90

11 NP-vollständige Probleme 91
11.1 Varianten von SAT     ....     91
11.1.1 Komplexität von 2SAT     ....    92

11.2 Varianten von 2SAT     ....    93
11.3 Graphenprobleme      ....    94

11.4 Zahlenprobleme     ....    95
11.4.1 Das KNAPSACK-Problem     ....    96

12 coNP und Funktionsprobleme 98
12.1 PRIMES      ....    99
12.2 Function Problems     ....    99

13 Randomisierte Berechnungen 102
13.1 Randomisierte Algorithmen     ....    102
13.1.1 Symbolische Determinanten     ....    102
13.1.2 Random Walks     ....    103

13.2 Randomisierte Komplexitätsklassen      ....    104
13.2.1 Die Klasse ZPP     ....    105
13.2.2 Die Klasse PP     ....    106
13.2.3 Die Klasse BPP     ....    106

13.3 Zufallsgeneratoren     ....    107
13.3.1 Eingeschränkte Zufallsgeneratoren     ....    108
13.4 Schaltkreiskomplexität     ....    109

14 Kryptographie     ....     112
14.1 Public Key-Kryptographie      ....     113
14.1.1 Kandidaten für One-Way{Funktionen      ....    114
14.2 Kryptographie und Komplexität      ....     114
14.3 Interaktives Beweisen     ....     115
14.3.1 Einführung      ....     115
14.3.2 Klassikation      ....    115
14.4 Zero Knowledge      ....    117
14.4.1 Das Zero Knowledge Protokoll      ....    117

15 Approximierbarkeit      ....    119
15.1 Approximationsalgorithmen      ....    119
15.1.1 Beispiele      ....    120
15.2 Polyzeit{Approximationsschema     ....    126
15.3 Vollständigkeit bei Approximationsalgorithmen     ....    126
15.3.1 Die L-Reduktion     ....    127
15.3.2 Die Klasse MAXSNP     ....    128
15.3.3 Vollständigkeit in MAXSNP     ....    129

16 P vs. NP 130
16.1 Was ist zwischen P und NPC?      ....     130
16.2 Beweise für P 6 =NP?     ....     130

17 Parallelität     ....     132
17.1 Beispiel-Algorithmen      ....    132
17.1.1 Matrizenmultiplikation      ....    132
17.1.2 Graph Reachability     ....    133
17.2 Prä x-Summen{Berechnung      ....    134
17.2.1 Determinanten      ....    134
17.2.2 Max Flow      ....    134
17.3 Parallele Maschinenmodelle      ....     134
17.3.1 Boolesche Schaltkreise      ....    134
17.3.2 Parallele RAMs     ....    135
17.3.3 Uniforme PRAM′s     ....    135
17.3.4 Kritik     ....    136
17.4 Die Klasse NC     ....     137
17.4.1 P{Vollständigkeit      ....    137
17.4.2 RNC      ....    140

18 Logarithmischer Platzverbrauch 141
18.1 L ?=NL     ....    141
18.2 Alternierung     ....    142
18.2.1 Die Klasse DP     ....    144
19 Polynomielle Hierarchie     ....     146

III Anhang     ....     149

A Datenstrukturen     ....     151
A.1 Heaps     ....     151
A.2 Union-Find      ....    151
A.3 Rot-Schwarz{ und 2-3-4{Büme     ....    152
A.3.1 2-3-4{Büme     ....    152
A.3.2 RS-Büme .     ....    152
B Sonstiges      ....    153
B.1 Ackermann-Funktion     ....    153
B.2 Steinerbaum-Problem      ....    153

C Beweis-Ideen      ....    155

C.1 Reduktionen     ....    155
C.2 NL     ....    156
C.3 NL-Vollständigkeit     ....    156
C.4 P-Vollständigkeit      ....    157
C.5 NP-Vollständigkeit      ....    158
C.6 Approximationsalgorithmen      ....    160

Verzeichnisse 162

Abbildungsverzeichnis      ....    162
Listingverzeichnis     ....     164
Literaturverzeichnis     ....     165

[...]

1 http://www.cs.bonn.edu/fgl

2 Im Papadimitriou wird die Logik umfassend aber dafür recht kurz behandelt. Will man den angeschnittenen Stoff in seinem ganzen Umfang verstehen, ist der Besuch einer dedizierten Logik-Vorlesung zu empfehlen.