|
Vorlesungsfolien
Vorlesungsskript
Übungen
|
 Vorlesung
Komplexitätstheorie
Dozent
Stefan Edelkamp
Termine 3.3.- 30.6.2017
Thema
In dieser Vorlesung wird ein algorithmischer Zugang zur
Komplexitätstheorie gelegt und verschiedene Maschinenmodelle
mit den Grenzen ihrer Berechnungskraft verglichen.
Inhaltsverzeichnis
(auf Basis Ingo Wegeners Büchern "Theoretische Komplexität",
"Komplexitättheorie",
"Highlights der Informatik",
Uwe Schönings Buch "Theoretische Informatik - kurzgefasst",
sowie dem KT-Skript von Marian Margraf)
Studienbrief 1: Einleitung und Landau'sche O-Notation
- 1.1 Einleitung und Übersicht
- 1.2 Beweisprinzipien und die reelen Zahlen
- 1.3 O-Notation
Studienbrief 2: Turingmaschinen, churchsche These und Entscheidbarkeit
- 2.1 Registermaschinen und deterministische Turingmaschinen
- 2.2 Techniken zur Programmierung von Turingmaschinen
- 2.3 Simulationen zwischen Turingmaschinen und Registermaschinen
- 2.4 Universelle Turingmaschinen
- 2.5 Die churchsche These
- 2.6 Die Unentscheidbarkeit des Halteproblems
- 2.7 Eigenschaften rekursiver und rekursiv aufzählbarer Sprachen
- 2.8 Die Unentscheidbarkeit des postschen Korrespondenzproblems
Studienbrief 3: Die NP-Vollständigkeitstheorie
- 3.1 Die Komplexitätsklasse P
- 3.2 Nichtdeterministische Turingmaschinen und die Komplexitätsklasse NP
- 3.3 NP-Vollständigkeit
- 3.4 Die NP-Vollständigkeit wichtiger Probleme
- 3.5 Pseudopolynomielle Algorithmen und starke NP-Vollständigkeit
- 3.6 Turing-Reduzierbarkeit, NP-schwierige, NP-einfache und NP-äquivalente Probleme
- 3.7 Eine Komplexitätstheorie für Approximationsprobleme
- 3.8 Eine Komplexitätstheorie für probabilistische Algorithmen
- 3.9 Die Struktur von NP und die polynomielle Hierarchie
Studienbrief 4: PCP Theorie
- 4.1 Logische Charakterisierung von Sprachen
- 4.2 Interaktive Beweise
- 4.3 PCP Theorem
- 4.4 Konsequenz für Approximationsalgorithmen
|
|