|
Vyučující
|
-
Jančar Petr, prof. RNDr. CSc.
|
|
Obsah předmětu
|
Předmět obsahuje vybrané pokročilé partie vyčíslitelnosti a složitosti. Diagonalizace a její limity: hierarchické věty, relativizace. Prostorová složitost: třídy PSPACE a NL a úplnosti. Polynomická hierarchie a alterace. Booleovské okruhy: neuniformní modely výpočtu, třída P/poly. Interaktivní dokazovací systémy: třída IP a pravděpodobností 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
|
|
Přednášení
|
|
Výstupy z učení
|
Studenti se seznámí se základními pojmy z 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, 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
|
-
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.
-
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. (1997). Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA.
|