Seminar Theoretische Informatik (WS 2017/18)
Organisatorisches
- Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7103, Tel. 0271-740-2826)
- Einführungstermin: Montag, 16.10.2017, 14:00-16:00 in Raum H-F 115
- 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 1-2 Vorträge anzubieten.
- Kolmogorov Komplexität (2 Vorträge)
- PAC-Lernalgorithmen
- Randomisierte Algorithmen und Random Walks auf Graphen
- Quanten-Suchalgorithmen
- Grammatik-basierte Kompression und Smallest Grammar Problem
- Streaming-Algorithmen
- Expandergraphen
- Pseudo-Zufallsgeneratoren
Programm
| Datum | Thema | Vortragender | Betreuer | |
| 1. | 5.2.2018, 09:00-10:30 | PAC-Lernalgorithmen (Schöning, Kapitel 10) | Jakob Hippe
|
Markus Lohrey |
| 2. | 5.2.2018, 10:30-12:00 | PAC-Lernalgorithmen II (Schöning, Kapitel 9) | Jonas Schmeck
|
Markus Lohrey
|
| 3. | 5.2.2018, 13:00-14:30 | Grammatik-basierte Kompression (Charikar et al.) | Vanessa Dreier
|
Danny Hucke |
| 4. | 5.2.2018, 14:30-16:00 | Pseudo-Random Generators | Simon Plasger
|
Markus
Lohrey
|
| 5. | 7.2.2018, 14:00-15:30 | Streaming-Algorithmen | Leon Rische | Markus Lohrey |
Literatur
- Uwe Schöning, Gems of Theoretical Computer Science (Thema 1-4)
- Moses Charikar, Eric Lehman, April Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, Abhi Shelat, The smallest grammar problem (Thema 5)
- Lecture Notes on Great Ideas in Theoretical Computer Science, MPI (Thema 6-8)