Seminar Theoretische Informatik (WS 2020/21)
Organisatorisches
- Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7103, Tel. 0271-740-2826)
- Einführungstermin: Montag, 26.10.2020, 14 Uhr via zoom (Zugangsdaten werden per email an die in unisono angemeldeten Studierenden verschickt)
- Die weiteren Termine werden beim Einführungstermin vereinbart.
Themen
In dem Seminar werden ausgewählte Themen aus der theoretischen Informatik behandelt. Wir beabsichten zu jedem der folgenden Themenkomplexe Vorträge anzubieten.
- Kolmogorov Komplexität I(Schöning Kapitel 8 und 9, 2 Vorträge)
- Average-Case Komplexität (Schöning Kapitel 25)
- Quanten-Suchalgorithmen (Schöning Kapitel 26)
- Streaming-Algorithmen und Kommunikationskomplexität (Roughgarden Seite 1-31, 4 Vorträge)
Programm
Datum | Thema | Vortragender | Betreuer | |
1. | 15.2.2021, 9:00 | Kolmogorov Komplexität I (Schöning, Kapitel 8) | Christopher Pack | Markus
Lohrey
|
2. | 15.2.2021, 10:30 | Quanten-Suchalgorithmen (Schöning, Kapitel 26) | Alaa Toni Khouri | Markus
Lohrey
|
3. | 22.2.2021, 10:00 | Kolmogorov Komplexität II (Schöning, Kapitel 9) | Leon Schmid | Markus
Lohrey
|
Literatur
- Uwe Schöning, Gems of Theoretical Computer Science (Thema 1-3)
- Tim Roughgarden, Communication Complexity (Thema 4)