Komplexitätstheorie (Vorlesung)



Diese Vorlesung kann wahlweise als Modul mit 6 LP (Modulnummer FMI-IN0028) bzw. 3 LP (Modulnummer FMI-IN0031) belegt werden. Bei Belegung mit 3 LP ist nur der Stoff der ersten Semesterhälfte prüfungsrelevant.

Modultitel (deutsch)

Komplexitätstheorie - 6 LP (Modulnummer FMI-IN0028)/
3 LP (Modulnummer FMI-IN0031)

Modultitel (englisch)

Computational Complexity

Modul-Verantwortliche/r

Prof. Olaf Beyersdorff

Voraussetzung für die Zulassung zum Modul

keine

Empfohlene bzw. erwartete Vorkenntnisse
  • FMI-IN0001 Algorithmen und Datenstrukturen
  • FMI-IN0005 Automaten und Berechenbarkeit

Art des Moduls (Pflicht-, Wahlpflicht- • Wahlpflichtmodul (TIA; ALG) für den M.Sc. Informatik

oder Wahlmodul)                                • Wahlpflichtmodul (Bereich Informatik) für den M.Sc. Bioinformatik

  • Wahlpflichtmodul (Angewandte Mathematik, Vertiefung Algorithmik, Nebenfach Informatik) für den M.Sc. Mathematik
  • Wahlpflichtmodul für den B.Sc. Wirtschaftswissenschaften, Schwerpunkt IMS
  • Wahlpflichtmodul für den B.A. Ergänzungsfach Informatik

Zusammensetzung des Moduls / Lehrformen (V, Ü, S, Praktikum, …)

6 VÜ

Inhalte

Einführung in die strukturelle Komplexitätstheorie mit den Themen

  • Komplexitätsmaße und -klassen
  • Hierarchiesätze
  • Reduzierbarkeit, Härte und Vollständigkeit

 

Weitere Themen sind beispielsweise

  • Polynomialzeithierarchie und Orakel
  • Komplexitätsklassen für probabilistische Berechnungen
  • Komplexitätsklassen für parallele Berechnungen
  • Approximierbarkeit

Lern- und Qualifikationsziele
  • Vertiefte Kenntnisse in Theoretischer Informatik und der quantitativen Grenzen der Berechenbarkeit.
  • Befähigung zur komplexitätstheoretischen Einordnung konkreter Berechnungsprobleme.
  • Einsicht in die PvsNP Frage und damit verknüpfter Thematiken.

Empfohlene Literatur
  • Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
  • Oded Goldreich: P, NP, and NP-Completeness: The Basics of Computational Complexity, Cambridge University Press, 2010.
  • Christos Papadimitriou: Computational Complexity, Addison Wesley, 1993.

Termine
Vorlesung und Übung finden am Ernst-Abbe-Platz 2 - SR 3325 statt.

Di.,  12:00 – 14:00,
Do., 12:00 – 14:00,

Voraussetzung für die Zulassung zur Übungskriterien, die zum Modulbeginn festgelegt werden Modulprüfung