Proseminar “Binäre Entscheidungsgraphen”
Proseminar “Binäre Entscheidungsgraphen”
Course with SWS 0/2/0 (lecture/exercise/practical) in WS 2026
Das Thema des Proseminars sind binäre Entscheidungsgraphen (engl. Binary Decision Diagrams, kurz BDDs). Diese wurden erstmals von Lee und Akers zur Darstellung von Schaltfunktionen vorgestellt. Heute werden verschiedene Varianten von ordered BDDs (OBDDs) in zahlreichen Verifikationswerkzeugen und Model Checkern wie z. B. nuSMV oder Prism als Datenstruktur zur effizienten Speicherung und Analyse von Systemmodellen eingesetzt.
Die individuell zu bearbeitenden Seminarthemen befassen sich mit den theoretischen Grundlagen binärer Entscheidungsgraphen. Insbesondere sollen die wichtigsten Operatoren und Algorithmen auf BDDs vorgestellt und hinsichtlich ihrer theoretischen Komplexität untersucht werden.
Registration
Registration via Opal is required until October 12.
Prerequisites
Besides an interest in theoretical computer science, the Proseminar requires solid foundations in algorithms and data structures, as well as mathematics as covered in the first two semesters of the study program.
Dates
The initial meeting will most likely be held on October 15 or 16. All participants registered in Opal by the due date will be notified about the details by e-mail. Each participant will then be assigned a topic and a supervisor. After that, further proceedings are arranged individually between each participant and their supervisor.
The required presentations and question-and-answer sessions will be held en bloc between January and March 2027. The specific dates will be announced later.
Examination
Bachelor Informatik (PO 2025)
- INF-25-Ba-WIA: Komplexe Leistung (60 hours)
Bachelor Angewandte Informatik (PO 2025)
- INF-25-Ba-WIA: Komplexe Leistung (60 hours)
Diplom Informatik (PO 2025)
- INF-25-Ba-WIA: Komplexe Leistung (60 hours)
The Komplexe Leistung (complex or multi-part examination) consists of a presentation (25 minutes) and an oral question-and-answer session (15 minutes).
Contact
In case of organizational questions, please send an e-mail to studies_alg@mailbox.tu-dresden.de.
