[NAIL021] - Booleovské funkce a jejich aplikace 14.01.2014

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: [NAIL021] - Booleovské funkce a jejich aplikace 14.01.2014

[NAIL021] - Booleovské funkce a jejich aplikace 14.01.2014

od Davpe » 14. 1. 2014 12:58

Konsenzuální metoda - algoritmus a důkaz
Přečetl si to, zeptal se jen na nějakou drobnost v důkazu co jsem tam měl napsanou, ale nevysvětlenou. Pak se zeptal na definici skrytě hornovské formule a jak rychle je umíme testovat. Řekl jsem, že je to falsifikovanost kvadratických funkcí a on namítl že ty můžou být dlouhé. Pak jsem si vzpomněl, že se to vyřešilo zavedením \mathcal{F}_p se složitostí algoritmu O(|\mathcal{F}|) a to mu stačilo - nechtěl ani její konstrukci.

Co jsem zaslechl od vedlejší lavice, tak se tam řešily duální funkce, algoritmus pro dualizaci regulárních a jak je obecně dualizace těžká.

Nahoru