Předmět Reprezentace booleovských funkcí (NAIL031)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NAIL031 - Reprezentace booleovských funkcí, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Naučit teorii a metody používané v oblasti boolovských funkcí
Sylabus
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.
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.
Garant
RNDr. Petr Savický, CSc.