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

Garant předmětu:

Dušan Knop

Přednášející:

Dušan Knop, Ondřej Suchý

Cvičící:

Radek Hušek, Dušan Knop, Michal Opler, Ondřej Suchý, Tomáš Valla

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 češtině

Další informace:

https://courses.fit.cvut.cz/NI-ICC

Rozvrh na zimní semestr 2026/2027:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út	místnost T9:155 Knop D. Suchý O. 14:30–16:00 (přednášková par. 1) Dejvice Posluchárna
St	místnost TH:A-1442 Valla T. 11:00–11:45 (přednášková par. 1 paralelka 101) Thákurova 7 (budova FSv)místnost TH:A-1442 Valla T. 11:45–12:30 (přednášková par. 1 paralelka 102) Thákurova 7 (budova FSv)místnost TH:A-1442 Opler M. 12:45–13:30 (přednášková par. 1 paralelka 103) Thákurova 7 (budova FSv)místnost TH:A-1442 Opler M. 13:30–14:15 (přednášková par. 1 paralelka 104) Thákurova 7 (budova FSv)
Čt	místnost T9:302 Suchý O. 12:45–13:30 (přednášková par. 1 paralelka 105) Dejvice NBFIT učebnamístnost T9:302 Suchý O. 13:30–14:15 (přednášková par. 1 paralelka 106) Dejvice NBFIT učebnamístnost T9:346 Hušek R. 16:15–17:00 (přednášková par. 1 paralelka 107) Dejvice NBFIT učebnamístnost T9:346 Hušek R. 17:00–17:45 (přednášková par. 1 paralelka 108) Dejvice NBFIT učebna
Pá

Rozvrh na letní semestr 2026/2027:

Rozvrh není připraven

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)