Logic and
Theory of
Discrete Systems

Informatik 7

Berechenbarkeit und Komplexität

Vorlesung im Wintersemester 2016/2017

Diese Vorlesung wird auf deutsch gehalten. Es gibt einen L²P-Lernraum sowie ein Übungssystem zu dieser Veranstaltung. Die Assistenten sind unter buk (ät) lists.rwth-aachen.de zu erreichen.

Art Termine/Ort Beginn Veranstalter  
V3

Di 14:15–15:45, Hörsaal Eph (1090|321)
Fr 14:15–15:45, Hörsaal Eph (1090|321)

Einzeldaten im Campus und im
Kalender des L²P-Lernraums

Di, 18. Oktober Schweitzer Campus-Link
Ü2 90-minütige Tutorien
(20 Gruppen zu unterschiedlichen Terminen)
24.–28. Oktober,
je nach Gruppe
Campus-Link

Inhalt

Welche Probleme kann man mit dem Computer lösen? Und welche Probleme kann man effizient lösen? - Das sind die Fragestellungen, um die es in dieser Vorlesung geht. Wir versuchen diese Fragen mit mathematischen Methoden zu beantworten. Dazu müssen wir zunächst Begriffe wie Problem, Computer und Effizienz modellieren. Anschließend werden wir verblüffend klare und weitgehende Aussagen über die (effiziente) Lösbarkeit von Problemen auf Rechnern machen können. Grundlage der Vorlesung sind mathematische Modelle und Methoden. Der Bezug zu realistischen Computern und praktischen Problemen wird aber klar herausgearbeitet. Ein Highlight der Vorlesung ist die NP-Vollständigkeitstheorie, deren Auswirkung auf Theorie und Praxis wohl kaum überschätzt werden kann. Im Einzelnen gliedert sich die Vorlesung wie folgt:

Teil 1: Berechenbarkeit

  • Kapitel 1: Einführung und Grundlagen
  • Kapitel 2: Modellierung von Rechnern und Programmiersprachen
  • Kapitel 3: Nichtberechenbare Probleme

Teil 2: Komplexität

  • Kapitel 4: Die Komplexitätsklassen P und NP
  • Kapitel 5: NP-Vollständigkeit
  • Kapitel 6: Heuristiken und Approximationsalgorithmen für NP-harte Probleme
FaLang translation system by Faboba