|
Vyučující
|
-
Jančar Petr, prof. RNDr. CSc.
|
|
Obsah předmětu
|
Předmět se zaměřuje na vybrané pokročilé partie vyčíslitelnosti a složitosti, např. následující: Diagonalizace a její limity: hierarchické věty, relativizace. Prostorová složitost: třídy PSPACE a NL úplnosti. Polynomiální hierarchie a alternace. Booleovské okruhy: neuniformní modely výpočtu, třída P/poly. Interaktivní dokazovací systémy: třída IP a pravděpodobnostní verifikátory, věta IP=PSPACE. PCP teorém a aproximovatelnost: přibližná řešení těžkých problémů, varianty PCP teorému, neaproximovatelnost. Složitost počítacích problémů (counting problems): příklady problémů, třída \#P a \#P-úplnost, Todova věta. Úvod do složitosti v průměrném případě: třídy distP a distNP.
|
|
Studijní aktivity a metody výuky
|
|
Dialogická (diskuze, rozhovor, brainstorming), Metody práce s textem (učebnicí, knihou)
|
|
Výstupy z učení
|
Studenti se seznámí se základními a vybranými pokročilejšími pojmy a metodami z teorie vyčíslitelnosti a složitosti.
1. Znalost Popsat a důkladně pochopit principy a metody vyčíslitelnosti a složitosti.
|
|
Předpoklady
|
nespecifikováno
|
|
Hodnoticí metody a kritéria
|
Ústní zkouška
Plnění zadaných úkolů. Složení zkoušky.
|
|
Doporučená literatura
|
-
Arora S., Barak B. (2009). Computational Complexity: A Modern Approach. Cambridge Univ. Press.
-
Gruska J. (1997). Foundations of Computing. International Thompson Computer Press.
-
Hopcroft J. E., Motwani R., Ullman J. D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston.
-
Kozen D. C. (1997). Automata and Computability. Springer.
-
Kozen D. C. (1991). The Design And Analysis of Algorithms. Springer.
-
Kozen D. (2006). Theory of Computation. Springer-Verlag, London.
-
Kučera, L. (1989). Kombinatorické algoritmy. SNTL Praha.
-
Leeuwen van, J. (1994). Handbook of Theoretical Computer Science, Vol. A: Algorithms. The MIT Press.
-
Lewis H. R., Papadimitriou C. H. (1994). Computational Complexity. Reading (Mass.), Addison Wesley.
-
Sedgewick S., Flajolet P. (1996). Analysis of Algorithms. Addison-Wesley.
-
Sipser M. (2013). Introduction to the Theory of Computation (Third Edition). Cengage Learning, Boston, MA, USA.
|