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.
Poslední úprava: T_KTI (20.04.2016)
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.
Cíl předmětu -
Poslední úprava: T_KTI (18.04.2016)
Naučit teorii a metody používané v oblasti booleovských funkcí.
Poslední úprava: RNDr. Jan Hric (07.06.2019)
TBA
Podmínky zakončení předmětu -
Poslední úprava: RNDr. Jan Hric (07.06.2019)
TBA
Poslední úprava: RNDr. Jan Hric (07.06.2019)
TBA
Literatura -
Poslední úprava: 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.
Poslední úprava: 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.