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

Inhalt:

In einigen Anwendungen treten heutzutage so große Graphen auf, dass diese teilweise nicht mehr explizit, d.h. durch Auflistung aller Knoten und Kanten mittels Adjazenzlisten und -matrizen beschrieben werden können, oder selbst klassische polynomielle Graphalgorithmen nicht mehr effizient genug sind. Einen Ausweg bieten implizite Darstellungen die als Heuristiken eingesetzt werden können. Graphen werden über die charakteristische Funktion ihrer Kantenmenge identifiziert, wobei die Knoten der Graphen binär codiert werden, und mittels Datenstrukturen für Boolesche Funktionen wie z.B. OBDDs verarbeitet. Die Behandlung zentraler algorithmischer Probleme auf implizit beschriebenen Graphen erfordert eine andere Herangehensweise als im expliziten Fall. Im Seminar werden implizite OBDD-basierte Graphalgorithmen vorgestellt und analysiert, sowie ihre Grenzen aufgezeigt.

Literatur:

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

Der weitere Ablauf ist der folgende:

• Die Vorbesprechung findet am 12.10.2010 um 8:30 Uhr im Raum 304, 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.

2.8.2010 - Beate Bollig