|
|
|
||
Poslední úprava: T_KTI (10.04.2001)
|
|
||
Poslední úprava: prof. RNDr. Ondřej Čepek, Ph.D. (12.06.2019)
Cílem předmětu je seznámi studenty se základy teorie Booleovských funkcí a případně poskytnout témata pro diplomové práce. |
|
||
Poslední úprava: prof. RNDr. Ondřej Čepek, Ph.D. (26.09.2020)
Zkouška je pouze ústní, předmětem zkoušky může být cokoli z probrané látky (pochopitelně včetně důkazů). V případě nařízeného uzavření školy bude zkouška probíhat on-line (přes Zoom). |
|
||
Poslední úprava: prof. RNDr. Ondřej Čepek, Ph.D. (30.04.2015)
Y.Crama, P.L.Hammer, Boolean Functions - Theory, Algorithms, and Applications. Cambridge University Press, 2011. |
|
||
Poslední úprava: prof. RNDr. Ondřej Čepek, Ph.D. (12.06.2019)
Zkouška je pouze ústní, předmětem zkoušky může být cokoli z probrané látky (pochopitelně včetně důkazů). |
|
||
Poslední úprava: prof. RNDr. Ondřej Čepek, Ph.D. (30.04.2015)
• Úvod do Booleovských funkcí - literály, logické operátory, Booleovské formule a funkce, normální formy (DNF, CNF) a jejich vlastnosti. • Rezoluce (konsensus) a její úplnost. • Monotónní Booleovské funkce a jejich základní vlasnosti. • Regulární funkce (poměrná síla proměnných, vlastnosti regulárních funkcí, rozpoznávání a dualizace regulárních funkcí) • Prahové funkce (vlastnosti, charakterizace a rozpoznávání prahových funkcí) • Splnitelnost Booleovských formulí (NP-úplnost SATu a 3-SATu, třídy formulí rozhodnutelné v polynomiálním čase: kvadratické, Hornovské a q-Hornovské funkce) • Minimální reprezentace Booleovských funkcí (důkazy NP-úplnosti pro některé známé třídy, případy řešitelné v polynomiálním čase: acyklické a quasi-acyklické funkce) |