|
Vyučující
|
-
Balun Jiří, Mgr.
-
Jančar Petr, prof. RNDr. CSc.
-
Osička Petr, Mgr. Ph.D.
|
|
Obsah předmětu
|
Připomenutí pojmů Turingův stroj (TS), výpočet (konfigurace, apod.), jazyk přijímaný TS, jazyk rozhodovaný TS, turingovsky vyčíslovaná funkce, Church-Turingova teze. Jazyky a problémy: vztah rekurzivních a částečně rekurzivních jazyků k jazykům Chomského hierarchie. Riceova věta, věta o rekurzi a jejich aplikace. Další modely výpočtů: stroje RAM a vzájemná simulace s TS. Připomenutí složitosti algoritmů a tříd složitosti, speciálně tříd PTIME a NPTIME. Další třídy složitosti: Třída PSPACE, třída NPSPACE a Savitchova věta. PSPACE-úplné problémy. Třídy EXPTIME a EXPSPACE. Třídy paměťové složitosti L a NL. Alternující Turingovy stroje a příslušné třídy složitosti, s jejich vztahem ke standardním třídám. Paralelní algoritmy, výpočetní obvody, a třídy AC, NC. PTIME-úplnost. Polynomiální hierarchie. Pravděpodobnostní algoritmy a příslušné třídy složitosti.
|
|
Studijní aktivity a metody výuky
|
|
Přednášení, Demonstrace
|
|
Výstupy z učení
|
Studenti si prohloubí a rozšíří znalosti z oblasti složitosti algoritmů a problémů.
1. Znalost Popsat a důkladně pochopit principy a metody teorie složitosti.
|
|
Předpoklady
|
nespecifikováno
|
|
Hodnoticí metody a kritéria
|
Ústní zkouška, Písemná zkouška
Aktivní účast v hodině. Plnění zadaných úkolů. Složení ústní (příp. písemné) zkoušky.
|
|
Doporučená literatura
|
-
Arora S., Barak B. (2009). Computational Complexity: A Modern Approach. Cambridge Univ. Press.
-
Kozen D. (2006). Theory of Computation. Springer-Verlag, London.
-
Kučera, L. (1989). Kombinatorické algoritmy. SNTL Praha.
-
Papadimitriou, C. H. (1995). Computational Complexity. Addison-Wesley, Reading (MA).
-
Sipser M. (2013). Introduction to the Theory of Computation (Third Edition). Cengage Learning, Boston, MA, USA.
|