NTIN099 — Algoritmické aspekty booleovských funkcí a parametrizovaná složitost

Petr Kučera, KTIML MFF UK

Základní informace

Termín

Přednáška probíhá v letním semestru (aktuálně 2016/17), termín přednášky je obvykle umlouván e-mailem. Letos byl již termín umluven na úterý 14:00 v chodbě KTIML ve třetím patře.

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. Úvod do parametrizované složitosti, příklady z teorie grafů.
  3. Parametrizované algoritmy pro SAT založené na backdoor množinách.
  4. Algoritmy pro SAT parametrizované stromovou šířkou.
  5. Algoritmy pro SAT parametrizované deficiencí formule vzhledem k matched formulím
  6. Kernelizace pro MaxSAT a parametrizace MaxSAT
  7. Algoritmy pro MaxSAT založené na větvení a prořezávání (branch & bound)
  8. Aproximační algoritmy pro MaxSAT