Einführung in die Komplexitätstheorie: Verständnis der grundlegenden Begriffe, Konzepte, Methoden und Resultate.
Grundlegende Begriffe der Komplexitätstheorie, deterministische und nicht-deterministische Komplexitätsklassen, NP-vollständige Probleme, logarithmischer Speicherbedarf, die Polynomielle Hierarchie, exponentiell schwierige Probleme, Anwendungen.
2 h Eingangstest 30 h Vorlesung (12 Termine inclusive Vorbereitung) 40 h Prüfungsvorbereitung 3 h schriftliche + mündliche Prüfung-----------------------------------------------------------
75 h = 3 Ects
Eingangstest,schriftliche Prüfung,mündliche Prüfung