LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München
english

Untere Schranken (WS 98/99)


* 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


mayr@informatik.tu-muenchen.de