Homepage
Sitemap
Kontakt




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


Optimierung von graphenbasierten Funktionsdarstellungen (03-699.53) 

Veranstalter: Dr. Rüdiger Ebendt

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


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


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


Übungsblatt 01

PDF

Post Script

generiert am 13.04.05
Übungsblatt 02

PDF

Post Script

generiert am 20.04.05
Übungsblatt 03

PDF

Post Script

generiert am 27.04.05
Übungsblatt 04

PDF

Post Script

generiert am 04.05.05
Übungsblatt 05

PDF

Post Script

generiert am 18.05.05
Übungsblatt 06

PDF

Post Script

generiert am 24.05.05
Übungsblatt 07

PDF

Post Script

generiert am 31.05.05
Übungsblatt 08

PDF

Post Script

generiert am 13.06.05
Übungsblatt 09

PDF

Post Script

generiert am 14.06.05
Übungsblatt 10

PDF

Post Script

generiert am 21.06.05
Übungsblatt 11

PDF

Post Script

generiert am 24.06.05




zurück





English









Zum Seitenanfang Zur Homepage
Zur Sitemap
Kontakt