Seminar Theoretische Informatik (WS 2016/17)
Organisatorisches
- Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7103, Tel. 0271-740-2826)
- Einführungstermin: Dienstag, 18.10.2016, 12:00-14: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-3 Vorträge anzubieten.
- Streaming-Algorithmen
- Algorithmen für Wörter und Bäume mittels algebraischer Techniken
- Randomisierte Algorithmen mittels Polynomen
- Grammatik-basierte Kompression und Smallest Grammar Problem
- Fast Fourier Transformation und Anwendungen
Programm
| Datum | Thema | Vortragender | Betreuer | |
| 1. | Sliding Window Streaming (Aggarwal, Seite 149-157) | Vanessa
Dreier
|
Danny Hucke | |
| 2. | Sliding Window Streaming (Aggarwal, Seite 157-166) | Maik
Bastian
|
Philipp
Reh
|
|
| 3. | Algorithms for regular languages that use algebra (Bojanczyk, Seite 1-5) | Andreas
Wiebe
|
Moses Ganardi | |
| 4. | Algorithms for regular languages that use algebra (Bojanczyk, Seite 6-10) | Andreas
Rosowski
|
Markus
Lohrey
|
|
| 5. | Faktorization Forests (Kufleitner, Seite 1-8) | |||
| 6. | The Smallest Grammar Problem (Charikar et al, Seite 1-6) | |||
| 7. | The Smallest Grammar Problem (Charikar et al, Seite 11-14) | |||
| 8. | Randomisierte Algorithmen und Polynomial Identity Testing (Lohrey, Seite 17-24) | |||
| 9. | Wortproblem in freien Gruppen und logarithmischer Platz (Lipton, Zalcstein) | Simon
Plasger
|
Daniel König | |
| 10. | Schnelle Fouriertransformation (Schöning, 273-284) | |||
| 11. |
Schnelle Multiplikation nach
Schönhagen/Strassen
(Diekert, Kufleitner/Rosenberger, Seite 111-115) |