|
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.
|
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.
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 ]
- 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
|
- Papadimitriou Computational Complexity, Addison Wesley 1994
- Savage Models of Computation, Exploring the Power of Computation,
Addison Wesley 1998
- Reischuk Einführung in die Komplexitätstheorie, Teubner
Verlag 1990
- Rudich, Wigderson (eds.) Computational Complexity Theory, IAS/Park
City Mathematics Series 10, AMS
- Sipser Introduction to the Theory of Computation, PWS Publishing
Company 1997
- Wegener Komplexitätstheorie. Grenzen der Effizienz von
Algorithmen, Springer 2003.
Peter Scheiblechner