Binary Decision Diagrams (BDDs) sind eine graphische Darstellung von booleschen Funktionen. Sie werden in Programmen für den Hardwareentwurf als Datenstruktur für die Speicherung und Manipulation von booleschen Funktionen, aber auch in der Komplexitätstheorie zur Untersuchung der Ressource Speicherplatz benutzt. Aufgrund ihrer Anwendbarkeit werden sie inzwischen bereits in der Vorlesung Datenstrukturen bzw. DAP 2 behandelt.

Die Vorlesung beginnt mit einer Wiederholung von OBDDs (Ordered Binary Decision Diagrams). Zusätzlich werden gegenüber der Vorlesung Datenstrukturen bzw. DAP 2 weitere Verfeinerungen der Algorithmen vorgestellt und es wird untersucht, für welche Operationen es vermutlich keine effizienten Algorithmen gibt. Eine weiteres wichtiges Problem besteht darin festzustellen, welche Funktionen mit kleinen OBDDs dargestellt werden können und welche nicht.  Während für den Nachweis, dass es kleine OBDDs für eine Funktion gibt, genügt, ein kleines OBDD anzugeben, ist der Nachweis, dass eine Funktion keine kleinen OBDDs hat, schwieriger, da man prinzipiell alle OBDDs für die Funktion betrachten muss.  Es stellt sich heraus, dass OBDDs für viele wichtige Funktionen zu groß sind. Es wird daher die Frage untersucht, ob Erweiterungen der OBDDs zu kleineren Darstellungen für diese Funktionen führen und welche Operationen auf booleschen Funktionen von den Erweiterungen unterstützt werden. Zu diesen Erweiterungen gehören Varianten mit schwächeren Anforderungen an die Variablenordnung wie auch nichtdeterministische und randomisierte Varianten von OBDDs.

Die Untersuchung von OBDDs und ihren Erweiterungen verwendet zugleich Methoden aus verschiedenen Bereichen der theoretischen Informatik. Dies sind Methoden zum Entwurf effizienter Algorithmen oder zum Beweis, dass solche Algorithmen vermutlich nicht existieren. Weiterhin wird die Kommunikationskomplexität als wichtigste Methode zum Beweis von unteren Schranken für den Ressourcenbedarf von Berechnungen behandelt. Nichtdeterministische Algorithmen sind in der Regel nicht praktikabel. Dagegen gibt es Varianten von nichtdeterministischen OBDDs, die auch in der Praxis eingesetzt werden. In der Vorlesung werden auch die Auswirkungen der theoretischen Ergebnisse auf die Praxis diskutiert.

Skript

Das Skript steht als Postscript, komprimiertes Postscript und PDF zur Verfügung. Es gibt außerdem eine Fehlerliste (Postscript, PDF).

Übungen

Inhalt der Vorlesungen

• 15.10.2003: Einführung (Aachen-Skript bis S. 5)
• 16.10.2003: Anforderungen an Datenstrukturen für boolesche Funktionen, Zusammenhang zwischen BDDs und nichtuniformen Berechnungen, Definition und Beispiele für OBDDs (Aachen-Skript bis S. 10)
  
• 22.10.2003: Reduktionsregeln und Struktursatz für OBDDs (Aachen-Skript bis S. 14)
• 23.10.2003: Reduktionsalgorithmus (Aachen-Skript S. 15 f.), linearer Reduktionsalgorithmus, symmetrische Funktionen (Aachen-Skript, S. 16), die Funktion Index, Def. nice, ugly etc. (bis Seite 2)
• 29.10.2003: Die Funktionen ISA und CKDSA, das Variablenordnungsproblem bei geg. Schaltkreis (Aachen-Skript, S. 21) und bei geg. Wertetabelle (Algorithmus von Friedman und Supowit)
• 30.10.2003: Rechenzeit- und Speicherplatzbedarf des Algorithmus von Friedman und Supowit, NP-Härte von MinSBDD (Aachen-Skript S. 21-23)
• 5.11.2003: Die Swap-Operation, lokale Suche und Sifting (Aachen-Skript S. 24), das Variablenordnungsproblem für partiell symmetrische Funktionen
• 6.11.2003: Operationen auf OBDDs: Auswertung, Erfüllbarkeit, Erfüllbarkeit-Anzahl, Erfüllbarkeit-Alle, Äquivalenztest, Synthese, m-äre Synthese, Ersetzung durch Konstanten und Funktionen (Aachen-Skript S. 24-31)
• 12.11.2003: Quantifizierung, Redundanztest, worst-case-Beispiele für die Operationen (Aachen-Skript S. 31-33), Operationen Exchange, Jump-up, Jump-down
• 13.11.2003: Umordnen von OBDDs, ZBDDs: Definition, Motivation, Reduktionsregeln
• 19.11.2003: ZBDDs: Struktursatz, Größenvergleich mit OBDDs, Synthese, Ersetzen durch Konstanten
  
