Seminar

Implizite Graphalgorithmen

Wintersemester 2008/2009

Veranstalterin:	Beate Bollig beate.bolliguni-dortmund.de

Voraussetzung:	Vordiplom
Termin:	wöchentlich jeweils dienstags, 8:30-10:00 Uhr
Beginn:	14.10.2008
Raum:	OH 14, 304

Inhalt:

Bekannte Graphalgorithmen können bei sehr großen Graphen an ihre Grenzen kommen. Selbst Rechenzeiten, die Polynome kleinen Grades sind, können zu groß sein. 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 beschreibbar sind. Alternative Beschreibungsformen, in denen weder Knoten noch Kanten explizit genannt werden, heißen implizit. Die Behandlung zentraler algorithmischer Probleme auf implizit beschriebenen Graphen führt zu neuen Herausforderungen. Im Seminar sollen OBDD-basierte Algorithmen 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:

Interessierte können sich noch bis zum 13.10.2008 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 Zwischenbeprechung 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.10.2008 - Beate Bollig