PředmětyPředměty(verze: 945)
Předmět, akademický rok 2015/2016
   Přihlásit přes CAS
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 2015 do 2016
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: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
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
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: 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.
Cíl předmětu
Poslední úprava: T_KTI (18.04.2016)

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

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.

Sylabus -
Poslední úprava: T_KTI (05.05.2015)
  • 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.

 
Univerzita Karlova | Informační systém UK