Proseminar: Effiziente Datenstrukturen für große Mengen
» Diese Veranstaltung wird auf deutsch gehalten.
Proseminar im Wintersemester 2003/2004
| Art | Termine/Ort | Beginn | Veranstalter |
|---|---|---|---|
| Ü2 | Di 16:00 - 17:30 AH II | Di 14.10.2003 | Thomas, Löding, Penner, Wallmeier |
Inhalt
Die Datenmengen, die man heute in der Systemverifikation oder im World Wide Web verwalten muss, lassen sich nur handhaben, wenn man neben hoher Rechnerleistung auch effiziente Datenstrukturen verwendet.
In diesem Proseminar werden, aufbauend auf der Vorlesung 'Algorithmen und Datenstrukturen', fortgeschrittene Datenstrukturen zur Darstellung von Mengen und Booleschen Funktionen erarbeitet.
Der erste Teil des Proseminars widmet sich den OBDDs (ordered binary decision diagrams), die eine wichtige Grundlage der formalen Verifikation von Systemen sind.
Im zweiten Teil des Proseminars studieren wir Datenstrukturen, die mehr auf der Vorlesung 'Algorithmen und Datenstrukturen' aufbauen. Darunter fallen z.B. Rot-Schwarz-Bäume, Binomial Heaps und Fibonacci Heaps.
Vorträge
Die Folgende Tabelle gibt eine vorläufige Übersicht über die geplanten Vorträge und Termine.Teil I: OBDDs
| Thema | Termin | Vortragende | Betreuer |
| Grundlagen zu Booleschen Funktionen | Di, 14.10.2003 | Patrice Nebo | Christof Löding |
| Einführung von OBDD's, Beispiele, Reduktionsalgorithmus | Di, 21.10.2003 | Hongyan Zhu Min Su |
Christof Löding |
| Binäre Verknüpfungen und Äquivalenztest | Di, 28.10.2003 | Christoph Becker Sven Hendriks |
Christof Löding |
| Implementierung von OBDD's | Di, 4.11.2003 | Maria Donner Lars Bücken |
Nico Wallmeier |
| Zusammenhang Variablenordung und OBDD-Größe | Di, 11.11.2003 | Sebastian Dahlen | Nico Wallmeier |
| Dynamisches Umordnen und Exakte Minimierung | Di, 18.11.2003 | entfällt | Nico Wallmeier |
Teil II: Fortgeschrittene Datenstrukturen
| Thema | Termin | Vortragende | Betreuer |
| Rot-Schwarz-Bäume | Di, 25.11.2003 | Yanhuai Peng Lei Wang |
Volker Penner |
| Anreichern von Datenstrukturen am Beispiel von Rot-Schwarz-Bäumen |
Di, 2.12.2003 | Christoph Emonds Abu Ahmad Qassem |
Volker Penner |
| Universelles und perfektes Hashing | Di, 9.12.2003 | Thostern Suckow-Homberg Katrin Landwehr |
Volker Penner |
| Amortisierte Komplexitätsanalysen | Di, 16.12.2003 | Heiko Ronsdorf Anis Larabi |
Volker Penner |
| Binomial Heaps | Di, 13.1.2004 | Anke Hilgers Michaela Slaats |
Volker Penner |
| Fibonacci Heaps | Di, 20.1.2004 | Paul Bütow Florian Bütow |
Volker Penner |
| Datenstrukturen für disjunkte Mengen | Di, 27.1.2004 | David Thesing Dominic Decarolis |
Volker Penner |
Literatur
- Teil I, OBDDs: Christoph Meinel und Thorsten Theobald. Algorithmen und Datenstrukturen im VLSI-Design. Springer-Verlag.
- Teil II, Fortgeschrittene Datenstrukturen: Coremen, Leiserson, Rivest, Stein. Introduction to Algorithms. MIT Press.