Komplexitätstheorie LAB

Modultitel (deutsch)

Komplexitätstheorie LAB

Modultitel (englisch)

Computational Complexity LAB

Modul-Verantwortliche/r

Olaf Beyersdorff, David Sherratt

Empfohlene bzw. erwartete Vorkenntnisse

FMI-IN0001 Algorithmen und Datenstrukturen

FMI-IN0005 Automaten und Berechenbarkeit

Art des Moduls (Pflicht-, Wahlpflicht- oder Wahlmodul)

Wahlpflichtmodul (TIA, ALG) für den M.Sc. Informatik

Wahlpflichtmodul für den B.Sc. Informatik

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

Wahlpflichtmodul (Angewandte Mathematik, Vertiefung Algorithmik, Nebenfach Informatik) für den M.Sc. Mathematik[friedolin4]External link 

Wahlpflichtmodul (Nebenfach Informatik) für den B.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, …)

4 SWS + Praktikum

Leistungspunkte (ECTS credits)

4 LP

Inhalte

Algorithmische Begleitung der Vorlesung Komplexitätstheorie;

Prototyp-Implementierungen von Algorithmen und Konzepten aus der Komplexitätstheorie:

• Simulation von Rechenmodellen: Turing-Maschinen, Schaltkreise etc.
• Hornformeln
• 2-KNF
• Erreichbarkeit in Graphen
• Flüsse in Graphen
• Experimente zur Laufzeit schwerer Probleme
• Reduktionen zwischen NP-vollständigen Problemen
• Testen der Reduktionen zur Lösung schwerer Probleme mit SAT- und QBF-Solvern

Lern- und Qualifikationsziele

Vertiefte Kenntnisse in Theoretischer Informatik und Komplexität

Befähigung zur komplexitätstheoretischen Einordnung konkreter Berechnungsprobleme

Befähigung zum Entwurf und Implementierung von Algorithmen und Reduktionen zwischen Berechnungsproblemen

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