Professur Theoretische Informatik
Ehemalige Professur Theoretische Informatik
Professur Theoretische Informatik 

Komplexitätstheorie

Wintersemester 2003/2004

Vorlesung: Komplexitätstheorie

SWS (V/Ü/P)

2/0/0

Vorkenntnisse

Vordiplom

Semesterempfehlung

5. oder 7.

Inhalt

Die Vorlesung Komplexitätstheorie ist als Fortsetzung der Vorlesung Theoretische Informatik II konzipiert. Folgende Themenkreise werden behandelt:

  • Komplexitätsklassen NP, PSPACE, P
  • Untere Schranken an Laufzeiten
  • Schaltkreiskomplexität.

Die Komplexitätstheorie ist als Herzstück der Theoretischen Informatik anzusehen. Solide Kenntnisse dieses Faches erlauben eine fundierte Einordnung der Probleme der Praxis.