Reprezentace booleovských funkcí - NAIL031

• Anglický název: Representations of Boolean Functions
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: zrušen
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Další informace: http://www.cs.cas.cz/~savicky/vyuka/rbf/
• Garant: RNDr. Petr Savický, CSc.
• Třída: Informatika Mgr. - Teoretická informatika
• Kategorizace předmětu: Informatika > Teoretická informatika

Anotace

čeština

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 (18.04.2016)

angličtina

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.

Poslední úprava: T_KTI (20.04.2016)

Cíl předmětu

čeština

Naučit teorii a metody používané v oblasti booleovských funkcí.

Poslední úprava: T_KTI (18.04.2016)

angličtina

TBA

Poslední úprava: Hric Jan, RNDr. (07.06.2019)

Podmínky zakončení předmětu

čeština

TBA

Poslední úprava: Hric Jan, RNDr. (07.06.2019)

Literatura

čeština

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)

Sylabus

čeština

• Zavedení zkoumaných modelů, Booleovské obvody, formule, rozhodovací diagramy (BDD), DNF, CNF, rozhodovací stromy, read-once BDD, uspořádané BDD (OBDD).

• Duální funkce, funkce monotonní, samoduální, lineární.

• Diagram vzájemných vztahů mezi zkoumanými modely (důkazy inkluzí).

• Složitost vyjádření funkcí pomocí DNF, CNF, rozhodovacích stromů.

• Hloubka a velikost stromu pro funkci vyjádřenou současně pomocí DNF a CNF.

• Odhady maximální složitosti obvodů a rozhodovacích diagramů.

• Odhady složitosti pro OBDD a read-once BDD.

• Diagram vzájemných vztahů mezi zkoumanými modely (ostré inkluze a neporovnatelnosti).

• Operace s funkcemi reprezentovanými pomocí OBDD a rozhodovacích stromů.

• Neuniformní Turingův stroj, souvislost s Booleovskými modely, Karp-Liptonova věta.

• Pravděpodobnostní test ekvivalence pro read-once rozhodovací diagramy.

• BPP je podmožina P/poly, tedy lze reprezentovat obvody polynomiální velikosti.

Poslední úprava: T_KTI (05.05.2015)

angličtina

• Partial input, subcube, monomial, DNF, implicant, primary implicant.

• Clause, CNF, implicate, prime implicate.

• Dual function, monotone, self-dual and linear funciotns.

• Boolean formulas, circuits.

• Binary decision tree, binary decision diagrams (BDD), read-once BDD, OBDD.

• Diagram of mutual relationships between the studied models, proofs of embeddings in it.

• The maximum complexity of representing functions using circuits and binary decision diagrams.

• Bounds on the complexity of functions in DNF, CNF, decision trees.

• Bounds on the complexity of OBDD and read-once BDD.

• Diagram of mutual relationships between the studied models, proofs of strict inclusions and incomparabilitites.

• Operations with functions represented by OBDD.

• The relationship between the depth and size of a decision tree and the complexity of the function expressed by both DNF and CNF.

• Operations with functions represented using decision trees.

• Nonuniform Turing machine, relationship to Boolean models, Karp-Lipton theorem.

• Probabilistic non-equivalence test for read-once decision diagrams.

• BPP is contained in P/poly, so is representable by polynomial size circuits.

• Lower bounds for decision trees using Fourier transform of the Boolean functions.

Poslední úprava: T_KTI (16.05.2011)