Předmět Vyčíslitelnost a složitost (KMI / PGSVS)
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 KMI / PGSVS - Vyčíslitelnost a složitost, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
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říkladyproblé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.
Získané způsobilosti
1. ZnalostPopsat a důkladně pochopit principy a metody vyčíslitelnosti a složitosti.
Literatura
Sedgewick S., Flajolet P. Analysis of Algorithms. Addison-Wesley, 1996. ISBN 0-201-40009-X.Kozen D. C. Automata and Computability. Springer, 1997. ISBN 0-387-94907-0.Lewis H. R., Papadimitriou C. H. Computational Complexity. Reading (Mass.), Addison Wesley, 1994. ISBN 0-201-53082-1.Gruska J. Foundations of Computing. International Thompson Computer Press, 1997. Leeuwen van, J. Handbook of Theoretical Computer Science, Vol. A: Algorithms. The MIT Press, 1994. ISBN 0-262-72014-0.Hopcroft J. E., Motwani R., Ullman J. D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston, 2006. ISBN 978-0321462251.Sipser M. Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA, 1997. ISBN 0-534-94728-X.Kozen D. C. The Design And Analysis of Algorithms. Springer, 1991. ISBN 0-387-97687-6.
Požadavky
Aktivní účast v hodině. Plnění zadaných úkolů. Složení ústní (příp. písemné) zkoušky.
Garant
doc. Ing. Lenka Motyčková, CSc.
Vyučující
doc. Ing. Lenka Motyčková, CSc.