Prof. Dr. sc. Christoph Meinel
FB IV - Informatik
Eines der Hauptprobleme beim Chipentwurf besteht darin, daß die Anzahl der zu bewältigenden Kombinationen der einzelnen Chipbausteine ins Unermeßliche steigt. Zur Beherrschung dieser Problematik hat sich eine sehr fruchtbare Verbindung zu einem Kerngebiet der Theoretischen Informatik, dem Gebiet des Entwurfs von Datenstrukturen und effizienten Algorithmen, herstellen lassen, die in dem Konzept der geordneten binären Entscheidungsgraphen (kurz OBDD) besteht. Ursache für die effiziente Arbeit mit OBDDs ist der relativ gute ``Trade-off'' zwischen speichereffizienter Repräsentation der Funktionalität und zeiteffizienter Ausführbarkeit wichtiger Grundoperationen wie Komposition und Äquivalenztest. OBDDs haben aber nicht nur im Chipentwurf, sondern auch im Bereich der kombinatorischen Optimierung der Verifikation sequentieller Systeme zahlreiche Anwendungen.
Die Vorlesung bietet eine systematische Einführung der Datenstruktur der binären Entscheidungsgraphen und eine breite Übersicht über ihre verschiedenen Anwendungen. Dabei wird sowohl Wert auf eine theoretisch fundierte Analyse der Komplexität der einzelnen Grundaufgaben der Booleschen Manipulation gelegt als auch auf den praktischen Umgang mit den zugrundeliegenden Software-Systemen.
Die Vorlesung ist vierstündig. Sie wendet sich vornehmlich an Studenten der Informatik, Wirtschaftsinformatik und der Mathematik im Hauptstudium. Das Vorlesungsskript liegt auch in elektronischer Form vor. (http://www.informatik.uni-trier.de/~meinel/Skripten.html )
&nb
Vorlesung:- Mo 8-10 (Raum: V 301) und
- Di 8-10 (Raum: V 301)
Übung: (Dipl.-Inf. Harald Sack)
