PředmětyPředměty(verze: 953)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Booleovské funkce a jejich aplikace - NAIL021
Anglický název: Boolean Functions and Their Applications
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020 do 2023
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0, Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Způsob výuky: prezenční
Další informace: http://ktiml.mff.cuni.cz/~cepek/vyuka.html
Garant: prof. RNDr. Ondřej Čepek, Ph.D.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Je prerekvizitou pro: NTIN094, NTIN093
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
Poslední úprava: T_KTI (10.04.2001)
Cíl předmětu -

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: Čepek Ondřej, prof. RNDr., Ph.D. (12.06.2019)
Podmínky zakončení předmětu -

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: Čepek Ondřej, prof. RNDr., Ph.D. (26.09.2020)
Literatura

Y.Crama, P.L.Hammer, Boolean Functions - Theory, Algorithms, and Applications. Cambridge University Press, 2011.

Poslední úprava: Čepek Ondřej, prof. RNDr., Ph.D. (30.04.2015)
Požadavky ke zkoušce

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: Čepek Ondřej, prof. RNDr., Ph.D. (12.06.2019)
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)

Poslední úprava: Čepek Ondřej, prof. RNDr., Ph.D. (30.04.2015)
 
Univerzita Karlova | Informační systém UK