In dieser Vorlesung werden wir uns mit der Berechenbarkeit und Komplexität von Problemen beschäftigen. Wir werden zunächst formalisieren, was wir unter einem Problem verstehen, und verschiedene Rechnermodelle kennenlernen. Wir haben im vergangenen Semester effiziente Algorithmen zur Lösung verschiedener Probleme entworfen. In dieser Vorlesung werden wir die Grenzen der Algorithmik kennenlernen und uns damit beschäftigen, für welche Probleme es keine effizienten Algorithmen gibt und welche überhaupt nicht algorithmisch gelöst werden können. Wir lernen mit dem Halteproblem ein nicht entscheidbares Problem kennen und beschäftigen uns mit der “P versus NP”-Frage und NP-schweren Problemen. Anschließend lernen wir noch verschiedene algorithmische Techniken zum Umgang mit NP-schweren Problemen kennen.

Die Vorlesung basiert auf diesem Skript.

Organisatorisches zur Vorlesung, wie z.B. Anmeldung zu den Übungsgruppen, Ausgabe der Übungszettel etc. erfolgt über die Kursseite im eCampus-System.