Modulcode:	Inf-BDD
Englische Bezeichnung:	Binary Decision Diagrams
Modulverantwortliche(r):	Prof. Dr. Rudolf Berghammer
Turnus:	unregelmäßig (SS12 SS13)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	60 Std. Vorlesung, 30 Std. Präsenzübung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	WI (BSc Inf (15)) WIAlg (BSc Inf) WI (MEd Inf) WPI (MEd Inf)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Binäre Entscheidungsdiagramme, insbesondere wenn sie geordnet und reduziert sind, bilden eine sehr effiziente Datenstruktur zur Implementierung von Booleschen Funktionen. In der Vorlesung werden die Grundlagen zu Booleschen Funktionen und binären Entscheidungsdiagrammen vorgestellt und einige Anwendungen in der Informatik und angrenzenden Gebieten angegeben.

Lernziele:

Ziel der Vorlesung ist das Erlernen der wichtigsten Begriffe und Techniken aus dem Umfeld der Booleschen Funktionen und der binären Entscheidungsdiagramme. Anhand von Anwendungsbeispielen (etwa aus dem Modelchecking, der Spieltheorie und der Relationenalgebra) soll auch gelernt werden, wo man die letztgenannte Datenstruktur sinnvoll einsetzen kann, welche Vorteile sich daraus ergeben und wie man Algorithmen mit binären Entscheidungsdiagrammen entwirft und möglichst effizient implementiert.

Lehrinhalte:

Aussagenlogik, Boolesche Algebra, Boolesche Funktionen, wichtige praktische Problemstellungen der Aussagenlogik und bei Booleschen Funktionen, binäre Entscheidungsdiagramme, Ordnungen und Reduktionsregeln, wichtige Eigenschaften von binären Entscheidungsdiagrammen (Eindeutigkeit, Größe usw.), fundamentale Algorithmen auf binären Entscheidungsdiagrammen, Anwendungen in der Informatik und angrenzenden Gebieten.

Weitere Voraussetzungen:

Informatik- und Mathematik-Vorlesungen des ersten Studienjahrs

Prüfungsleistung:

Am Ende des Semesters findet eine mündliche Modulabschlußprüfung statt.

Lehr- und Lernmethoden:

In der Regel Tafelvortrag, unterstützt durch Beamerpräsentationen, wenn solche angebracht sind.

Verwendbarkeit:

Literatur:

Als begleitende Lehrbücher sind zu empfehlen:

• Rolf Drechsler und Bernd Becker, Graphenbasierte Funktionsdarstellung, Teubner-Verlag, 1998.
• Christoph Meinel, Thorsten Theobald, Algorithms and data structures in VLSI design, Springer-Verlag, 1998.
• Ingo Wegener, Branching programs and binary decision diagrams, SIAM, 2000

Weitere Hinweise auf Originalarbeiten werden in der Vorlesung angegeben.

Verweise:

Kommentar: