Algorithmen und Berechnungskomplexität II

Vorlesungen

Wann Wo Beginn Dozent
Mittwoch 12:15-13:45 CP1-HSZ / Hörsaal 2 19. April 2023 Anne Driemel
Freitag 10:15-11:45 CP1-HSZ / Hörsaal 1 14. April 2023 Anne Driemel

Achtung: Der erste Vorlesungstermin ist am 14.4.2023.

Inhalt

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.

Literatur

Die Vorlesung basiert auf diesem Skript.

Organisation

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


Page Tools