Detail předmětu
Složitost (v angličtině)
FIT-SLOaAk. rok: 2018/2019
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.
Garant předmětu
Zajišťuje ústav
Nabízen zahradnič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.
- doporučená prerekvizita
Doporučená nebo povinná literatura
- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
- Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
- Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
Způsob a kritéria hodnocení
- Čtyři projekty - každý za 8 bodů (doporučený minimální zisk z projektů je 15 bodů).
- Závěrečná zkouška: 68 bodů.
Jazyk výuky
angličtina
Osnovy výuky
- Osnova přednášek:
- Úvod, Turingovy stroje, složitost časová a prostorová.
- Alternativní modely výpočtů, skeletový jazyk, stroje typu RAM, RASP a jejich vztah k Turingovým strojům.
- Asymptotické odhady složitosti, třídy složitosti, determinismus a nedeterminismus z pohledu složitosti.
- 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.
- Blumův teorém. Gap theorem.
- Redukovatelnost, pojem úplnosti tříd složitosti, nejběžnější případy úplnosti.
- Třídy P a NP a jejich vlastnosti. NP-úplné problémy, problém splnitelnosti a jeho varianty.
- Problém obchodního cestujícího, problém batohu a další významné NP-úplné problémy.
- NP optimalizační problémy a jejich deterministické řešení: pseudo-polynomiální algoritmy, parametrizovaná složitost.
- Aproximační algoritmy, neaproximovatelnost.
- Pravděpodobnostní algoritmy a pravděpodobnostní třídy složitosti.
- Složitost a kryptografie.
- 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.
Cíl
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ů.
Zařazení předmětu ve studijních plánech
- Program IT-MGR-2 magisterský navazující
obor MBS , libovolný ročník, letní semestr, 5 kreditů, volitelný
obor MBI , libovolný ročník, letní semestr, 5 kreditů, volitelný
obor MIN , libovolný ročník, letní semestr, 5 kreditů, povinně volitelný
obor MMM , libovolný ročník, letní semestr, 5 kreditů, povinně volitelný
obor MGM , libovolný ročník, letní semestr, 5 kreditů, volitelný - Program IT-MGR-2 magisterský navazující
obor MGMe , libovolný ročník, letní semestr, 5 kreditů, povinně volitelný
- Program IT-MGR-2 magisterský navazující
obor MPV , libovolný ročník, letní semestr, 5 kreditů, volitelný
obor MSK , libovolný ročník, letní semestr, 5 kreditů, volitelný - Program IT-MGR-1H magisterský navazující
obor MGH , libovolný ročník, letní semestr, 5 kreditů, doporučený
- Program IT-MGR-2 magisterský navazující
obor MIS , 1. ročník, letní semestr, 5 kreditů, volitelný
Typ (způsob) výuky
Přednáška
26 hod., nepovinná
Vyučující / Lektor
Osnova
- Úvod, Turingovy stroje, složitost časová a prostorová.
- Alternativní modely výpočtů, skeletový jazyk, stroje typu RAM, RASP a jejich vztah k Turingovým strojům.
- Asymptotické odhady složitosti, třídy složitosti, determinismus a nedeterminismus z pohledu složitosti.
- 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.
- Blumův teorém. Gap theorem.
- Redukovatelnost, pojem úplnosti tříd složitosti, nejběžnější případy úplnosti.
- Třídy P a NP a jejich vlastnosti. NP-úplné problémy, problém splnitelnosti a jeho varianty.
- Problém obchodního cestujícího, problém batohu a další významné NP-úplné problémy.
- NP optimalizační problémy a jejich deterministické řešení: pseudo-polynomiální algoritmy, parametrizovaná složitost.
- Aproximační algoritmy, neaproximovatelnost.
- Pravděpodobnostní algoritmy a pravděpodobnostní třídy složitosti.
- Složitost a kryptografie.
- PSPACE-úplné problémy. Složitost a formální verifikace.
Projekt
26 hod., povinná
Vyučující / Lektor
Osnova
Čtyři dílčí domácí úlohy zaměřené na různé aspekty probírané látky.