• 20.11.2003: OFDDs: Reed-Muller-Zerlegung, Definition, Beispiele, Auswertung, Reduktionsregeln, tau-Operator, Zusammenhang zwischen vollständigen OBDDs und OFDDs
• 26.11.2003: Eigenschaften den tau-Operators, Struktursatz für OFDDs, OFDDs für symmetrische Funktionen sowie für 1cl_n,3 und parity-cl_n,3, Synthese für OFDDs
• 27.11.2003: Ersetzen durch Konstanten für OFDDs, Parity-OBDDs: Definition, Auswertung, Umformung von OBDDs und OFDDs in Parity-OBDDs, Beispielfunktionen xy+z, INDEX
  
• 3.12.2003: Parity-OBDDs: Diskussion des Variablenordnungsproblems, Hinzufügen und Entfernen von Linearkombinationen, Vektorräume V^f_k und V^G_k, Struktursatz
• 4.12.2003: Parity-OBDDs: Beweis des Struktursatzes, Algorithmus zur Minimierung der Anzahl der Knoten, Parity-Synthese, Erfüllbarkeit-Anzahl, Äquivalenztest
• 10.12.2003: Synthese von Parity-OBDDs, Einführung in nichtdeterministische und randomisierte OBDDs (mit Ergänzungen vom 11.12.), Partitioned BDDs: Definition, Beispiel ISA
• 11.12.2003: PBDD für ISA mit zwei Teilen, Eindeutigkeit von PBDDs, Synthese, Erfüllbarkeitsprobleme, Ersetzen durch Konstanten; Fehlerarten von randomisierten OBDDs
• 17.12.2003: Randomisierte OBDDs: Auswertung, Probability Amplification, Fingerprinting am Beispiel der Ungleichheitsfunktion
• 18.12.2003: Randomisierte OBDDs für den Graphen der Multiplikation, NP-Härte des Erfüllbarkeitsproblems. FBDDs: Beispiele ISA und INDEX-EQ
• 7.1.2004: FBDDs: Minimierung, Test, ob f AND g=0, Arithmetisierung von booleschen Berechnungen
  
• 8.1.2004: Äquivalenztest für FBDDs, Graphgesteuerte BDDs: Definition, Synthese, Ersetzen durch Konstanten, Einführung und Motivation für den Beweis unterer Schranken
• 14.1.2004: Beweis unterer Schranken für BDDs mit Zählargumenten und mit der Neciporuk-Methode, Einführung in Kommunikationskomplexität, Protokollbäume
• 15.1.2004: Kommunikationsmatrizen, Rechtecke, Rangmethode, Unterscheidungsmengen, Anwendung von Kommunikationskomplexität zum Beweis unterer Schranken für die BDD-Größe
• 21.1.2004: Einweg-Kommunikationskomplexität, Einweg-Unterscheidungsmengen, Anwendung auf die INDEX-Funktion, Beweis unterer Schranken für die OBDD-Größe für beliebige Variablenordnungen, Anwendung auf die HWB-Funktion
• 22.1.2004: Nichtdeterministische Kommunikationskomplexität und ihre Anwendung zum Beweis unterer Schranken für die Größe von nichtdeterministischen OBDDs am Beispiel der Funktion INDEX-EQ
• 28.1.2004: Beweis unterer Schranken für die Größe von deterministischen FBDDs für parity-cl_n,3 und die Größe von nichtdeterministischen FBDDs für PERM_n
• 29.1.2004: Beweis einer unteren Schranke für die Größe von PBDDs für INDEX-EQ, Definition von impliziten Graphdarstellungen, Berechnung der Anzahl der Kanten und der Anzahl der Dreiecke als Beispiele für einfache Operationen, Diskussion der Komplexität von GAP und der Folgen auf die Anwendbarkeit von impliziten Graphdarstellungen.
• 4.2.2004: PSPACE-Vollständigkeit von GAP für implizite Graphdarstellungen, Def. Flussmaximierung, flussvergrößernde Wege, Niveaunetzwerk
  
• 5.2.2004: Def. Sperrfluss, Beispiel für Flussmaximierung mit Hilfe von Sperrflussberechnungen, Algorithmus zur Berechnung von implizit dargestellten Niveaunetzwerken und implizit dargestellten Sperrflüssen.