Komplexitätstheorie

Prof. Peter Bürgisser, Sommersemester 2007


Termine

Vorlesung (V2)
Mo 14:15 - 15:45      E2.304 Peter Bürgisser
Fr 11:15 - 12:45      D1.338

Übung (Ü1)
Fr 14:00 - 15:30      J2.130 Peter Scheiblechner

Beginn
Mo 21. Mai 14:00
Beginn Übung
Fr  1. Juni 14:00
Achtung! Die Vorlesung hat den Umfang V2 + U1, wird jedoch als halbsemestrige 4-stündige Blockveranstaltung in der zweiten Hälfte des Sommersemesters abgehalten werden. Beginn in der Woche vom 21.Mai.

Hinweise: Der Abgabetermin für die Übungsblätter ist ab sofort Montag.
Die Vorlesung fällt am Montag, den 25. 6. 2007 und am Freitag, den 29. 6. 2007 aus. Ein Ersatztermin ist Freitag, der 6. 7. 2007 um 7:30 Uhr im Hörsaal D2.
Es ist nun entschieden, dass wir statt einer Klausur mündliche Prüfungen für die Informatiker anbieten. Alle Prüfungen sollen am Montag, den 10. 9. 2007 oder Dienstag, den 11. 9. 2007 stattfinden. Interessenten melden sich bitte bei Herrn Bürgisser zur genauen Terminabsprache.
Der vorläufige Prüfungsplan befindet sich hier (offline).
Es wird eine zweite Prüfungsrunde um den 10. 10. 2007 geben. Interessenten melden sich bitte zwischen dem 27. 8. 2007 und 7. 9. 2007 im zentralen Prüfungssekretariat an, und kontaktieren zusätzlich Herrn Bürgisser zur genauen Terminabsprache.

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, Reduktionen und Vollständigkeit, Platzkomplexität, Hierarchiesätze, Relativierung, Boolesche Schaltkreise, Uniformität, parallele Komplexitätsklassen, Randomisierung, polynomiale Hierarchie, Permanente.

Inhaltsangabe: [ ps | pdf ]

Formales

Kriterium zum Scheinerwerb (oder qualifizierter Studiennachweis) für Mathematiker
 50% der Punkte in den Übungsaufgaben
Mündliche 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 Algorithmen und Komplexität

Literaturangaben


Übungsaufgaben


Interessante Links


Peter Scheiblechner