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: