Seminar

OBDD-basierte Graphalgorithmen

Sommersemester 2009

Veranstalterin:	Beate Bollig beate.bolliguni-dortmund.de

Voraussetzung:	Vordiplom/Bachelor
Termin:	wöchentlich jeweils dienstags, 10:00-12:00 Uhr
Beginn:	21.4.2009
Raum:	OH 14, 304

Inhalt:

Viele Anwendungen erfordern heutzutage die Verarbeitung von immer größeren Datenmengen. Neuere Anwendungen wie die Modellierung technischer Systeme, des Verkehrs und des WWWs führen zu so großen Netzwerken, dass diese nicht mehr explizit, d.h. durch Auflistung aller Knoten und Kanten beschrieben werden können, oder bekannte Graphalgorithmen an ihre Grenzen kommen, da selbst lineare Rechenzeiten nicht effizient genug sind. Implizite Darstellungen repräsentieren Graphen über charakteristische Funktionen ihrer Kantenmengen. Diese können mittels Datenstrukturen für boolesche Funktionen behandelt werden. OBDDs sind eine der gebräuchlichsten Datenstrukturen für boolesche Funktionen in vielen Anwendungen. Die Behandlung zentraler algorithmischer Probleme auf implizit beschriebenen Graphen führt zu neuen Herausforderungen. Im Seminar sollen OBDD-basierte Graphalgorithmen vorgestellt und analysiert werden.

Literatur:

Rafaella Gentilini (2005). Graph Algorithms for Massive Data-Sets. PhD Thesis.

Daniel Sawitzki (2006). Algorithmik und Komplexität OBDD-repräsentierter Graphen. Dissertation (Technische) Universität Dortmund.

Darüberhinaus wird im Seminar weitere Originalliteratur behandelt.

Der weitere Ablauf ist der folgende:

Die Vorbesprechung findet am 19.3.2009 um 14:15 Uhr im Raum 305 0H 14 statt. Interessierte können sich vorab persönlich oder per e-mail bei der Veranstalterin melden.
Die Vorträge sollen anhand der angegebenen Literatur vorbereitet werden.
Die Einarbeitung in die vorgeschlagene und bei Bedarf auch weitere Literatur erfolgt selbstständig, d.h. nicht im Rahmen einer Vorlesung o.Ä. Die Veranstalterin steht aber für inhaltliche Fragen und Fragen zur Vortragsgestaltung zur Verfügung.
Eine in Latex erstellte Zusammenfassung des Vortragsthemas von 3-5 Seiten ist bis spätestens 3 Wochen vor dem Vortrag bei der Veranstalterin abzugegeben. Die Zusammenfassungen werden anschließend an alle Seminarteilnehmerinnen und -teilnehmer verteilt.
Spätestens 2 Wochen vor dem Vortrag findet eine Zwischenbesprechung statt. Die Teilnehmer und Teilnehmerinnen sollten jeweils ein schlüssiges Konzept vorstellen, d.h. die wesentlichen Aussagen der zugrundeliegenden Literatur sollte verstanden sein.
Eine ausreichende Zusammenfassung und eine ausreichende Zwischenbesprechung ist Voraussetzung für einen Seminarvortrag und damit für den Seminarschein. Darüberhinaus ist die aktive Mitarbeit an allen Terminen Voraussetzung für die erfolgreiche Seminarteilnahme.

9.2.2009 - Beate Bollig