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)
Anotace
Tato přednáška je vhodná pro všechny studenty (nebo doktorandy), kteří mají alespoň základní znalosti z matematické logiky, teorie grafů a složitosti algoritmů. Přednáška pokrývá několik oblastí zajímavých problémů soustředěných okolo Boolovských funkcí. Ačkoli je přednáška převážně teoretická, zahrnuje i ukázky aplikací probírané teorie (např. v oblasti umělé inteligence a relačních databází).
Jedním z cílů přednášky je poskytnout studentům zajímavá výzkumná témata, vhodná případně i pro diplomové práce