Detail předmětu

Složitost (v angličtině)

FIT-SLOaAk. rok: 2024/2025

Turingovy stroje jako základní výpočetní model pro analýzu výpočetní složitosti, časová a prostorová složitost výpočtů na Turingových strojích. Alternativní modely výpočtů, skeletový jazyk, stroje RAM a RASP a jejich vztah k Turingovým strojům z hlediska výpočetní složitosti. Asymptotické odhady složitosti, pojem tříd složitosti založených na časově a prostorově zkonstruovatelných funkcích, typické příklady tříd složitosti. Vlastnosti tříd složitosti: význam determinismu a nedeterminismu v oblasti výpočetní složitosti, Savitchův teorém, vztah prostoru a času, uzavřenost tříd složitosti vůči doplňku, ostrost vztahů mezi třídami. Některé pokročilé vlastnosti tříd složitosti: Blumův teorém, gap theorem (a jeho vztah k definici tříd složitosti na základě časově a prostorově zkonstruovatelných funkcí). Redukovatelnost a pojem úplnosti tříd složitosti. Příklady problémů úplných pro různé třídy složitosti. Hlubší diskuse tříd P a NP s důrazem na NP-úplné problémy (problém splnitelnosti apod.). Vztah rozhodovacích a optimalizačních problémů. Metody řešení výpočetně složitých optimalizačních problémů: deterministické přístupy, aproximace, pravděpodobnostní algoritmy. Vztah výpočetní složitosti a kryptografie. Hlubší diskuse PSPACE-úplných problémů, výpočetní složitost typických problémů z oblasti formální verifikace.

Jazyk výuky

angličtina

Počet kreditů

5

Garant předmětu

doc. Mgr. Adam Rogalewicz, Ph.D.

Zajišťuje ústav

Ústav inteligentních systémů (UITS)

Nabízen zahraničním studentům

Všech fakult

Vstupní znalosti

Teorie formálních jazyků a rozhodnutelnosti na magisterské úrovni.

Pravidla hodnocení a ukončení předmětu

  • Tři projekty - každý za 10 bodů (doporučený minimální zisk z projektů je 15 bodů).
  • Závěrečná zkouška: 70 bodů.

Učební cíle

Seznámit studenty s teorií výpočetní složitosti, nutnou k pochopení praktických možností algoritmického řešení problémů na fyzikálně realizovatelných výpočetních systémech. Seznámit studenty s vybranými přístupy k řešení výpočetně složitých problémů.
Znalost teoretických i praktických mezí použitelnosti výpočetních systémů. Schopnost použít vybrané přístupy k řešení výpočetně složitých problémů.

Prerekvizity a korekvizity

Základní literatura

Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009, ISBN: 0521424267. Dostupné online. (EN)
Ding-Zhu Du, Ker-I Ko: Theory of Computational Complexity, 2nd Edition, Wiley 2014, ISBN: 978-1-118-30608-6 (EN)
Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0 (EN)
Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1 (EN)
Papadimitriou, C. H.: Computational Complexity, Addison-Wesley, 1994, ISBN 0201530821 (EN)

Doporučená literatura

Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2 (EN)
Goldreich, O.: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 0-521-88473-X (EN)
Kozen, D.C.: Theory of Computation, Springer, 2006, ISBN 1-846-28297-7 (EN)

Zařazení předmětu ve studijních plánech

  • Program IT-MGR-1H magisterský navazující

    specializace MGH , 0 ročník, letní semestr, doporučený kurs

  • Program MIT-EN magisterský navazující 0 ročník, letní semestr, povinně volitelný

  • Program MITAI magisterský navazující

    specializace NGRI , 0 ročník, letní semestr, volitelný
    specializace NADE , 0 ročník, letní semestr, volitelný
    specializace NISD , 0 ročník, letní semestr, volitelný
    specializace NMAT , 0 ročník, letní semestr, povinný
    specializace NSEC , 0 ročník, letní semestr, volitelný
    specializace NISY do 2020/21 , 0 ročník, letní semestr, volitelný
    specializace NNET , 0 ročník, letní semestr, volitelný
    specializace NMAL , 0 ročník, letní semestr, volitelný
    specializace NCPS , 0 ročník, letní semestr, volitelný
    specializace NHPC , 0 ročník, letní semestr, volitelný
    specializace NVER , 0 ročník, letní semestr, volitelný
    specializace NIDE , 0 ročník, letní semestr, volitelný
    specializace NISY , 0 ročník, letní semestr, volitelný
    specializace NEMB do 2023/24 , 0 ročník, letní semestr, volitelný
    specializace NSPE , 0 ročník, letní semestr, volitelný
    specializace NEMB , 0 ročník, letní semestr, volitelný
    specializace NBIO , 0 ročník, letní semestr, volitelný
    specializace NSEN , 0 ročník, letní semestr, volitelný
    specializace NVIZ , 0 ročník, letní semestr, volitelný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

doc. Mgr. Adam Rogalewicz, Ph.D.
Ing. Ondřej Lengál, Ph.D.

Osnova

  1. Úvod, Turingovy stroje, složitost časová a prostorová.
  2. Alternativní modely výpočtů, skeletový jazyk, stroje typu RAM, RASP a jejich vztah k Turingovým strojům.
  3. Asymptotické odhady složitosti, třídy složitosti, determinismus a nedeterminismus z pohledu složitosti.
  4. Souvislosti prostoru a času z pohledu složitosti, uzavřenost tříd složitosti vůči doplňku, ostrost inkluzí mezi třídami složitosti.
  5. Blumův teorém. Gap theorem.
  6. Redukovatelnost, pojem úplnosti tříd složitosti, nejběžnější případy úplnosti.
  7. Třídy P a NP a jejich vlastnosti. NP-úplné problémy, problém splnitelnosti a jeho varianty.
  8. Problém obchodního cestujícího, problém batohu a další významné NP-úplné problémy.
  9. NP optimalizační problémy a jejich deterministické řešení: pseudo-polynomiální algoritmy, parametrizovaná složitost.
  10. Aproximační algoritmy, neaproximovatelnost.
  11. Pravděpodobnostní algoritmy a pravděpodobnostní třídy složitosti.
  12. Složitost a kryptografie.
  13. PSPACE-úplné problémy. Složitost a formální verifikace.

Projekt

26 hod., povinná

Vyučující / Lektor

doc. Mgr. Adam Rogalewicz, Ph.D.

Osnova

Tři dílčí domácí úlohy zaměřené na různé aspekty probírané látky.