Název:

Složitost

Zkratka:SLO
Ak.rok:2011/2012
Semestr:letní
Studijní plán:
ProgramOborRočníkPovinnost
IT-MGR-2MBI-volitelný
IT-MGR-2MBS-volitelný
IT-MGR-2MGM-volitelný
IT-MGR-2MGM.-volitelný
IT-MGR-2MIN-povinně volitelný - skupina B
IT-MGR-2MIN.2.volitelný
IT-MGR-2MIS1.volitelný
IT-MGR-2MIS.1.volitelný
IT-MGR-2MMI-volitelný
IT-MGR-2MMM-povinně volitelný - skupina L
IT-MGR-2MPS-volitelný
IT-MGR-2MPV-volitelný
IT-MGR-2MSK-volitelný
IT-MGR-2EITE2.volitelný
Vyučovací jazyk:čeština, angličtina
Informace pro zapsané:http://www.fit.vutbr.cz/study/courses/SLO/private/
Kredity:5 kreditů
Ukončení:zkouška (kombinovaná)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:2600026
 zkouškatestycvičenílaboratořeostatní
Body:6800032
Garant:Vojnar Tomáš, prof. Ing., Ph.D., UITS
Přednášející:Rogalewicz Adam, Mgr., Ph.D., UITS
Cvičící:Rogalewicz Adam, Mgr., Ph.D., UITS
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav inteligentních systémů FIT VUT v Brně
Prerekvizity: 
Teoretická informatika (TIN), UITS
Navazující:
Formální analýza a verifikace (FAV), UITS
Kryptografie (KRY), UITS
Paralelní a distribuované algoritmy (PRL), UITS
Nahrazuje:
Vyčíslitelnost a složitost (VSL), UITS
 
Cíle předmětu:
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ů.
Anotace:
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.
Požadované prerekvizitní znalosti a dovednosti:
Teorie formálních jazyků a rozhodnutelnosti na magisterské úrovni.
Získané dovednosti, znalosti a kompetence:
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ů.
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.
Literatura referenční:
  1. Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
  2. Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2
  3. Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
Literatura studijní:
  1. Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
  2. Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2
  3. Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
  4. Goldreich, O.: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 0-521-88473-X
  5. Kozen, D.C.: Theory of Computation, Springer, 2006, ISBN 1-846-28297-7
Průběžná kontrola studia:
  • Čtyři opravované domácí úlohy - každá za 8 bodů.
  • Závěrečná zkouška: 68 bodů.
  • Podmínka zápočtu: min. 15 bodů získaných v průběhu semestru.
  • Hranice pro úspěšnou zkoušku podle pravidel ECTS: 50 bodů.
Podmínky zápočtu:
Celkový zisk minimálně 15 bodů z domácích úloh.