Introduction to Computational Complexity

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:

Předpokládají se znalosti teorie grafů a grafových algoritmů v rámci kurzu BI-AG1, jakož i znalosti formálních jazyků a nedeterminismu v rámci kurzu BI-AAG. Znalosti z kurzu BI-AG2 jsou výhodou.

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í:

1. Návrh jednoduchých Turingových strojů

2. Omezení Turingových strojů, snižení počtu pásek

3. Návrh nedeterministických Turingových strojů, charakterizace třídy NP

4. Návrh polynomiálních redukcí

5. Návrh pokročilejších polynomiálních redukcí

6. Návrh pseudopolynomiálních algoritmů

7. Fomulace problémů jako úlohy SAT

8. Fomulace problémů jako úlohy ILP

9. Návrh mírně exponenciálních algoritmů

10. Návrh aproximačních algoritmů

11. Návrh FPT algoritmů

12. Návrh heuristických algoritmů

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 anglič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ů:

• Master specialization Computer Security, Version 2026 (povinný předmět programu)
• Master programme, for the phase of study without specialisation, ver. for 2026 and higher (povinný předmět programu)
• Master specialization Computer Systems and Networks, in English, 2026 (povinný předmět programu)
• Master specialization Computer Science, in English, 2026 (povinný předmět programu)
• Master specialization Programming Languages, in English, 2026 (povinný předmět programu)