Prof. Dr. Thomas Schneider,
Dr. Jean Christoph Jung
K4, Modulbereich Theorie, Profile SQ, KIKR
Di 12–14 MZH 6190
erste Sitzung Di. 2.4., 12:15 Uhr
Do 14–16 MZH 6340
Die Komplexitätstheorie beschäftigt sich mit der inhärenten Komplexität von Berechnungsproblemen: wie viel 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. Außerdem versucht sie, die natürliche Neugierde nach dem in der Informatik prinzipiell Machbaren zu befriedigen.
Der Kurs kombiniert mehrere Lehrformen und legt den Schwerpunkt auf die eigenständige Erarbeitung eines wissenschaftlichen Themas durch die Teilnehmenden. In den ersten 4 Wochen finden Vorlesungen und Übungen statt, in denen die Grundlagen vermittelt werden. Danach bearbeiten die Teilnehmenden ein eigenes weiterführendes Thema, zu dem sie in den letzten ca. 2 Semesterwochen eine eigene Vorlesungseinheit mit kurzer Übung halten werden. Dabei werden sie durch die Dozenten betreut. In der Mitte des Semesters wird es zwei weitere Vorlesungseinheiten durch die Dozenten geben.
vorläufiger Ablaufplan:
| Di. 2.4. | Vorlesung, Organisatorisches | |
| Do. 4.4. | Vorlesung | |
| Di. 9.4. | Vorlesung | |
| Mi. 10.4. | Abgabe Übungsblatt 1 | |
| Do. 11.4. | Übung | |
| Di. 23.4. | Vorlesung, Vorstellung der weiterführenden Themen | |
| Do. 25.4. | Vorlesung | |
| Di. 30.4. | Vorlesung, Wahl der weiterführenden Themen | |
| Mi. 1.5. | Abgabe Übungsblatt 2 | |
| Do. 2.5. | Übung | |
| Mai, Juni | selbstständige Bearbeitung der weiterführenden Themen | |
| ca. Anfang Juni | 2 weitere Vorlesungen | |
| ca. 2.7.–11.7. | Präsentation der weiterführenden Themen durch die Teilnehmenden |
Die Vorlesung wird folgende grundlegende Themen vermitteln:
Als mögliche weiterführende Themen sind angedacht: