apl. Prof. Dr. Klaus Reinhardt

keine

Studierende sollen durch dieses Modul die folgenden Kompetenzen erwerben:

• Sie können beurteilen, mit welchem Aufwand algorithmische Probleme auf einer Maschine, unabhängig vom konkreten Computer, gelöst werden können.
• Sie verstehen praktische Grenzen der algorithmischen Lösbarkeit von Problemen und können die Komplexität spezieller Probleme einschätzen und klassifizieren.
• Sie sind in der Lage, mit Reduktions- und Simulationstechniken komplexitätstheoretische Untersuchungen anzustellen.
• Sie verstehen abstrakte Zusammenhänge und können selbstständig mit grundlegenden mathematische Methoden umgehen.
• Sie können verschiedene Problemlösestrategien und Beweisverfahren anwenden.

• Das Bestreben der Komplexitätstheorie ist es, grundlegende Aussagen zu treffen, mit welchem Zeit- und Speicherplatzaufwand algorithmische Prozesse auf einer Maschine gelöst werden können. Als Grundlage für geräteunabhängige Untersuchungen dient die Turingmaschine, mit der Komplexitätsabschätzungen mathematisch exakt behandelt werden können. Konsequenzen der Resultate für den praktischen Rechnereinsatz erhält man über den Zwischenschritt der Registermaschine.
• In dem Modul wird untersucht, mit welchem Aufwand ein nichtdeterministscher Algorithmus auf einer deterministischen Maschine simuliert werden kann. Bewiesen werden Enthaltenseinsbeziehungen zwischen verschiedenen Komplexitätsklassen.
• Zusammenfassend betrachtet das Modul die Inhalte

Komplexitätsmaße für Turing- und Registermaschinen
Raum- und Zeitkomplexität sowie bedeutende Komplexitätsklassen
Deterministische und nichtdeterministische Berechnungen
Hierarchien und Lücken bei Komplexitätsklassen
Reduzierbarkeit und vollständige Probleme
Das P-NP-Problem

Vertiefungsmodul für die Vertiefungsrichtung "Algorithmen und Theoretische Informatik" im Masterstudiengang Informatik ab Version 2013.

mindestens 50% der Punkte aus den Übungsblättern zur Komplexitätstheorie

mündl. Prüfung oder Klausur