Veranstalterin:	Beate Bollig beate.bolliguni-dortmund.de
Voraussetzung:	Vordiplom/Bachelor
Termin:	wöchentlich jeweils dienstags, 10:00-12:00 Uhr
Beginn:	13.4.2010
Raum:	OH 14, E02

Inhalt:

Immer größere Datenmengen in verschiedenen Anwendungen führen zur Entstehung so großer Graphen, dass diese teilweise nicht mehr explizit, d.h. durch Auflistung aller Knoten und Kanten beschrieben werden können, oder selbst lineare klassische Graphalgorithmen nicht mehr effizient genug sind. Implizite Darstellungen, manchmal auch als symbolische Darstellungen bezeichnet, repräsentieren Graphen über die charakteristischen Funktionen ihrer Kantenmengen, wobei die Knoten der Graphen binär codiert werden. Diese können mittels Datenstrukturen für Boolesche Funktionen wie z.B. OBDDs verarbeitet werden. Die Behandlung zentraler algorithmischer Probleme auf implizit beschriebenen Graphen erfordert eine andere Herangehensweise als im expliziten Fall. Im Seminar sollen OBDD-basierte Graphalgorithmen vorgestellt und analysiert werden, sowie ihre Grenzen aufgezeigt werden.

Literatur:

Im Seminar wird Originalliteratur behandelt. Eine gute Einführung in das Thema bietet:

Der weitere Ablauf ist der folgende:

• Die Vorbesprechung findet am 13.4.2010 um 10:15 Uhr im Raum E02 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.

10.2.2010 - Beate Bollig