The models for representation of boolean functions are discussed, namely
boolean formulas in DNF and CNF, and different types of binary decision
diagrams (BDD), in particular read-once decision diagrams and OBDD.
The course will mainly concentrate on the proofs of comparison of the
expressive power of the models and on the algorithms for the operations
with the boolean functions using BDD.
Last update: T_KTI (18.04.2016)
Přednáška se zabývá modely pro reprezentaci booleovských funkcí,
především booleovskými formulemi ve tvaru DNF, CNF, a různými typy
rozhodovacích diagramů (BDD), především read-once rozhodovacími
diagramy a OBDD. Přednáška je věnována důkazům vzájemného porovnání
vyjadřovací síly těchto modelů a jsou uvedeny algoritmy pro operace
s booleovskými funkcemi pomocí OBDD.
Aim of the course - Czech
Last update: T_KTI (18.04.2016)
Naučit teorii a metody používané v oblasti booleovských funkcí.
Literature -
Last update: T_KTI (18.04.2016)
I. Wegener. Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications, 2000.
Ch. Meinel, T. Theobald. Algorithms and Data Structures in VLSI-Design: OBDD - Foundations and Applications. Springer-Verlag, Berlin, Heidelberg, New York, 1998.
Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Springer-Verlag, 2012.
Last update: T_KTI (18.04.2016)
I. Wegener. Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications, 2000.
Ch. Meinel, T. Theobald. Algorithms and Data Structures in VLSI-Design: OBDD - Foundations and Applications. Springer-Verlag, Berlin, Heidelberg, New York, 1998.
Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Springer-Verlag, 2012.