Seminar Theoretische Informatik (WS 2019/20)
Organisatorisches
- Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7103, Tel. 0271-740-2826)
- Einführungstermin: Montag, 7.10.2019, 14:00-16:00 in Raum H-C 6336/37
- 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 (2 Vorträge)
- Average-Case Komplexität
- Quanten-Suchalgorithmen
- Streaming-Algorithmen und Kommunikationskomplexität (3 Vorträge)
- Grammatik-basierte Kompression und Smallest Grammar Problem (2 Vorträge)
Programm
Alle Vorträge finden im Raum H-A 7101 statt.
| Datum | Thema | Vortragender | Betreuer | |
| 1. | 5.2.2020, 09:00-10:30 | Kolmogorov Komplexität (Schöning, Kapitel 8) | Sven Meyer | Markus
Lohrey
|
| 2. | 5.2.2020, 10:30-12:00 | Kolmogorov Komplexität (Schöning, Kapitel 9) | Leon Rische | Markus
Lohrey
|
| 3. | 5.2.2020, 13:30-15:00 | Quanten-Suchalgorithmen (Schöning, Kapitel 26) | Nathanael Stöhr | Markus
Lohrey
|
Literatur
- Uwe Schöning, Gems of Theoretical Computer Science (Thema 1-3)
- Tim Roughgarden, Communication Complexity (Thema 4)
- Moses Charikar, Eric Lehman, April Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, Abhi Shelat, The smallest grammar problem (Thema 5)