Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail předmětu
FIT-SLOaAk. rok: 2019/2020
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
Počet kreditů
Garant předmětu
Zajišťuje ústav
Nabízen zahraničním studentům
Výsledky učení předmětu
Prerekvizity
Způsob a kritéria hodnocení
Učební cíle
Prerekvizity a korekvizity
Doporučená literatura
Zařazení předmětu ve studijních plánech
obor MBS , libovolný ročník, letní semestr, volitelnýobor MBI , libovolný ročník, letní semestr, volitelnýobor MIN , libovolný ročník, letní semestr, povinně volitelnýobor MMM , libovolný ročník, letní semestr, povinně volitelnýobor MGM , libovolný ročník, letní semestr, volitelný
obor MGMe , libovolný ročník, letní semestr, povinně volitelný
obor MPV , libovolný ročník, letní semestr, volitelnýobor MSK , libovolný ročník, letní semestr, volitelný
specializace NBIO , libovolný ročník, letní semestr, volitelnýspecializace NISD , libovolný ročník, letní semestr, volitelnýspecializace NISY , libovolný ročník, letní semestr, volitelnýspecializace NIDE , libovolný ročník, letní semestr, volitelnýspecializace NCPS , libovolný ročník, letní semestr, volitelnýspecializace NSEC , libovolný ročník, letní semestr, volitelnýspecializace NMAT , libovolný ročník, letní semestr, povinnýspecializace NGRI , libovolný ročník, letní semestr, volitelnýspecializace NNET , libovolný ročník, letní semestr, volitelnýspecializace NVIZ , libovolný ročník, letní semestr, volitelnýspecializace NSEN , libovolný ročník, letní semestr, volitelnýspecializace NMAL , libovolný ročník, letní semestr, volitelnýspecializace NHPC , libovolný ročník, letní semestr, volitelnýspecializace NVER , libovolný ročník, letní semestr, volitelnýspecializace NEMB , libovolný ročník, letní semestr, volitelnýspecializace NADE , libovolný ročník, letní semestr, volitelnýspecializace NSPE , libovolný ročník, letní semestr, volitelný
obor MGH , libovolný ročník, letní semestr, doporučený
obor MIS , 1. ročník, letní semestr, volitelný
Přednáška
Vyučující / Lektor
Osnova
Projekt