Komplexitätstheorie

Vortragende: Prof. Carsten Lutz und Dr. Thomas Schneider

K4, Modulbereich Theorie

Di 18-20 MZH 1470
Do 18-20 MZH 1460

Raumverlegung:
Am Di 9.12. abweichend im GW1 C1070

Am 18.12. Ausfall wegen Weihnachtsvorlesung


Kurzbeschreibung

Die Komplexitätstheorie beschäftigt sich mit der inhärenten Komplexität von Berechnungsproblemen: wieviel Zeit (oder andere Ressourcen) benötigt man, um ein gegebenes Problem zu lösen—unabhängig davon, wie clever der Algorithmus ist, den man verwendet? Es geht also um die Grenzen der Berechenbarkeit unter beschränkten Ressourcen. Damit stellt die Komplexitätstheorie eine wichtige Grundlage für den Entwurf und das Verständnis von effizienten Algorithmen dar. Ausserdem versucht sie, die natürliche Neugierde nach dem in der Informatik prinzipiell machbaren zu befriedigen. Die Vorlesung wird sich mit folgenden Themen beschäftigen:

Folien


Übungsaufgaben


Literatur


AG Theorie der künstlichen Intelligenz