PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Algoritmické aspekty booleovských funkcí a parametrizovaná složitost - NTIN099
Anglický název: Algorithmic Aspects of Boolean Functions and Parameterized Complexity
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2015 do 2018
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: RNDr. Petr Kučera, Ph.D.
Třída: Informatika Mgr. - volitelný
Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Informatika, Aplikační software, Počítačová grafika a geometrie, Databázové systémy, Didaktika informatiky, Diskrétní matematika, Předměty širšího základu, Předměty obecného základu, Počítačová a formální lingvistika, Optimalizace, Programování, Softwarové inženýrství, Teoretická informatika
Anotace -
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.
Podmínky zakončení předmětu -
Poslední úprava: RNDr. Petr Kučera, Ph.D. (10.06.2019)

Předmět je zakončen zkouškou. Zkouška je ústní a zkouší se z látky probrané na přednáškách. V případě menšího počtu studentů může být zkouška nahrazena referováním článku, který navazuje na témata přednášená na přednášce.

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

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

 
Univerzita Karlova | Informační systém UK