Prof. Dr. sc. Christoph Meinel
FB IV - Informatik
Ziel der Komplexitätstheorie ist die Quantifizierung von Computerressourcen (Zeit, Speicherplatz, Hardwareaufwand, ...), die zur algorithmischen Lösung konkreter Probleme bzw. von Problemklassen benötigt werden. In der Vorlesung, die sich an Studenten des Informatik- bzw. Mathematikhauptstudiums wendet und Kernvorlesung für den Bereich der theoretischen Informatik ist, sollen schwerpunktmäßig die folgenden Themenkomplexe behandelt werde
- Komplexitätsklassen und ihre Beziehungen
- Reduktionskonzepte
- NP-vollständige Probleme
- Randomisierte Berechnungen
- Approximationstheorie
Die Vorlesung ist 4-stündig.
Vorlesung:Mo, Mi 8-10 (Raum V301)
Übung:
Mo 10-12 (Raum V301)
Vorlesungsskript
