Detail předmětu

Složitost (v angličtině)

FIT-SLOaAk. rok: 2017/2018

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

prof. Ing. Tomáš Vojnar, Ph.D.

Zajišťuje ústav

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

Nabízen zahraničním studentům

Všech fakult

Výsledky učení předmětu

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

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

Způsob a kritéria hodnocení

Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.

Celkový zisk minimálně 15 bodů z domácích úloh.

Osnovy výuky

    Osnova přednášek:
    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.

    Osnova ostatní - projekty, práce:
    Čtyři dílčí domácí úlohy zaměřené na různé aspekty probírané látky.

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

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

  • Čtyři projekty - každý za 8 bodů.
  • Závěrečná zkouška: 68 bodů.

Prerekvizity a korekvizity

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

  • Program IT-MGR-2 magisterský navazující

    obor MBI , 0 ročník, letní semestr, volitelný
    obor MSK , 0 ročník, letní semestr, volitelný
    obor MMM , 0 ročník, letní semestr, povinně volitelný
    obor MBS , 0 ročník, letní semestr, volitelný
    obor MPV , 0 ročník, letní semestr, volitelný
    obor MIS , 1 ročník, letní semestr, volitelný
    obor MIN , 0 ročník, letní semestr, povinně volitelný
    obor MGM , 0 ročník, letní semestr, volitelný

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

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