Booleovské funkce a jejich aplikace

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