Reprezentace Booleovských funkcí

English version

Přednáška se koná na Katedře teoretické informatiky a matematické logiky (KTIML) MFF UK.
Odkaz do informačního systému: NAIL031
Úmluva na přednášku probíhá emailem.

Rozsah: LS 2/0 Zk

Průběh

2014/2015

Anotace

Přednáška se zabývá modely pro reprezentaci Booleovských funkcí, především Booleovskými obvody a formulemi, DNF, CNF, a různými typy rozhodovacích diagramů. Některé z uvedených modelů jsou použitelné jako datová struktura pro algoritmy, které provádějí operace s Booleovskými funkcemi. Přednáška je věnována především důkazům některých známých výsledků týkajících se vzájemného porovnání vyjadřovací síly těchto modelů.

Osnova

  1. Zavedení zkoumaných modelů, Booleovské obvody, formule, rozhodovací diagramy (BDD), DNF, CNF, rozhodovací stromy, read-once BDD, uspořádané BDD (OBDD).
  2. Duální funkce, funkce monotonní, samoduální, lineární.
  3. Diagram vzájemných vztahů mezi zkoumanými modely (důkazy inkluzí).
  4. Složitost vyjádření funkcí pomocí DNF, CNF, rozhodovacích stromů.
  5. Hloubka a velikost stromu pro funkci vyjádřenou současně pomocí DNF a CNF.
  6. Odhady maximální složitosti obvodů a rozhodovacích diagramů.
  7. Odhady složitosti pro OBDD a read-once BDD.
  8. Diagram vzájemných vztahů mezi zkoumanými modely (ostré inkluze a neporovnatelnosti).
  9. Operace s funkcemi reprezentovanými pomocí OBDD a rozhodovacích stromů.
  10. Neuniformní Turingův stroj, souvislost s Booleovskými modely, Karp-Liptonova věta.
  11. Pravděpodobnostní test ekvivalence pro read-once rozhodovací diagramy.
  12. BPP je podmožina P/poly, tedy lze reprezentovat obvody polynomiální velikosti.

Texty k přednášce

Body 1 - 4 a 6 - 8 jsou v textu rbf2011a1.pdf (zhuštěně rbf2011a2.pdf).

Body 5 a 9 - 12 jsou v textu rbf2011b1.pdf (zhuštěně rbf2011b2.pdf).

Bod 13 je v textu rbf2011c1.pdf (zhuštěně rbf2011c2.pdf).

Zkouška

Zkouška obvykle probíhá v Ústavu Informatiky na Mazance (u metra C Ládví). Přihlásit se ke zkoušce je možné emailem.

Literatura

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. pdf ke stažení

Pro doplnění: paritní OBDD paritni.pdf.

Obrázky vícerozměrných krychlí

zde