Předmět Složitost (FIT-SLO)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu FIT-SLO - Složitost, Fakulta informačních technologií, Vysoké učení technické v Brně (VUT).

Materiál	Typ	Datum	Počet stažení

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

Osnova

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.

Literatura

Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0 Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2 Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1 Goldreich, O.: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 0-521-88473-X Kozen, D.C.: Theory of Computation, Springer, 2006, ISBN 1-846-28297-7 Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0 Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2 Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1

Požadavky

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

Garant

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

Vyučující

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