Dieses Dokument hat das Ziel, den Leser bei der Vorbereitung für die Informatik-Diplomprüfung zu unterstützen.
Dieses Skript basiert auf Literatur und Vorlesungen. Die Vorlesungen wurden an der Universität Bonn von Prof. Dr. Lengauer gehalten. Die Basis für den größten Teil der Vorlesungen bilden dabei ein neues Werk von Mehlhorn und Näher sowie Werke von Reischuk und Papadimitriou.
Auf einen Blick
- Note: 1,7
- Beweisideen zu Reduktionen und Vollständigkeit im Anhang
- Vergleich deterministischer und zufälliger Konstruktionen konvexer Hüllen
- Darstellung des RSA-Kryptoschemas und seiner Schlüssel
- 48 Abbildungen
Inhaltsverzeichnis
I Algorithmen
1 Graphen
1.1 Grundlegende Notationen
1.2 Speicherung von Graphen
1.2.1 Adjazenzmatrix
1.2.2 Knoten-Kanten–Inzidenzmatrix
1.2.3 Adjazenzliste
1.3 Graphenisomorphie
1.4 Planarität
1.5 Bäume
1.6 Zusammenhang
1.6.1 Schwacher Zusammenhang
1.6.2 Starker Zusammenhang
1.6.3 Zweifacher Zusammenhang
1.6.4 k -facher Zusammenhang
1.7 Depth-First-Search
1.7.1 Laufzeit
1.7.2 Struktur des DFS
1.7.3 Anwendung des DFS
1.8 kürzeste Wege in Graphen
1.8.1 Historie
1.8.2 Beschreibung des Problems
1.8.3 Ein generischer Algorithmus
1.8.4 Single-Pair
1.8.5 Bellmann-Ford-Algorithmus
1.8.6 All Pairs
1.8.7 Kürzeste Wege mit Adjazenzmatrizen
1.9 Minimale Spannbäume
1.9.1 Generischer Algorithmus
1.9.2 Algorithmus von Borûvka
1.9.3 Algorithmus von Prim
1.9.4 Algorithmus von Kruskal
1.10 Matching in Graphen
1.10.1 Bipartite Graphen
1.10.2 Ein „Checker“ für Maximum Matchings
1.11 Netzwerkflüsse
1.11.1 Residuales Netzwerk
2 Geometrie
2.1 Konvexe Hülle
2.1.1 Deterministische Konstruktion (per SweepLine)
2.1.2 Zufällige inkrementelle Konstruktion
2.1.3 Breite einer Punktemenge
2.2 Triangulierungen
2.2.1 Einige Grundbegriffe
2.2.2 Triangulierung per Plane Sweep
2.3 Die Delaunay-Triangulierung
2.3.1 Der Flipping Algorithmus
2.3.2 Voronoi-Diagramme
2.4 Segmentschnitte
2.4.1 Problembeschreibung
2.4.2 Test auf Linienschnitte
2.4.3 SweepLine–Algorithmus zu Segmentschnitten
II Komplexitätstheorie
3 Einleitung
3.1 Historie & Motivation
3.1.1 Messen von Ressourcen
4 Turingmaschinen
4.1 Allgemeines
4.2 Turingmaschinen als Algorithmen
4.3 Linearer Speedup
4.4 Aufwand beim Akzeptieren der Palindromsprachen
4.4.1 Zeitabschätzung für 1-String Akzeptoren
4.4.2 Speicherplatz der Palindromsprache
4.5 Die Registermaschine (Random Access Machine)
4.5.1 Einführung der RAM
4.5.2 Mächtigkeit der RAM
4.6 Nichtdeterminismus
4.6.1 Intuition
5 Unentscheidbarkeit
5.1 Halteproblem
5.2 Abgeschlossenheit
5.3 Rekursive Trennbarkeit
6 Aussagenlogik
6.1 Erfüllbarkeit & Wahrheit
6.2 Logik–Funktionen
7 Logik erster Stufe
7.1 Syntax
7.2 Semantik
7.3 Modelle für die Zahlentheorie
7.4 Gültige Sätze
7.5 Konsistenz der Logik erster Ordnung
7.5.1 Mechanisierte Beweistechniken
7.5.2 Gödelscher Vollständigkeitssatz
7.5.3 Konsequenzen aus Gödels Vollständigkeitssatz
7.5.4 Verbindung zwischen Logik & Komplexität bei Graphen
7.5.5 Logik 2. Ordnung
8 Unentscheidbarkeit in der Logik
8.1 Berechnung als zahlentheoretisches Konzept
9 Beziehungen zwischen Komplexitätsklassen
9.1 Komplexitätsklassen
9.1.1 Komplexitätsklassen
9.1.2 Komplemente nichtdeterministischer Klassen
9.2 Hierarchiesätze
9.3 Erreichbarkeitsmethode
9.3.1 Nichtdeterministischer Platz
10 Reduktion und Vollständigkeit
10.1 Reduktion
10.2 Vollständigkeit
10.2.1 Die Tabellenmethode
10.3 Charakterisierung mittels Logik
11 NP-vollständige Probleme
11.1 Varianten von SAT
11.1.1 Komplexität von 2SAT
11.2 Varianten von 2SAT
11.3 Graphenprobleme
11.4 Zahlenprobleme
11.4.1 Das KNAPSACK-Problem
12 coNP und Funktionsprobleme
12.1 PRIMES
12.2 Function Problems
13 Randomisierte Berechnungen
13.1 Randomisierte Algorithmen
13.1.1 Symbolische Determinanten
13.1.2 Random Walks
13.2 Randomisierte Komplexitätsklassen
13.2.1 Die Klasse ZPP
13.2.2 Die Klasse PP
13.2.3 Die Klasse BPP
13.3 Zufallsgeneratoren
13.3.1 Eingeschränkte Zufallsgeneratoren
13.4 Schaltkreiskomplexität
14 Kryptographie
14.1 Public Key-Kryptographie
14.1.1 Kandidaten für One-Way–Funktionen
14.2 Kryptographie und Komplexität
14.3 Interaktives Beweisen
14.3.1 Einführung
14.3.2 Klassifikation
14.4 Zero Knowledge
14.4.1 Das Zero Knowledge Protokoll
15 Approximierbarkeit
15.1 Approximationsalgorithmen
15.1.1 Beispiele
15.2 Polyzeit–Approximationsschema
15.3 Vollständigkeit bei Approximationsalgorithmen
15.3.1 Die L-Reduktion
15.3.2 Die Klasse MAX SNP
15.3.3 Vollständigkeit in MAX SNP
16 P vs. NP
16.1 Was ist zwischen P und NPC?
16.2 Beweise für P ≠ NP?
17 Parallelität
17.1 Beispiel-Algorithmen
17.1.1 Matrizenmultiplikation
17.1.2 Graph Reachability
17.2 Präfix-Summen–Berechnung
17.2.1 Determinanten
17.2.2 Max Flow
17.3 Parallele Maschinenmodelle
17.3.1 Boolesche Schaltkreise
17.3.2 Parallele RAMs
17.3.3 Uniforme PRAM’s
17.3.4 Kritik
17.4 Die Klasse NC
17.4.1 P–Vollständigkeit
17.4.2 RNC
18 Logarithmischer Platzverbrauch
18.1 L = NL
18.2 Alternierung
18.2.1 Die Klasse DP
19 Polynomielle Hierarchie
Verzeichnisse
1. Listingverzeichnis
Zielsetzung und Themen
Das Vorlesungsskript unterstützt die Vorbereitung auf eine theoretische Informatik-Diplomprüfung. Es erläutert algorithmische Verfahren und untersucht, welche Ressourcen ihre Ausführung benötigt und wie sich die Schwierigkeit von Problemen anhand formaler Modelle und Reduktionen einordnen lässt.
- Graphenalgorithmen und algorithmische Geometrie
- Berechenbarkeit, Turingmaschinen und Logik
- Komplexitätsklassen, Reduktionen und Vollständigkeit
- Randomisierung, Kryptographie und Approximation
- Parallele Berechnung und polynomielle Hierarchie
Auszug aus dem Buch
Deterministische Konstruktion (per SweepLine)
Sweep-Richtung = Zeitachse linearer Zuordnung der Punkte, deshalb ist zuvor eine Sortierung notwendig. Zur Konstuktion der konvexen Hülle wird nun mit einer trivialen Hülle – bestehend aus den ersten beiden Punkten – begonnen. Alsdann wird die SweepLinie über die Ebene hinweg bewegt (genauer: springe von einem Punkt zum nächsten), bei Hinzunahme des neuen Punktes wird die konvexe Hülle aktualisiert. Dieser Update-Schritt wird wie folgt durchgeführt:
Sei p der nächste Punkt, auf den die SweepLine gestoßen ist. Zu suchen sind nun die beiden äußeren Tangenten an die konvexe Hülle (siehe Abbildung 2.2): die Hülle ist dergestalt zu modifizieren, daß die Verbindungen zwischen p und diesen Tangentialpunkten t1, t2 hinzugenommen, alle Punkte zwischen diesen beiden dagegen gelöscht werden.
Wie lassen sich nun t1, t2 bestimmen? Sei der Punkte q der letzte Punkt, der in die Hülle aufgenommen worden ist. Offensichtlich ist q von p aus sichtbar. Es ist nun hinreichend, von q aus in beide Richtungen (mit/entgegen Uhrzeigersinn) die Hülle abzugehen und für jeden Punkt zu testen, ob er von p aus sichtbar ist. Die beiden extremen Punkte sind dann genau die Tangentialpunkte.
Der Check, ob ein Punkt von p aus sichtbar ist, läßt sich leicht mit Hilfe des auf Seite 50 beschriebenen Kreuzproduktes realisieren: Ein Punkt q′ ist genau dann nicht mehr sichtbar, wenn ein zuvor getesteter Punkt rechts (bei Test im Gegenuhrzeigersinn) von pq′ liegt.
Zusammenfassung der Kapitel
1 Graphen: Das Kapitel behandelt Graphendarstellungen, Tiefensuche, kürzeste Wege, Spannbäume, Matchings und Netzwerkflüsse.
2 Geometrie: Vorgestellt werden Verfahren für konvexe Hüllen, Triangulierungen und Segmentschnitte.
3 Einleitung: Die Einführung skizziert Berechenbarkeit und die Messung algorithmischer Ressourcen.
4 Turingmaschinen: Turingmaschinen und Registermaschinen dienen als Modelle zur Betrachtung von Zeit, Platz und Nichtdeterminismus.
5 Unentscheidbarkeit: Das Kapitel erläutert das Halteproblem, Abschlusseigenschaften und rekursive Trennbarkeit.
6 Aussagenlogik: Aussagenlogische Ausdrücke, Normalformen, Erfüllbarkeit und boolesche Funktionen werden eingeführt.
7 Logik erster Stufe: Behandelt werden Syntax, Semantik, Modelle und Beweistechniken sowie Zusammenhänge mit Grapheneigenschaften.
8 Unentscheidbarkeit in der Logik: Die Darstellung verbindet zahlentheoretische Axiomensysteme mit der Kodierung von Berechnungen.
9 Beziehungen zwischen Komplexitätsklassen: Hierarchiesätze und Erreichbarkeitsmethoden illustrieren Beziehungen zwischen Zeit- und Platzklassen.
10 Reduktion und Vollständigkeit: An Beispielen wird erläutert, wie Probleme reduziert und Vollständigkeitsbeweise aufgebaut werden.
11 NP-vollständige Probleme: Das Kapitel betrachtet Erfüllbarkeitsvarianten sowie Graphen- und Zahlenprobleme einschließlich des Rucksackproblems.
12 coNP und Funktionsprobleme: Thematisiert werden Komplementklassen, Primzahlfragen und die Berechnung von Lösungen zu Entscheidungsproblemen.
13 Randomisierte Berechnungen: Beispiele zufälliger Algorithmen führen zu randomisierten Komplexitätsklassen und Zufallsgeneratoren.
14 Kryptographie: Öffentliche Schlüssel, Einwegfunktionen und interaktive Beweise werden mit Komplexitätsfragen verknüpft.
15 Approximierbarkeit: Das Kapitel behandelt Näherungsalgorithmen, Approximationsschemata und L-Reduktionen.
16 P vs. NP: Skizziert werden Zwischenklassen und die Rolle von Orakelmaschinen bei möglichen Beweisansätzen.
17 Parallelität: Beispiele paralleler Algorithmen führen zu Schaltkreisen, parallelen Registermaschinen und der Klasse NC.
18 Logarithmischer Platzverbrauch: Im Mittelpunkt stehen logarithmische Platzklassen, Erreichbarkeit und alternierende Maschinen.
19 Polynomielle Hierarchie: Die Hierarchie wird anhand von Orakeln, alternierenden Quantoren und quantifizierten Formeln vorgestellt.
Schlüsselwörter
Graphenalgorithmen, Laufzeitanalyse, konvexe Hülle, Turingmaschine, Berechenbarkeit, Aussagenlogik, Komplexitätsklassen, Reduktion, NP-Vollständigkeit, Randomisierung, Kryptographie, Approximationsalgorithmen, Parallelität, polynomielle Hierarchie
Häufig gestellte Fragen
Worum geht es in der Arbeit?
Das Skript behandelt Algorithmen und theoretische Grundlagen zur Einordnung der Schwierigkeit von Berechnungsproblemen.
Welche Themenfelder stehen im Mittelpunkt?
Schwerpunkte sind Graphen und Geometrie, Berechenbarkeit und Logik sowie Komplexitätsklassen, Randomisierung, Kryptographie und Parallelität.
Welches Ziel verfolgt das Skript?
Es soll bei der Vorbereitung auf die theoretische Informatik-Diplomprüfung unterstützen und erarbeitete Zusammenhänge festhalten.
Welche wissenschaftliche Vorgehensweise wird verwendet?
Das Skript arbeitet mit mathematischen Definitionen, Algorithmen, Laufzeitabschätzungen, Sätzen, Beweisen und Reduktionen.
Was wird im Hauptteil behandelt?
Der Hauptteil führt von konkreten Graphen- und Geometriealgorithmen zu Berechnungsmodellen, Vollständigkeit und weiterführenden Komplexitätsfragen.
Welche Begriffe charakterisieren die Arbeit?
Wichtige Begriffe sind Graphenalgorithmus, Turingmaschine, Komplexitätsklasse, Reduktion, NP-Vollständigkeit und Approximation.
Wie werden kürzeste Wege behandelt?
Die Darstellung erläutert verschiedene Problemvarianten und Verfahren, darunter Dijkstra, Bellmann-Ford und die Berechnung mit Adjazenzmatrizen.
Welche Rolle spielt die konvexe Hülle?
Sie dient als Beispiel der algorithmischen Geometrie und wird unter anderem mit einer deterministischen und einer zufälligen Konstruktion behandelt.
Wie verbindet das Skript Kryptographie und Komplexität?
Es erläutert Einwegfunktionen, öffentliche Schlüssel und interaktive Beweissysteme im Zusammenhang mit Fragen der Berechnungskomplexität.
- Citation du texte
- Christoph Vogt (Auteur), Kai Lingemann (Auteur), 2000, Algorithmen und Komplexitätstheorie, Munich, GRIN Verlag, https://www.grin.com/document/2045