Binäre Entscheidungsgraphen, hier vor allem der geordnete, reduzierte Entscheidungsgraph (engl. reduced ordered Binary Decision Diagrams, kurz BDDs) sind eine Datenstruktur für Boolesche Funktionen. Boolesche Funktionen spielen im Hardware-Entwurf eine große Rolle. Sie sind aber auch in vielen anderen Bereichen der Informatik wichtig, da es immer dann um sie geht, wenn Objekte endlicher Größe binär kodiert werden. BDDs haben sich in der Praxis bewährt, da sie einen guten Kompromiss zwischen einerseits der Effizienz der darauf basierenden Algorithmen zur Funktionsmanipulation, und andererseits ihrer Kompaktheit darstellen. In der Komplexitätstheorie kann man mit BDDs Betrachtungen zum Speicherbedarf anstellen, aber auch die algorithmische Härte der Optimierung der Variablenordnung ist von Interesse. So kann z.B. von der Wahl der Variablenordnung abhängen, ob das BDD nur lineare oder exponentielle Größe besizt. Letztgenannte Problematik tritt auch bei pfadbezogenen Optimalitätskriterien auf, die in jüngerer Zeit zunehmend an Bedeutung gewonnen haben.
Die Vorlesung vermittelt Kenntnisse zu grundlegenden Repräsentationsformen Boolescher Funktionen. Ziel ist das Verständnis der Algorithmen zu Manipulation und Optimierung von Funktionsgraphen. Die Inhalte umfassen die theoretischen Grundlagen, z.B. untere und obere Schranken für die Größe bzw. Güte von Darstellungen, sowie grundlegende Suchverfahren aus der Künstlichen Intelligenz (KI) wie Hill-Climbing, Branch and Bound oder der generische A*-Algorithmus. Diese werden zur heuristischen und exakten Optimierung der Variablenordnung in BDDs eingesetzt.