Homepage
Sitemap
Kontakt




Universität Bremen Universität Bremen Fachbereich 3 Informatik
Home « Lehre « Lehrmaterial


Optimierung von graphenbasierten Funktionsdarstellungen (03-05-H-699.53) 

Veranstalter: Prof. Dr. Rolf Drechsler

Veranstalter: Dr. Rüdiger Ebendt

Die Veranstaltung kann aus gesundheitlichen Gründen ab dem 11. Mai 2006 leider nicht fortgesetzt werden.

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, 2005

Ergänzende Literatur:
  • 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



 Entnehmen Sie Angaben bezügl. Ort und Zeit bitte der Lehrveranstaltungs-Liste der Universität Bremen



[Folien (außer Übungsblätter) nur aus dem Campusnetz erreichbar]


Übungsblatt 1

PDF

Post Script

generiert am 25.04.2006




zurück





English









Zum Seitenanfang Zur Homepage
Zur Sitemap
Kontakt