Stammvorlesung "Theorie des
Logikentwurfs"
Sommersemester 2000
| Veranstalter: |
Detlef Sieling |
| Übungen: |
Paul Fischer |
Übersicht über den Inhalt der Vorlesung, Literaturangaben
Diese Übersicht über den Inhalt
der Vorlesung enthält Literaturangaben und eine genaue
Beschreibung der prüfungsrelevanten Teile der Vorlesung.
Begleitmaterial zur Vorlesung
Gegenüber dem Begleitmaterial, das während des Semesters zur
Verfügung gestellt wurde, wurden einige kleinere Korrekturen
vorgenommen und das Begleitmaterial zu einem zusammenhängenden Text
zusammengefügt. Eine Fehlerliste zum Begleitmaterial
befindet sich auf der
WWW-Seite der Vorlesung "Theorie des Logikentwurfs" im Sommersemester
2001.
Neu: Das Buch "Effiziente Algorithmen
für grundlegende Funktionen" von Ingo Wegener, auf das im
Begleitmaterial vielfach verwiesen wird, steht jetzt auch im WWW unter http://ls2-www.cs.uni-dortmund.de/monographs/tdl/
zur Verfügung.
OBDD-Pakete
Wer Interesse an den in der Vorlesung erwähnten OBDD-Paketen hat,
findet auf der Homepage
von Fabio Somenzi Hinweise auf das CUDD-Paket, das auch von dort
geladen werden kann.
Preisaufgabe
Das Problem, für zwei Polynome zu entscheiden, ob sie dieselbe
Funktion darstellen, ist als NP-hart bekannt. Daher können wir nur
auf Heuristiken für dieses Problem hoffen. Die Preisaufgabe besteht
darin, einen möglichst guten Algorithmus für dieses Problem
zu entwerfen und zu implementieren. Für die beste Lösung
dieses Problems gibt es einen Buchpreis. Die folgenden Links
zeigen auf eine genauere Beschreibung der
Aufgabenstellung und auf zwei Dateien (Datei1
, Datei2) mit Beispielen für die
Eingabe für das gewünschte Programm.
Übungsblätter
14.5.2003 - Detlef Sieling