|
Dozent:
Prof. Dr. Ernst W. Mayr
|
|
|
Bereich:
2 SWS Vorlesung im
Bereich Informatik III (Theoretische Informatik)
Vertiefende Vorlesung
im Gebiet Komplexität
|
|
|
Zeit und Ort:
Do 8:30 - 10:00, Hörsaal 1180
Beginn: 5. November
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Mi 8:30 - 10:00, Raum S2225
Beginn: 11. November
Übungsleitung: Volker Heun
Übungsschein: Einen Schein erhält, wer
mindestens 40% der Punkte zu den Hausaufgaben erreicht und
erfolgreich an der Semestralklausur teilnimmt.
|
|
|
Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
|
|
|
Voraussetzungen:
Vorlesung Komplexitätstheorie vorteilhaft, aber nicht notwendig.
|
|
|
Empfehlenswert für:
Erweiterte Kenntnisse im Bereich Komplexität
|
|
|
Inhalt:
Ein sehr interessantes, aber auch schwieriges Gebiet der
Algorithmentheorie ist das Zeigen unterer Schranken für
die Zeit- oder Platzkomplexität von Problemen. In dieser
Vorlesung werden verschiedene bekannte Techniken zum Beweisen
unterer Schranken vorgestellt und anhand paradigmatischer
Beispiele veranschaulicht.
- Einleitung, Übersicht
- Zweck der Vorlesung
- Literatur
- Techniken für Untere Schranken
- Modelle
- Einige Notationen
- Einige Platz- und Zeitschranken für Turingmaschinen
- Eine quadratische Zeitschranke für 1-Band-TMs
- Ein Gap-Theorem für kleinen deterministischen Platz
- Gap-Theorem für 1-Band-Turingmaschinen
- Hierarchien
- Allgemeiner Hierarchiesatz
- Zeithierarchien
- Platzhierarchie
- Nichtdeterministische Hierarchiesätze
- Platz vs. Zeit
- 1-Band Turingmaschinen
- Ein Spiel auf Graphen
- Konstruktion von Berechnungsgraphen
- Boolesche Schaltkreise
- Grundlagen
- Asymptotische Schranken
- Probabilistische Methoden
- Die Klasse AC0
- Schaltkreise geringer Tiefe für Parität
- Håstad's untere Schranke
- Exponentielle untere Schranke für Parität
- Eine algebraische Methode (Razborov)
- Zusammenfassung und Ausblick
|
|
|
Weiterführende bzw. verwandte Vorlesungen:
EinfÏhrung in die KomplexitÌtstheorie
|
|
|
Skript:
Kein Skript.
|
|
|
Literatur:
-
K.R. Reischuk:
-
Einfhrung in die Komplexittstheorie
B.G. Teubner, 1990
-
J. HÔstad:
-
Computational limitations of small-depth circuits
The MIT Press: Cambridge(MA)-London, 1987
|
|
|
Sprechstunde:
siehe hier
|
