Prof. Dr. M. Dietzfelbinger

Inhalt und Modalitäten

Im Hauptseminar werden vertieft Methoden im Umfeld der Vorlesungen

Randomisierte Algorithmen, Approximationsalgorithmen und Effiziente Algorithmen des vergangenen und des laufenden Semesters erarbeitet.

Basis: Fortgeschrittene (englischsprachige) Lehrbücher.

Folgende Themen sind vorgesehen:

1. Randomisierter Algorithmus für 3-SAT
2. Färben von Kreissegmenten
3. Randomisiertes Packet Routing in Netzwerken
4. Hamiltonkreise in Zufallsgraphen
5. Irrfahrten in Zufallsgraphen
6. Irrfahrten auf Graphen und Cover-Zeiten
7. Minimale Spannbäume in Linearzeit
8. ”Balanced Allocations“: Balancierung durch 2-fache Wahl
9. Randomisierter Algorithmus für das Caching-Problem
10. Nächste Nachbarn in der Ebene
11. Flüsse in Netzwerken: Preflow-Push-Algorithmen
12. Flüsse in Netzwerken: Rundflüsse und Anwendungen
13. Dynamische Programmierung: Fließband-Ablaufplanung und längste gemeinsame Teilstrings
14. Analyse von Approximationsalgorithmen durch Kostenzuweisung (”Pricing“)
15. Approximative Lastbalancierung mittels Linearer Programmierung
    

Nötig sind ausreichende mathematische Kenntnisse.

Ort und Zeit: Kompaktveranstaltung zum Semesterende

Vorbesprechung:
Freitag, 14.10.2005, 10:45 Uhr
Informatikgebäude (”Blechhaus“), Raum 115

Voranmeldung: per email oder Liste im Sekretariat, Raum 305

Information und Material: Webseite des Fachgebiets

Auskunft: jederzeit beim Veranstalter (Raum 306, Tel. 03677/69-2656, email: martin.dietzfelbinger@tu-ilmenau.de)