Hasso-Plattner-Institut
  
    • de
 

Vorlesungsankündigung

(Sommersemester 2000)

Komplexitätstheorie

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