Úvod do výpočetní složitosti

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Prezenční přednášky a cvičení s podporou e-learningového portálu s podklady, streamovanými a nahranými přednáškami a prosemináři. Důraz je kladen na aktivní zapojení studentů a diskuzi

Požadavky:

Osnova přednášek:

1. Deterministické Turingovy stroje, výpočet a univerzální Turingův stroj.

2. Nerozhodnutelnost, Halting problém, časová složitost, třída P, věta o časové hierarchii (bez důkazu).

3. Nedeterministické Turingovy stroje, výpočet a univerzální Turingův stroj, příklady výpočtů, třída NP.

4. Many-one redukce, NP-těžkost a NP-úplnost, Cookova věta (bez důkazu), příklady redukcí (Nezávislá množina,...).

5. Vliv čísel na vstupu - silná a slabá NP-těžkost, pseudopolynomiální algoritmy (dynamický program pro problém batohu a příbuzné problémy).

6. Prostorová složitost, třídy DSPACE a NSPACE, Savitchova věta.

7. Řešení těžkých problémů pomocí SAT řešičů.

8. Řešení těžkých problémů pomocí ILP řešičů.

9. Mírně exponenciální algoritmy pro těžké problémy. Heldův-Karpův algoritmus. Využití principu vícenásobné inkluze. Efektivní rekurzivní algoritmy.

10. Aproximační algoritmy pro těžké problémy. Ukázky pro vrcholové pokrytí, s využitím LP, a pro další problémy, např. k-Center.

11. FPT algoritmy a kernelizace pro těžké problémy. Ukázky pro vrcholové pokrytí a případně další problémy.

12. Heuristické metody pro přístup k těžkým problémům. Local Search a metody založené na něm. Metaheuristiky.

13. Orákulové TS a polynomiální hierarchie.

Osnova cvičení:

bude doplněno

Cíle studia:

Cílem předmětu je seznámit studenty s úplnými základy teorie vyčíslitelnosti a základy teorie složitosti, zejména nerozhodnutelností, NP-těžkostí a NP-úplností. Dále se základy prostorové složitosti. Následně jsou předvedeny jednotlivé způsoby jak lze ke zvládání těžkých výpočetních problémů přistupovat -- zejména SAT a ILP řešiče, návrh mírně

exponenciálních algoritmů, aproximační algoritmy, parametrizované algoritmy a heuristiky

Studijní materiály:

1. Arora, S., Barak, B: Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ISBN 0521424267.

2. Wigderson, A.: Mathematics and Computation: A Theory Revolutionizing Technology and Science. Princeton University Press, 2019. ISBN 9780691189130.

3. Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. ISBN 052188473X.

Poznámka:

předmět je vyučován v češtině

Další informace:

bude doplněno

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Mgr. specializace Počítačová bezpečnost, 2026 (povinný předmět programu)
• Mgr. specializace Počítačové systémy a sítě, 2026 (povinný předmět programu)
• Mgr. specializace Teoretická informatika, 2026 (povinný předmět programu)
• Mgr. specializace Programovací jazyky, 2026 (povinný předmět programu)
• Mgr. specializace Umělá inteligence, 2026 (povinný předmět programu)
• Mgr. program, pro fázi studia bez specializace, ver. pro roky 2026 a vyšší (povinný předmět programu)