HOME | CONTACT

Logo Universtity of Bremen
LOGO AGRA | AG Rechnerarchitektur



Group of Computer Architecture / AGRA | Computer Science | Faculty 03 | University of Bremen
Only available in German

Optimierung von graphenbasierten Funktionsdarstellungen (03-699.53)
H |

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.


Literatur:
  • R. Ebendt, G. Fey, R. Drechsler, Advanced BDD Optimization, Springer, nun lieferbar
  • Graphenbasierte Funktionsdarstellung, R. Drechsler, B. Becker, Teubner, 1998
  • C. Meinel, T. Theobald, Algorithms and Data Structures in VLSI Design - Foundations and OBDD Applications, Springer, 1998
  • I. Wegener, The Complexity of Boolean Functions, John Wiley & Sons, 1987

Veranstalter:
Dr. Rüdiger Ebendt

Ort & Zeit:
Vorlesung, Di von 08:00 - 10:00 SpT C4180
Übung, Do von 13:00 - 15:00 MZH 7230


©2023 | Group of Computer Architecture | Contact | Legal & Data Privacy