Modulcode:	Inf-KompTheo
Englische Bezeichnung:	Introduction to Complexity Theory
Modulverantwortliche(r):	Prof. Dr. Thomas Wilke
Turnus:	unregelmäßig (WS14/15 SS16 WS18/19 SS20)
Präsenzzeiten:	2V 1Ü
ECTS:	4
Workload:	30 Std. Vorlesung, 15 Std. Präsenzübung, 75 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	TI (MSc Inf (15)) WI (MSc Inf (15)) WI (MEd Inf) WPI (MEd Inf) TG (TA) (MSc Inf (2-Fach)) IG (MSc Inf) TG (MSc Inf) MV (MSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-ADS Inf-LogInf Inf-TGI

Kurzfassung:

Eine Einführung in die Komplexitätstheorie mit besonderem Schwerpunkt auf Beziehungen zur Logik.

Lernziele:

Die Studierenden ...

• kennen zentrale Begriffe wie NP-Vollständigkeit und Reduktionen
• können die Komplexität algorithmischer Probleme abschätzen
• kennen die Charakterisierungen zentraler Komplexitätsklassen durch Logiken

Lehrinhalte:

• Komplexitätsmaße: Zeit- und Platzbedarf
• Deterministische und nicht-deterministische Algorithmen
• Reduktionen
• NP-Vollständigkeit (Satz von Cook)
• Polynomialzeithierarchie und PSPACE: Charakterisierungen und vollständige Probleme
• Logische Charakterisierungen von P, der Stufen der Polynomialzeithierarchie und PSPACE

Weitere Voraussetzungen:

• Logik in der Informatik oder mathematische Logik
• Algorithmen und Datenstrukturen
• Grundlagen der Theoretischen Informatik

Prüfungsleistung:

Mündliche Abschlussprüfung

Lehr- und Lernmethoden:

Vorlesung, Frontalübung

Verwendbarkeit:

Literatur:

• Neil Immerman: Descriptive Complexity, Springer 1999
• Michael R. Garey, D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman 1979

Verweise:

Kommentar: