Um mit Booleschen Funktionen arbeiten zu können, benötigen wir eine Darstellungsform oder Datenstruktur, die es einerseits ermöglicht, dass viele Funktionen und insbesondere für Anwendungen wichtige Funktionen kompakt dargestellt werden können, und die andererseits die effiziente Durchführung wichtiger Operationen (z.B. Synthese oder Gleichheitstest) unterstützt. Seit mehr als 10 Jahren werden hierfür vor allem Varianten von sogenanten BDDs (binary decision diagrams) und insbesondere OBDDs (ordered BDDs) eingesetzt. Diese Datenstrukturen lassen sich leicht definieren und führen zu einer Fülle von spannenden Fragestellungen.
Wir werden Algorithmen für den Umgang mit vielen BDD-Varianten vorstellen und analysieren und manchmal zeigen, dass bestimmte Operationen nicht effizient durchführbar sind. Wir vergleichen die verschiedenen Varianten bzgl. der Klasse der mit kleiner Größe darstellbaren Funktionen und der Menge der effizient durchführbaren Operationen. Dabei wird die Darstellungsgröße konkreter, wichtiger Funktionen abgeschätzt, es werden also obere und untere Schranken bewiesen.
Insgesamt erhalten wir im theoretischen Teil ein Zusammenspiel der Gebiete Datenstrukturen, Effiziente Algorithmen und Komplexitätstheorie, wobei die zugehörigen Stammvorlesungen nicht vorausgesetzt werden.
Es wird auch gezeigt, wie Datenstrukturen in der industriellen Praxis eingesetzt werden. Das wichtigste Anwendungsgebiet ist die Verifikation von Hardware (wie hätte der Fehler im Pentium Dividierer vermieden werden können) und weitergehend das Gebiet Model Checking. Hinzu kommen verschiedene CAD-Anwendungen, aber auch Anwendungen bei der Lösung von Optimierungsproblemen wie der Optimierung von Flüssen in Netzwerken.
Die Vorlesung basiert auf dem Buch
Ingo Wegener: Branching Programs and Binary Decision Diagrams - Theory and Applications,
das fertiggestellt ist und wohl noch 1999 erscheint. Nötigenfalls werden den Studierenden Kopien zur Verfügung gestellt.
Das Anwendungspotential von BDD-Techniken zeigt sich daran, dass sie in Dortmund mindestens an den Lehrstühlen 2,4,5,11 und 12 benutzt werden.
Die Übungen werden von mir selbst geleitet. Das Buch enthält eine Sammlung von 193 Übungsaufgaben, die Teilnehmerinnen und Teilnehmer können sich die zu lösenden Aufgaben aus diesem Reservoir frei auswählen. Die Übungsstunden bestehen in der Diskussion der Aufgabenlösungen, um vor allem die Methoden, Lösungswege und Tricks herauszuarbeiten.
Insgesamt ist die Vorlesung unter anderem auch eine gute Vorbereitung auf eine Diplomarbeit. Themen für Diplomarbeiten gibt es für jede der folgenden Ausrichtungen: Entwurf von Datenstrukturen, Algorithmen und ihre Analyse, komplexitätstheoretische Untersuchungen und BDDs in den Anwendungen. Die Diplomarbeiten können theoretisch ausgerichtet sein, aber auch in Richtung einer Anwendung gehen und auch größere Inplementierungsanteile haben.