Homepage Sitemap Contact




Home « Studies « Teaching Materials
Sorry, only available in german.


Optimierung von graphenbasierten Funktionsdarstellungen (03-699.53)

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



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



[Folien (ausser Übungsblätter) nur aus dem Campusnetz erreichbar]


Übungsblatt 01



generiert am 13.04.05
Übungsblatt 02



generiert am 20.04.05
Übungsblatt 03



generiert am 27.04.05
Übungsblatt 04



generiert am 04.05.05
Übungsblatt 05



generiert am 18.05.05
Übungsblatt 06



generiert am 24.05.05
Übungsblatt 07



generiert am 31.05.05
Übungsblatt 08



generiert am 13.06.05
Übungsblatt 09



generiert am 14.06.05
Übungsblatt 10



generiert am 21.06.05
Übungsblatt 11



generiert am 24.06.05


  Zur Liste der Lehrveranstaltungen der Universität Bremen




zurück





Deutsch








Sitemap Kontakt

ISMVL2014 DUHDE