Komplexitätstheorie
- Dozent:
Prof. Dr. Ernst W. Mayr
- Modul:
IN2007,
TUMonline
- Bereich:
4+2 SWS Vorlesung im
Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung
im Gebiet Algorithmen
- Zeit und Ort:
Dienstag, 08:25–09:55, MI HS 2
Freitag, 08:25–09:55, 00.13.009A
-
Übung:
2 SWS Übung zur Vorlesung
Übungsleitung: Chris Pinkau
- Klausur:
Termin: Do 02.08.2012, 08:30 bis 11:30 Uhr
Die angegebenen Zeiten sind die reinen Bearbeitungszeiten. Anwesenheit mindestens 15min vorher.
Als Hilfsmittel ist nur ein beidseitig eigenhändig beschriebenes A4-Blatt mit Notizen zugelassen.
- Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
- ECTS: 8 Punkte
- Voraussetzungen:
Stoff des Informatik Grundstudiums
Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.
Vorlesung Randomisierte Algorithmen vorteilhaft, aber nicht notwendig.
- Empfehlenswert für:
Erweiterte Kenntnisse im Bereich Komplexität
- Folien:
Und hier gibt es alles in einer Datei!
(Hinweise zum Zugriff auf obige Folien)
- Literatur:
-
S. Arora, B. Barak:
-
Computational Complexity --- A Modern Approach
Cambridge University Press, 2009; Textbuch
-
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
