Ausnahme: Am 31.7.2003 findet die Vorlesung im Seminarraum des Lehrstuhls 1 statt (E1, Raum 4013).
an den folgenden Tagen: 9.5., 23.5., 6.6., 27.6., 4.7., 25.7.
Raum 4013 in Gebäude E1, Ahornstr. 55
(Seminarraum des Lehrstuhls 1)
| Veranstalter: | Detlef Sieling |
|
|
| Termin: | Donnerstag, 10.00-11.30 Uhr |
| Ort: | Raum
6124 in Gebäude E2 (Seminarraum des Lehrstuhls 6) Ausnahme: Am 31.7.2003 findet die Vorlesung im Seminarraum des Lehrstuhls 1 statt (E1, Raum 4013). |
| Übungen: |
Freitag, 11.45-13.15 Uhr an den folgenden Tagen: 9.5., 23.5., 6.6., 27.6., 4.7., 25.7. Raum 4013 in Gebäude E1, Ahornstr. 55 (Seminarraum des Lehrstuhls 1) |
| Übungsblätter
(PS-Files): |
Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5 Blatt 6 |
| Skript: |
Postscript
(550k), PDF (400k) |
Binary Decision Diagrams (BDDs) sind eine graphische Darstellung von
booleschen Funktionen. Sie werden in Programmen für den
Hardwareentwurf als Datenstruktur für die Speicherung und
Manipulation von booleschen Funktionen, aber auch in der
Komplexitätstheorie zur Untersuchung der Ressource Speicherplatz
benutzt.
Die Vorlesung beginnt mit einer Einführung in OBDDs (Ordered
Binary Decision Diagrams). Es werden effiziente Algorithmen für
einige der wichtigen Operationen zur Manipulation von booleschen
Funktionen wie z.B. den Äquivalenztest vorgestellt. Andere
Operationen wie z.B. die Minimierung der Größe von OBDDs
sind
dagegen NP-hart. Weiterhin wird die OBDD-Größe von wichtigen
Funktionen untersucht. Es gibt viele wichtige Funktionen, für die
OBDDs sehr groß sind. Daher werden verschiedene erweiterte
Varianten von OBDDs besprochen, die zu kleinerer
Darstellungsgröße führen. Diese Varianten werden auch
zur Untersuchung von speicherplatzbeschränkten Berechnungen
untersucht. Das Ziel des Beweises unterer Schranken für die
Größe von OBDDs und ihren Verallgemeinerungen für
wichtige Funktionen besteht einerseits darin zu zeigen, dass die
betrachtete Variante nicht für die Darstellung dieser Funktionen
geeignet ist, zum anderen erhält man auch untere Schranken
für
den Speicherplatzbedarf zur Berechnung dieser Funktion.
Die Untersuchung von OBDDs und ihren Erweiterungen verwendet zugleich
Methoden aus verschiedenen Bereichen der theoretischen Informatik. Dies
sind Methoden zum Entwurf effizienter Algorithmen oder zum Beweis, dass
solche Algorithmen vermutlich nicht existieren. Weiterhin wird die
Kommunikationskomplexität als wichtigste Methode zum Beweis von
unteren Schranken für den Ressourcenbedarf von Berechnungen
behandelt.
Literatur:
CUDD-Paket