PRŮBĚH PŘEDNÁŠKY REPREZENTACE BOOLEOVSKÝCH FUNKCÍ (ZIMNÍ SEMESTR 2014/2015)

==============================  15.10.2014  ==============================

- Reprezentace booleovské funkce, složitost reprezentace, složitost funkce.
- Obecný rámec porovnávání modelů pomocí tříd polynomiální složitosti.
- Neuniformní TS, L/poly = Poly(rozh.diagramy), P/poly = Poly(obvody),
  PSPACE/poly = Poly(sekvenční obvody).
- Délka programu a kolmogorovská složitost, Chaitinova věta o neúplnosti.
- Váha vektoru z {0,1}^n, Hammingovská vzdálenost, duální funkce.
- Monotonní, samoduální a lineární funkce.
- Maximální třídy booleovských funkcí uzavřené na skládání, charakterizace
  úplných bází.
- Počet monotonních, samoduálních a lineárních funkcí.
- Každá booleovská funkce je určena právě jedním polynomem nad F_2.
- Zadáno cvičení: Nalezněte obvod velikosti 2.5 n + O(1) v bázi všech binárních
  spojek pro současný výpočet konjunkce, disjunkce a parity n proměnných.

==============================  30.10.2014  ==============================

- Zavedení dnf(f), cnf(f), dt(f), nerovnost dnf(f) + cnf(f) \le dt(f).
- Bez důkazu nerovnost dt(f) \le s^O(log s log n), kde s = dnf(f) + cnf(f).
- Implikant, primární implikant, kanonická DNF, pro libovolnou funkci existuje
  minimální DNF složená pouze z primárních implikantů.
- Příklad funkce, která má 3^n/poly(n) primárních implikantů.
- Primární implikant monotonní funkce je monotonní.
- Pro monotonní f je dnf(f) rovna počtu primárních implikantů.
- Pro obecnou funkci je dnf(f) \ge |Supp(f) \cap A|/k, kde k je maximální počet
  ohodnocení z množiny A, které může splnit jeden primární implikant f.
- Složitost parity n proměnných je 2^{n-1}.
- Pro hloubku stromu dt-depth(f) a délky monomů a klauzulí dnf-width(f)
  a cnf-width(f) platí nerovnost dt-depth(f) \le dnf-width(f) cnf-width(f).
- Příklad funkce, pro kterou předchozí nerovnost platí jako rovnost.

==============================  3.11.2014  ==============================

- Konstrukce rozhodovacího stromu na základě CNF a DNF reprezentace stejné
  funkce, kvazipolynomiální test duality pro dvě monotonní DNF.
- V důkazu byl vynechán postup získání protipříkladu na dualitu, pokud 
  v některém kroku algoritmu není nalezen monom s požadovaným omezením délky.
- Konstrukce minimální DNF, která je ekvivalentní dané monotonní CNF,
  v kvazipoly čase ve vztahu k velikosti vstupu a výstupu.
- Zavedení read-once rozhodovacích diagramů a OBDD.
- Srovnání OBDD a konečných automatů v abecedě {0,1}.
- Charakterizace velikosti OBDD při daném uspořádání proměnných, důkaz
  nedokončen.

==============================  10.11.2014  ==============================

- Doplnění testu duality z minulé hodiny o nalezení protipříkladu proti dualitě,
  pokud dualita neplatí.
- Souvislost \pi-OBDD a konečných automatů.
- Pro každé částečné ohodnocení proměnných "a" kompatibilní s uspořádáním \pi
  obsahuje libovolné \pi-OBDD pro f uzel, který počítá subfunkci f|_a.
- Algoritmus pro minimalizaci OBDD, které neobsahuje nedosažitelné uzly, pomocí
  pravidel pro eliminaci a sloučení uzlů (elimination rule, merging rule).
- Minimální velikost \pi-OBDD pro f je rovna počtu subfunkcí f pro uspořádání \pi.
- Velikost OBDD pro funkci DSA_n pro různá uspořádání.
- Zavedena funkce ISA_n, dt(ISA_n) \le O(n^2).
- Zmíněno zavedení paritních OBDD, popsáno vyhodnocení pro daný vstup.
- Charakterizace velikosti parity-OBDD pomocí dimenze lineárního obalu S(f, \pi).
- Zmíněna souvislost velikosti OBDD a parity-OBDD s komunikační složitostí.

==============================  8.12.2014  ==============================

- Paritní OBDD pro pointerové funkce.
- Horní odhad počtu uzlů paritního OBDD pomocí obousměrné komunikační složitosti.
- Dolní odhad velikosti OBDD pro funkce ISA a shifted-equality.
- Definována funkce HWB.
- Výpočet optimálního pořadí proměnných jako nejkratší cesty v grafu velikosti 2^n.

==============================  15.12.2014  ==============================

- Debata o Rubikově kostce a podobných úlohách.
- Maximální složitost funkcí v OBDD a obvodech je \Theta(2^n/n).
- Dolní odhad 2^{n/5 - 1} pro složitost HWB_n.

==============================  5.1.2015  ==============================

- Dolní odhad velikosti 1-bdd pro k-mixed funkce.
- Funkce s polynomiální DNF a exponenciálním 1-bdd.
- Dolní odhady velikosti 1-bdd blízké maximální složitosti.

==============================  8.1.2015  ==============================

- Syntéza OBDD, spojka ITE, computed table, unique table.
- OBDD pro substituci funkce za proměnnou.