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ů

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á kombinovaná zkouška: 70 bodů. Obě části jsou povinnou součástí.

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ů.

Studijní opory

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)

Elearning

eLearning: aktuální otevřený kurz

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.

Elearning

eLearning: aktuální otevřený kurz