Komplexitätstheorie LAB WiSe 2019/2020

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] 

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


Die Termine zum LAB finden im Raum 3330 am Ernst-Abbe-Platz 2 statt.

Do., 14:00 bis 16:00 und
Fr.,   12:00 bis 14:00.

Template zur "Translationtask" zum Downloaden hier.

LAB-Aufzeichnungen 01 zum Downloaden hier.

LAB-Aufzeichnungen 02 zum Downloaden hier.

LAB-Aufzeichnungen 03 zum Downloaden hier.

LAB-Aufzeichnungen 04 zum Downloaden hier.

LAB-Aufzeichnungen 05 zum Downloaden hier.

LAB-Aufzeichnungen 06 zum Downloaden hier.

LAB-Aufzeichnungen 07 zum Downloaden hier.

LAB-Aufzeichnungen 08 zum Downloaden hier.

Datei "Reachability" zum Downloaden hier.