Uni-Logo
Algorithms and Complexity
 

Seminar
"Komplexitätstheorie"
Wintersemester 2006/2007
Prof. Dr. Susanne Albers


Seminar

Die folgenden Formalitäten bilden den Rahmen für unser Seminar.
  • Zeit: Mittwoch, 11-13 Uhr (c.t.)
  • Ort: SR 01-016, Gebäude 101
Bei Anregungen und Fragen zum Seminar wenden Sie sich bitte an Fabian Müller.

Aktuelles

11. November 2006
Der erste Vortrag wird am 13. Dezember 2006 um 11 Uhr (c.t.) stattfinden.
24. Oktober 2006
Erster Seminartermin ist der 8. November 2006.
23. Oktober 2006
Der Raum für die Zentrale Vorstellungsveranstaltung steht nun fest. Es ist Hörsaal 101-00-026.
11. Oktober 2006
Die Zentrale Vorstellungsveranstaltung über alle im Wintersemester angebotenen Seminare wird am Mittwoch, den 25.10. ab 13:00 Uhr stattfinden. Hier können Sie sich auch für das Seminar anmelden.

Inhalt der Veranstaltung

In diesem Seminar werden wir uns hauptsächlich mit struktureller Komplexitätstheorie beschäftigen. Die folgenden Themen werden behandelt:

TerminVortragenderThema
13.12.2006Tenda OkimotoEinführung / Hierarchiesatz
20.12.2006Fabian MüllerRaum versus Zeit
10.1.2007Matthias WestphalSatz von Savitch und
das 2. LBA-Problem
17.1.2007Tobias JacobsWas uns Orakel über P =? NP verraten
24.1.2007Christoph BetzP ≠ NP mit Wahrscheinlichkeit 1
31.1.2007Ahmadullah AminyKolmogoroff-Komplexität
7.2.2007Stefan TeichtweierInteraktive Beweise und Zero Knowledge

Literatur

Die folgende Literatur dient als Quelle für das Seminar.
  • U. Schöning: Perlen der Theoretischen Informatik, BI Wissenschaftsverlag, 1995
  • M. R. Garey, D. S. Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness, Freeman, 1979
  • C. H. Papadimitriou: Computational Complexity, Addison-Wesley, 1994
  • K. W. Wagner: Einführung in die Theoretische Informatik, Springer, 2003