|
Dozent:
Prof. Dr. Ernst W. Mayr
|
|
|
Bereich:
4 SWS Vorlesung im
Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung
im Gebiet Komplexität
|
|
|
Zeit und Ort:
Di 8:30 - 10:00, Hörsaal N1070
Fr 8:30 - 10:00, Hörsaal N1070
Beginn: 16. Oktober
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Di 16h s.t. - 17:30, Hörsaal 2705
Beginn: 30. Oktober
Übungsleitung: Ulrich Rührmair
Ü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:
Stoff des Informatik Grundstudiums
Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.
|
|
|
Empfehlenswert für:
Erweiterte Kenntnisse im Bereich Komplexität
|
|
|
Inhalt [ps][pdf]
|
|
|
Weiterführende bzw. verwandte Vorlesungen:
Effiziente Algorithmen und Datenstrukturen I
|
|
|
Skript:
Kein Skript.
|
|
|
Literatur:
-
J.L. Balcázar, J. Díaz, J. Gabarró:
-
Structural Complexity I (and II)
EATCS Monographs, Springer-Verlag, begleitend
-
K.R. Reischuk:
-
Einführung in die Komplexitätstheorie
Teubner-Verlag, in Ausschnitten
-
Ch. Papadimitriou:
-
Computational Complexity
Addison-Wesley
-
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi:
-
Complexity and Approximation --- Combinatorial optimization problems and their approximability properties
Springer-Verlag
|
|
|
Sprechstunde:
siehe hier
|
