RUB » LMI » Lehre » Komplexitätstheorie WS17/18

Komplexitätstheorie Winter 2018/2019

LVR-Nr: 150 262
Veranstaltung: Komplexitätstheorie
4 std.
IA 1/109 Di 12.00-14.00
IA 1/109 Do 12.00-14.00
Dozent: Hans U. Simon
Übungen: IA 1/109 Do 14.00-16.00 Leonie Ryvkin

           

Die mündlichen Prüfungen finden jeweils am 06. Februar und 26. März statt. Termine bitte frühzeitig mit Frau Ryvkin absprechen, damit die Anmeldungen in den jeweiligen Prüfungsämtern erfolgen können.

   

Die Vorlesungen am 29. und 31. Januar fallen aus, aber der Dozent steht zu den betreffenden Vorlesungszeiten in seinem Büro, IB 3/145, für inhaltliche Fragen zur Vorlesung zur Verfügung.

Kommentar

Die Komplexitätstheorie stellt sich die Aufgabe Berechnungsprobleme anhand des zu ihrer Lösung erforderlichen Verbrauchs an Rechenzeit oder Speicherplatz in Klassen einzuordnen. Probleme von (annähernd) gleicher Komplexität landen dabei in derselben Klasse. Gegenstand der Vorlesung sind hauptsächlich die Komplexitätsklassen zwischen P und PSpace wie zum Beispiel die Klasse NP. Hierbei bezeichnet P die Klasse der in Polynomialzeit und PSpace die Klasse der mit polynomiell beschränktem Speicherplatz erkennbaren Sprachen. NP ist das nichtdeterministische Pendant zu P und bezeichnet die Klasse der nichtdeterministisch in Polynomialzeit erkennbaren Sprachen. Die Klasse enthält eine Vielzahl von grundlegenden Problemen aus verschiedenen Wissenschaftsbereichen. Eine der wichtigsten ungeklärten Fragen der theoretischen Informatik ist, ob die Klassen P und NP überhaupt verschieden sind. In der Vorlesung behandeln wir eingehend die NP-Vollständigkeitstheorie, die sich mit schwersten Problemen innerhalb NP beschäftigt. Weitere Themen sind die polynomielle Hierarchie von Stockmeyer, schwerste Probleme in PSpace und schließlich randomisierte Algorithmen bzw. Approximationsalgorithmen und die jeweils dazu passenden Komplexitätsklassen.

Voraussetzungen

Elementare Grundkenntnisse zu der Thematik, wie sie etwa in der Vorlesung "Theoretische Informatik" vermittelt werden, werden weitgehend vorausgesetzt. (Diese Voraussetzungen sind aber von mathematisch gebildeten Studierenden relativ rasch im Selbststudium herstellbar.) ITS- oder AI-Studierende sollten ein ausgeprägtes Interesse an Theoretischer Informatik (und keine Probleme mit der mathematischen Denkweise) haben.

Materialien

Übungsaufgaben

Skript

Handzettel zur Grenze zwischen P und NP

Definitionen zum Abschnitt über FPT

Abschlusseigenschaft in der polynomiellen Hierarchie

Vorwissen aus der Vorlesung "Theoretische Informatik

Übungsschein

Auf jedem Übungsblatt gibt es pro Aufgabe 4 Punkte. Einen Übungsschein erhält, wer mindestens 50% der Übungspunkte erreicht und einmal eine korrekte Lösung an der Tafel präsentiert hat. Es kann in Gruppen mit bis zu 3 Personen abgegeben werden. Die Übungsblätter erscheinen wöchentlich donnerstags, die Bearbeitungszeit beträgt eine Woche. Die Abgabe erfolgt dann zu Beginn der nächsten Übung bei der Übungsgruppenleiterin.

Prüfungen

Die Prüfungsleistung zum Modul Komplexitätstheorie ist in Form einer mündlichen Prüfung zu erbringen. Hierfür können Sie einen Termin für den 06. Februar oder den 26. März mit Frau Ryvkin absprechen. Bitte sprechen Sie Termine rechtzeitig ab um eine fristgerechte Anmeldung zu gewährleisten. Die Prüfungsanmeldung erfolgt nach den Regeln des für Sie zuständigen Prüfungsamtes.

Kontakt (Raumangaben gültig ab dem 18.10.)