Seminar Erweiterte Binary Decision Diagrams

Sommersemester 2003

RWTH Aachen

Veranstalter:	Detlef Sieling

In der Vorlesung Binary Decision Diagrams werden hauptsächlich OBDDs (Ordered Binary Decision Diagrams) untersucht. In dem Seminar sollen erweiterte Varianten von OBDDs vorgestellt werden und in Bezug auf die Darstellungsgröße von Funktionen und auf die Effizienz der Algorithmen mit OBDDs verglichen werden. Neben den Algorithmen sollen auch spezielle Anwendungen, auf die diese Varianten zugeschnitten sind, diskutiert werden. Dazu gehören z.B. die Verifikation von Schaltkreisen und endlichen Automaten, sowie kombinatorische Probleme wie das Zählen von Springerkreisen auf dem Schachbrett.

Die einzelnen Vorträge sollen anhand von Originalarbeiten vorbereitet werden. Die in der Vorlesung Binary Decision Diagrams vorgestellten Methoden und Denkweisen sind hilfreich für das Verständnis der Seminarvorträge, vorausgesetzt werden allerdings nur die grundlegenden Definitionen und Eigenschaften von OBDDs, die am Anfang der Vorlesung behandelt werden und sich auch in Kapitel 5 meines Skripts "Theorie des Logikentwurfs" (http://ls2-www.cs.uni-dortmund.de/lehre/sommer2000/tdl/TdL2000.ps) finden.

17.7.2003 - Detlef Sieling