Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (01.02.2019)
Přednáška seznamující s některými algoritmy pro booleovské funkce,
zejména splnitelnost. Přednáška též seznamuje se základy
parametrizované složitosti. Exponenciální algoritmy pro splnitelnost.
Parametrizovaná složitost a parametrizované algoritmy pro splnitelnost
a MaxSAT. Aproximační a prohledávací algoritmy pro MaxSAT.
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (01.02.2019)
The purpose of this lecture is to present several algorithms for
Boolean functions, especially for the satisfiability problem. The
lecture also contains an introduction to fixed-parameter algorithms and
parameterized complexity theory. Exponential algorithms for SAT and
MaxSAT. Parameterized complexity and fixed-parameter algorithms for
SAT and MaxSAT. Approximation and search algorithms for MaxSAT.
Literatura -
Poslední úprava: T_KTI (27.02.2014)
A. Biere, M. Heule, H. van Maaren, T. Walsh (Eds.). Handbook of Satisfiability, in: Frontiers in Artificial Intelligence and Applications, vol. 185, IOS Press, 2009, pp. 131-153
Niedermeier, Rolf. Invitation to fixed-parameter algorithms. Vol. 3. Oxford: Oxford University Press, 2006
Flum, Jörg, and Martin Grohe. Parameterized complexity theory. Vol. 3. Heidelberg: Springer, 2006
Poslední úprava: T_KTI (27.02.2014)
A. Biere, M. Heule, H. van Maaren, T. Walsh (Eds.). Handbook of Satisfiability, in: Frontiers in Artificial Intelligence and Applications, vol. 185, IOS Press, 2009, pp. 131-153
Niedermeier, Rolf. Invitation to fixed-parameter algorithms. Vol. 3. Oxford: Oxford University Press, 2006
Flum, Jörg, and Martin Grohe. Parameterized complexity theory. Vol. 3. Heidelberg: Springer, 2006
Sylabus -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (01.02.2019)
Exponenciální algoritmy pro k-SAT a obecný SAT
Úvod do parametrizované složitosti, příklady z teorie grafů.
Parametrizované algoritmy pro SAT založené na backdoor množinách.
Algoritmy pro SAT parametrizované stromovou šířkou.
Algoritmy pro SAT parametrizované deficiencí formule vzhledem k matched formulím
Kernelizace pro MaxSAT a parametrizace MaxSAT
Algoritmy pro MaxSAT založené na větvení a prořezávání (branch & bound)
Aproximační algoritmy pro MaxSAT
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (01.02.2019)
Exponential algorithms for k-SAT and general SAT
Introduction to parameterized complexity, examples from the graph theory
Fixed-parameter algorithms for SAT based on backdoor sets
Algorithms for SAT parameterized with treewidth
Algorithms for SAT parameterized with a deficiency of a formula
Kernelization of MaxSAT and parameterization of MaxSAT