Předmět Booleovské funkce a jejich aplikace (NAIL021)
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 NAIL021 - Booleovské funkce a jejich aplikace, 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
Sylabus
• Ú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)
Literatura
Y.Crama, P.L.Hammer, Boolean Functions - Theory, Algorithms, and Applications. Cambridge University Press, 2011.
Garant
doc. RNDr. Ondřej Čepek, Ph.D.