(Wintersemester 1997/98)

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.

• Di, Do 8-10 (Raum V301 )

Übung:

• Mi 8-10 (Raum E50)