RUB » LMI » Lehre » Komplexitätstheorie WS19/20

Komplexitätstheorie Winter 2019/2020

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

News

  • NEWS NEWS NEWS
  • Die Vorlesungen zu den Terminen 28. Januar und 30. Januar fallen aus, aber der Dozent steht an diesen Tagen zwischen 12:15 und 13:45 Uhr im Buero (IB E3/145) für Fragen oder Kommentare 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

Wochenübersicht

Die Kapitelangaben beziehen sich auf das Skriptum zur Vorlesung.

  • Okt 07 - Okt 11: Kapitel 1 und 2 (Einleitung und grundlegende Begriffe)
  • Okt 14 - Okt 18: Kapitel 3 und 4 (Konstruieren versus Entscheiden, Selbstreduzierbarkeit)
  • Okt 21 - Okt 25: Kapitel 5 (Grenze zwischen P und NPC), 6 (Analyse von eingeschränkten Graphproblemen) und 7 (starke NP-Vollständigkeit), Abschnitte 7.1 und 7.2
  • Okt 28 - Okt 31: Kapitel 7.3 und 8 (Polynomielle versus NP-harte Approximation), Abschnitte 8.1-8.3
  • Nov 04 - Nov 08: Kapitel 8.4 und 8.5, sowie Kapitel 9 Parametrisierte Komplexität, 10 (Zwischenbilanz zum Thema ``P versus NP'' und 11 (Struktur von NP)
  • Nov 11 - Nov 15: Kapitel 12 (Isomorphe, spärliche und dichte Sprachen) und 13 (Relativierung der ``P versus NP'' Frage)
  • Nov 18 - Nov 22: Kapitel 14 (Beziehungen zwischen den Komplexitätsklassen) und 15 (Hierarchiesätze)
  • Nov 25 - Nov 29: Kapitel 16 (Die Klasse NL) und Abschnitt 17.1 von Kapitel 17 (PSpace-vollständige Probleme)
  • Dez 02 - Dez 06: Rest von Kapitel 17 (PSpace-vollständige Probleme), Kapitel 18 (Polynomielle Hierarchie) und Abschnitt 19.1 von Kapitel 19 (Satz von Celia Wrathall)
  • Dez 09 - Dez 13: Rest von Kapitel 19 (Satz von Celia Wrathall) und Abschnitt 20.1 von Kapitel 20 (Uniforme versus nicht-uniforme Komplexität)
  • Dez 16 - Dez 20: Rest von Kapitel 20 (Uniforme versus nicht-uniforme Komplexität)
  • Jan 06 - Dez 10: Kapitel 21 (Probabilistische Komplexitätsklassen) mit Ausnahme von Lemma 21.11, Satz 21.12 und Abschnitt 21.6
  • Jan 13 - Dez 17: Abschnitte 1.1-1.3 aus Kapitel 1 (Fixed-Parameter Tractability)) des Lehrbuchs ``Parameterized Complexity Theory'' der Autoren Jörg Flum und Martin Grohe.
  • Jan 20 - Dez 24: Abschnitte 1.4 und 1.6 aus Kapitel 1 (Fixed-Parameter Tractability)) sowie Abschnitt 9.1 aus Kapitel 9 (Kernelization and Linear Programming Techniques) des Lehrbuchs ``Parameterized Complexity Theory'' der Autoren Jörg Flum und Martin Grohe.

Handzettel zur Grenze zwischen P und NP

Ü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 09. April mit Frau Ryvkin absprechen. Bitte Sprechen Sie die 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. Durch Bearbeiten der Übungsaufgaben können Sie einen Prüfungsbonus erwerben: Studierende, die mindestens 50% der Übungspunkte erreicht haben, erhalten einen Notenbonus von 4% bzw. einer Drittelnote für die mündliche Prüfung.

Kontakt