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 2024
• 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: nevyučován
• Jazyk výuky: čeština, angličtina
• 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

čeština

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)

angličtina

This course is suitable for all undergraduate and doctoral students who have acquired at least basic knowledge of mathematical logic, graph theory, and complexity of algorithms. The course covers several areas of interesting problems centerted around Boolean functions. Although the course is mostly theoretical, it includes examples of applications of the covered theory (e.g. in artificial intelligence and relational databases). One of the goals of this course is to provide the students with interesting research topics, which may be suitable for their master thesis.

Poslední úprava: T_KTI (10.04.2001)

Cíl předmětu

čeština

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)

angličtina

The aim of this course is to introduce to the students the foundations of Boolean function theory and perhaps also suggest possible topics for a master theses.

Poslední úprava: Čepek Ondřej, prof. RNDr., Ph.D. (12.06.2019)

Podmínky zakončení předmětu

čeština

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)

angličtina

There is only an oral exam. The subject of the exam can be anything covered in the course (including all proofs, of course). If the school is closed due to state regulations the exam will be administered online (via 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

čeština

• Ú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)

angličtina

1) Introduction to Boolean functions.

• literals, logic operators, Boolean formulae and funkctions

• normal forms (DNF, CNF) and their properties

2) Implicants, consequents, resolution (consensus) and its completeness

3) Monotone functions and their basic properties

2) Regular functions.

• relative strength of variables, properties of regular functions

• recognition and dualization of regular functions

3) Threshold functions.

• properties, characterization, and recognition of threshold functions

4) Satisfiability of Boolean formulae

• NP-completeness of SAT and 3-SAT

• classes of formulae with polynomial time SAT: quadratic, Horn and q-Horn functions

5) Minimal representation of Boolean functions.

• proofs of NP-completeness for some known classes

• cases solvable in polynomial time: acyclic and quasi-acyclic functions

Poslední úprava: Čepek Ondřej, prof. RNDr., Ph.D. (30.04.2015)