Zu der Vorlesung wird es voraufgezeichnete Videos geben, welche über eCampus zur Verfügung gestellt werden. Mittwochs ab 12:15 Uhr wird es jeweils eine Fragestunde über Zoom geben, in der die Videos besprochen und Fragen gestellt werden können. Die Tutorien finden zweiwöchentlich via Zoom statt.

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.

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