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ů

5

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