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.
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¨at
1.5 B¨aume
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 kurzeste 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 Kurzeste Wege mit Adjazenzmatrizen
1.9 Minimale Spannb¨aume
1.9.1 Generischer Algorithmus
1.9.2 Algorithmus von Borˆuvka
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“ fur Maximum Matchings
1.11 Netzwerkflusse
1.11.1 Residuales Netzwerk
2 Geometrie
2.1 Konvexe Hulle
2.1.1 Deterministische Konstruktion (per SweepLine)
2.1.2 Zuf¨allige 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¨atstheorie
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¨atzung fur 1-String Akzeptoren
4.4.2 Speicherplatz der Palindromsprache
4.5 Die Registermaschine (Random Access Machine)
4.5.1 Einfuhrung der RAM
4.5.2 M¨achtigkeit 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 Erfullbarkeit & Wahrheit
6.2 Logik–Funktionen
7 Logik erster Stufe
7.1 Syntax
7.2 Semantik
7.3 Modelle fur die Zahlentheorie
7.4 Gultige S ¨ ¨atze
7.5 Konsistenz der Logik erster Ordnung
7.5.1 Mechanisierte Beweistechniken
7.5.2 G¨odelscher Vollst¨andigkeitssatz
7.5.3 Konsequenzen aus G¨odels Vollst¨andigkeitssatz
7.5.4 Verbindung zwischen Logik & Komplexit¨at bei Graphen
7.5.5 Logik 2. Ordnung
8 Unentscheidbarkeit in der Logik
8.1 Berechnung als zahlentheoretisches Konzept
9 Beziehungen zwischen Komplexit¨atsklassen
9.1 Komplexit¨atsklassen
9.1.1 Komplexit¨atsklassen
9.1.2 Komplemente nichtdeterministischer Klassen
9.2 Hierarchies¨atze
9.3 Erreichbarkeitsmethode
9.3.1 Nichtdeterministischer Platz
10 Reduktion und Vollst¨andigkeit
10.1 Reduktion
10.2 Vollst¨andigkeit
10.2.1 Die Tabellenmethode
10.3 Charakterisierung mittels Logik
11 N P-vollst¨andige Probleme
11.1 Varianten von SAT
11.1.1 Komplexit¨at von 2SAT
11.2 Varianten von 2SAT
11.3 Graphenprobleme
11.4 Zahlenprobleme
11.4.1 Das KNAPSACK-Problem
12 coN P 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¨atsklassen
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¨ankte Zufallsgeneratoren
13.4 Schaltkreiskomplexit¨at
14 Kryptographie
14.1 Public Key-Kryptographie
14.1.1 Kandidaten fur One-Way–Funktionen
14.2 Kryptographie und Komplexit¨at
14.3 Interaktives Beweisen
14.3.1 Einfuhrung
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¨andigkeit bei Approximationsalgorithmen
15.3.1 Die L-Reduktion
15.3.2 Die Klasse MAX SN P
15.3.3 Vollst¨andigkeit in MAX SN P
16 P vs. N P
16.1 Was ist zwischen P und N PC?
16.2 Beweise fur P = N P?
17 Parallelit¨at
17.1 Beispiel-Algorithmen
17.1.1 Matrizenmultiplikation
17.1.2 Graph Reachability
17.2 Pr¨afix-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 N C
17.4.1 P–Vollst¨andigkeit
17.4.2 RN C
18 Logarithmischer Platzverbrauch
18.1 L ?= N L
18.2 Alternierung
18.2.1 Die Klasse DP
19 Polynomielle Hierarchie
III Anhang
A Datenstrukturen
A.1 Heaps
A.2 Union-Find
A.3 Rot-Schwarz– und 2-3-4–B¨aume
A.3.1 2-3-4–B¨aume
A.3.2 RS-B¨aume
B Sonstiges
B.1 Ackermann-Funktion
B.2 Steinerbaum-Problem
C Beweis-Ideen
C.1 Reduktionen
C.2 N L
C.3 N L-Vollst¨andigkeit
C.4 P-Vollst¨andigkeit
C.5 N P-Vollst¨andigkeit
C.6 Approximationsalgorithmen
Zielsetzung & Themen
Dieses Skript unterstützt Informatik-Studierende bei der Prüfungsvorbereitung im Bereich Theorie (A) und vermittelt tiefgehendes Wissen über die Effizienz und Komplexität von Algorithmen sowie deren theoretische Einordnung.
- Grundlagen der Graphentheorie und deren algorithmische Speicherung
- Analyse von Komplexitätsklassen wie P, NP, PSPACE und deren Hierarchien
- Theorie der Berechenbarkeit und Unentscheidbarkeit
- Verfahren zur Approximation NP-schwerer Optimierungsprobleme
Auszug aus dem Buch
Graphenisomorphie
Definition. Zwei Graphen G1 = (V1, E1) und G2 = (V2, E2) heißen isomorph, wenn es bijektive Abbildungen φV : V1 → V2 und φE : E1 → E2 gibt, sodaß φE(e) inzident zu φV (v) ist gdw. e inzident zu v ist.
Aktuelle Algorithmen lösen dieses Problem in O(n log n). Bis heute ist aber kein Beweis für die NP-Vollständigkeit bekannt. Man nimmt an, daß der Isomorphietest in NP aber nicht in NPC liegt.
Für Definitionen von NP, NPC siehe Abschnitt 4.6.1 (Seite 64) bzw. Abschnitt 10.2 (Seite 88).
Zusammenfassung der Kapitel
Graphen: Behandelt grundlegende Definitionen, Speicherungsarten sowie fortgeschrittene Konzepte wie Zusammenhang, Bündelstrukturen, Graphenisomorphie und Suchalgorithmen auf Graphen.
Geometrie: Erläutert algorithmische Ansätze in der Geometrie, wie die Berechnung konvexer Hüllen, Triangulierungen und die Detektion von Segmentschnitten.
Einleitung: Führt in die Komplexitätstheorie ein, definiert das Messen von Ressourcen und erläutert die Historie sowie Motivation der Komplexitätsmessung.
Turingmaschinen: Definiert Turingmaschinen als Basismodell für Algorithmen und untersucht Laufzeit sowie Speicherverbrauch.
Unentscheidbarkeit: Analysiert die Grenzen der Berechenbarkeit, insbesondere anhand des klassischen Halteproblems.
Aussagenlogik: Bietet eine Einführung in die Syntax, Semantik und Normalformen der klassischen Aussagenlogik.
Logik erster Stufe: Vertieft die logischen Grundlagen auf die Prädikatenlogik erster Stufe inklusive ihrer Syntax, Semantik und Modelle.
Unentscheidbarkeit in der Logik: Untersucht die Grenzen der Ableitbarkeit von Aussagen im Vokabular der Zahlentheorie.
Beziehungen zwischen Komplexitätsklassen: Erörtert die hierarchische Einordnung und Beziehungen verschiedener Komplexitätsklassen zueinander.
Reduktion und Vollst¨andigkeit: Erklärt den Begriff der Reduktion und nutzt ihn zur Definition von Vollständigkeitsbegriffen innerhalb von Komplexitätsklassen.
NP-vollst¨andige Probleme: Präsentiert klassische Beispiele für NP-vollständige Probleme, wie 3SAT oder das Independent-Set-Problem.
coNP und Funktionsprobleme: Behandelt die Komplexitätsklasse coNP und die theoretische Fundierung von Funktionsproblemen.
Randomisierte Berechnungen: Untersucht den Einsatz von Zufall in Algorithmen und die resultierenden probabilistischen Komplexitätsklassen.
Kryptographie: Diskutiert die theoretischen Grundlagen kryptographischer Verfahren, insbesondere One-Way-Funktionen und Zero-Knowledge-Protokolle.
Approximierbarkeit: Analysiert Algorithmen für Optimierungsprobleme und deren Güte sowie die Theorie der Approximationsschemata.
P vs. NP: Erörtert das zentrale offene Problem der Informatik und die Grenzen aktueller Beweismethoden.
Parallelit¨at: Untersucht parallele Algorithmen, Schaltkreis-Komplexität und Maschinenmodelle für die parallele Datenverarbeitung.
Logarithmischer Platzverbrauch: Analysiert die Klasse der Probleme, die bei logarithmischem Platzaufwand entscheidbar sind.
Polynomielle Hierarchie: Führt die hierarchische Struktur der Komplexitätsklassen basierend auf alternierenden Turingmaschinen ein.
Schlüsselwörter
Algorithmen, Komplexitätstheorie, Graphentheorie, Turingmaschinen, Unentscheidbarkeit, NP-Vollständigkeit, Randomisierte Algorithmen, Kryptographie, Approximierbarkeit, Parallelität, P vs NP, Schaltkreis-Komplexität, Logik erster Stufe, Reduktion, Polynomielle Hierarchie
Häufig gestellte Fragen
Was ist das Hauptziel dieser Arbeit?
Die Arbeit dient der theoretischen Vorbereitung auf die Informatik-Diplomprüfung im Bereich Theorie, insbesondere bei Prof. Dr. T. Lengauer.
Welche Themenfelder werden abgedeckt?
Das Skript behandelt ein breites Spektrum von algorithmischen Grundlagen über Komplexitätsklassen und Unentscheidbarkeit bis hin zu fortgeschrittenen Themen wie Kryptographie und Approximation.
Was ist die zentrale Forschungsfrage der Komplexitätstheorie?
Ein zentraler Punkt ist die Untersuchung der Beziehung zwischen deterministischer (P) und nicht-deterministischer (NP) Laufzeit und ob P gleich NP ist.
Welche wissenschaftliche Methode wird primär angewandt?
Das Skript nutzt formale Methoden, mathematische Beweise und die Komplexitätsanalyse, um Probleme in Klassen wie P, NP, PSPACE oder IP einzuordnen.
Was behandelt der Hauptteil des Skripts?
Im Hauptteil finden sich detaillierte Analysen von Graphenalgorithmen, Turingmaschinen, logischen Systemen, Reduktionsverfahren für NP-vollständige Probleme sowie Ansätze zur Parallelisierung.
Welche Schlüsselbegriffe charakterisieren die Arbeit?
Zu den prägenden Begriffen gehören Komplexitätsklassen, Reduzierbarkeit, Approximationsalgorithmen und die Untersuchung von Graphen- und Entscheidungsproblemen.
Warum sind PRAMs von Bedeutung?
PRAMs dienen als Modell für parallele Berechnungen, um die Effizienz von Algorithmen unter Berücksichtigung von Arbeit und Zeit besser zu verstehen.
Was ist die Bedeutung von One-Way-Funktionen in der Kryptographie?
One-Way-Funktionen sind Funktionen, die leicht zu berechnen, aber schwer umzukehren sind. Sie bilden die theoretische Grundlage für sichere Verschlüsselungssysteme.
- Quote paper
- Christoph Vogt (Author), Kai Lingemann (Author), 2000, Algorithmen und Komplexitätstheorie, Munich, GRIN Verlag, https://www.grin.com/document/2045