Základní informace

• Přednášející: Petr Kučera <>, místnost S304
• Termín: Pátek 10:40 - 12:10
• Informace k předmětu v SIS

Pro organizaci přednášky budu používat moodle, přihlašte se v něm k tomuto kurzu.

Sylabus

Obsah přednášky může být upraven podle aktuálního zájmu studentů.

1. Exponenciální algoritmy pro k-SAT a obecný SAT
2. Parametrizované algoritmy pro SAT založené na backdoor množinách.
3. Algoritmy pro SAT parametrizované stromovou šířkou
4. Kernelizace pro MaxSAT a parametrizace MaxSAT
5. Algoritmy pro MaxSAT založené na větvení a prořezávání (branch & bound)
6. Algoritmy pro #SAT
7. Reprezentace znalostí založené na NNF (negation normal form)
8. OBDD, DNNF, d-DNNF, SDD
9. Srovnání těchto reprezentací s ohledem na zodpovídání dotazů a velikost
10. Kompilace formule v KNF do různých typů reprezentací
11. Využití pro počítání modelů