Hasso-Plattner-InstitutSDG am HPI
Hasso-Plattner-InstitutDSG am HPI
  
Login
 

Binary Decision Diagram Technology (Wintersemester 2005/2006)

Dozent:
Tutoren: Prof. Dr. Christoph Meinel

Allgemeine Information

  • Semesterwochenstunden: 4
  • ECTS: 6
  • Benotet: Ja
  • Einschreibefrist: 01.11.2005
  • Lehrform:
  • Belegungsart: Wahlpflichtmodul

Studiengänge

  • IT-Systems Engineering MA

Beschreibung

This course covers both the theoretic aspect and the practical application of Binary decision Diagrams.

The course is divided into three parts:

  • In the first part, the basic theory of BDDs is developed. Algorithms for BDD manipulation and minimization based on variable ordering are discussed. Approximation of the worst-case run-time for all algorithms is given.
  • The second part of the course considers the basic data structures (directed acyclic graphs, look-up tables) and essential programming techniques (hashing, dynamic programming) used to represent and manipulate Binary Decision Diagrams. The implementation of a high performance BDD package in C/C++ is discussed, based on a case study of a state-of-the-art BDD package.
  • The third part of the course is devoted to application of binary and other DDs to problems encountered in logic synthesis, verification, and testing, image processing.

Voraussetzungen

Prerequisites: Basic knowledge in computer science, programming in C, data structures and algorithms.

Literatur

Course literature: