Seminar
"Theoretische Informatik"
Wintersemester 2005/06
Prof. Dr. Susanne Albers
Zeit und Ort: Fr. 11:00 -13.00 (wöchentlich), Raum SR 01-016, Geb. 101
Anmeldung und Vergabe der Themen erfolgt in der zentralen Informationsveranstaltung:
Termin: Montag, 24.10. (Semesterbeginn), von 16-17.30 Uhr
Vorstellung der Proseminare a 10 Minuten inkl. Fragen + Anmeldung
Ort: Gebäude 101-026
Eine Anmeldung zu dem Proseminar kann natürlich auch weiterhin unabhängig und im Vorfeld von den zentralen Informationsveranstaltungen erfolgen.
Die Teilnehmer lesen in diesem Proseminar selbstständig fachliches Material und stellen es in einem Vortrag von ca. 45 Minuten den anderen Studierenden vor. Zusätzlich ist bis zum Ende der Vorlesungszeit eine schriftliche Ausarbeitung von ca 5-10 Seiten anzufertigen.
Themen:
| Thema | Vortragender | Termin |
| 1. Kuchenteilen | ||
| 2. Karten mischen | ||
| 3. Lateinische Quadrate | David Goergen | 27.01.06 |
| 4. Das Dinitz-Problem | ||
| 5. Museumswächter, Freunde und Politiker | Benjamin Drayer | 10.02.06 |
| 6. Stabile Heirat | ||
| 7. Greedy Algorithmen - Scheduling | ||
| 8. Dynamische Programmierung - Closest pair und ganz. Multiplikation | ||
| 9. Approximationsalgorithmen - Lastbalancierung und Auswahl von Zentren | ||
| 10. Approximationsalgorithmen - Set Cover und Vertex Cover | ||
| 11. Geometrische Algorithmen - Scan-Line-Prinzip, Schnitt von Liniensegmenten und geom. D&C | ||
| 12. Randomisierte Algorithmen | ||
| 13. Parallele Algorithmen |
Literatur:
- 1. Spektrum der Wissenschaft, Dez. 1996, 12ff
- 2. M. Aigner, G. Ziegler. Das Buch der Beweise, 177-187
- 3. M. Aigner, G. Ziegler. Das Buch der Beweise, 203-210
- 4. M. Aigner, G. Ziegler. Das Buch der Beweise, 211-217
- 5. M. Aigner, G. Ziegler. Das Buch der Beweise, 231-234 und 253-255
- 6. J. Kleinberg, E. Tardos. Algorithm Design, 1-12 und 19-25
- 7. J. Kleinberg, E. Tardos. Algorithm Design, 115-131
- 8. J. Kleinberg, E. Tardos. Algorithm Design, 225-234
- 9. J. Kleinberg, E. Tardos. Algorithm Design, 599-612
- 10. J. Kleinberg, E. Tardos. Algorithm Design, 612-624
- 11. T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen, 435-456
- 12. T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen, 653-666
- 13. T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen, 667-684
Weitere Informationen zu dieser Veranstaltung finden Sie demnächst hier.