Předmět Algoritmické aspekty booleovských funkcí a parametrizovaná složitost (NTIN099)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTIN099 - Algoritmické aspekty booleovských funkcí a parametrizovaná složitost, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
Materiál | Typ | Datum | Počet stažení |
---|
Další informace
Sylabus
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
Literatura
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-153Niedermeier, Rolf. Invitation to fixed-parameter algorithms. Vol. 3. Oxford: Oxford University Press, 2006Flum, Jörg, and Martin Grohe. Parameterized complexity theory. Vol. 3. Heidelberg: Springer, 2006
Garant
RNDr. Petr Kučera, Ph.D.