Komplexitätstheorie

Prof. Peter Bürgisser, Sommersemester 2005


Termine

Vorlesung (V2)
Mo 11:00 - 12:30      D2 Peter Bürgisser

Übung (Ü2)
Mo 9:15 - 10:45      E2.304 Peter Scheiblechner

Beginn
Mo 11. April 11:00
Achtung! Die Vorlesung fällt am 27. Juni sowie 4. und 11. Juli aus. Stattdessen finden folgende Ersatztermine statt 
    Mi, 22. Juni 18:00 - 19:30      D2
    Mi, 13. Juli 11:00 - 12:30      B2
    Fr, 15. Juli 14:00 - 15:30      D2
Die Übung fällt am 4. Juli aus.


Inhalt der Vorlesung

Die Komplexitätstheorie ist eine wichtige Ergänzung der Theorie der Algorithmen.
Ihr Ziel ist es zu verstehen, warum gewisse Berechnungsprobleme schwierig sind und diese anhand ihrer Schwierigkeit zu klassifizieren. Das bekannteste und wichtigste Beispiel ist die Theorie der NP-Vollständigkeit.

Stichworte zum Inhalt

Komplexitätsklassen, Hierarchiesätze, Boolesche Schaltkreise, Reduktion und Vollständigkeit, NP- und PSPACE-vollständige Probleme, P versus NP, untere Schranken für Schaltkreise, Randomisierung.

Inhaltsangabe: [ ps | pdf ]

Formales

Kriterium zum Scheinerwerb (oder qualifizierter Studiennachweis) für Mathematiker
 50% der Punkte in den Übungsaufgaben
Prüfung für Informatiker
Mündliche Prüfung mit Bonuspunkten
Durch aktive Mitarbeit in den Übungen haben Sie die Möglichkeit, ihre
in der abschliessenden Prüfung erreichte Note wie folgt zu verbessern:

    

  •  Erreichen Sie mindestens 50% der Punkte der Übungsaufgaben, so
verbessert sich die Note der Prüfung um 1/3 (ein Notenschritt).

  •  Erreichen Sie mindestens 75% der Punkte der Übungsaufgaben, so
verbessert sich die Note der Prüfung um 2/3 (zwei Notenschritte).

  • Eine Verbesserung über die Note 1.0 (sehr gut) hinaus ist nicht
möglich.



WICHTIG: Eine Verbesserung der Note 5.0 (nicht bestanden)
ist nicht möglich.
Hörerkreis
i6, ma6, ama6
Prüfungsgebiet
Modelle und Algorithmen
Vorkenntnisse
Datenstrukturen und Algorithmen, Einführung in Berechenbarkeit und Komplexität
Weiterführende Veranstaltungen
Komplexitätstheorie II

Literaturangaben


Übungsaufgaben


Interessante Links

Peter Scheiblechner