Hasso-Plattner-Institut
  
    • de
 

Vorlesungsankündigung

(Wintersemester 1997/98)

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 werden:

 Komplexitätsklassen und ihre Beziehungen

  • Reduktionskonzepte
  • NP-vollständige Probleme
  • Randomisierte Berechnungen
  • Approximationstheorie

Die Vorlesung ist 4-stündig.

 


Vorlesung:

  • Di, Do 8-10 (Raum V301 )

Übung:

  • Mi 8-10 (Raum E50)


Bitte beachten!! Die erste Vorlesung findet am 30.10.1997 statt.