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 werden:
Komplexitätsklassen und ihre Beziehungen
- Reduktionskonzepte
- NP-vollständige Probleme
- Randomisierte Berechnungen
- Approximationstheorie
Die Vorlesung ist 4-stündig.
Vorlesung:Übung:
Bitte beachten!! Die
erste Vorlesung findet am
30.10.1997 statt.