Předmět Vyčíslitelnost a složitost (KMI / VCSAV)
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 / VCSAV - 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
Úvod do vyčíslitelnosti: Definice Turingova stroje (TS), formalizace pojmu výpočet (konfigurace, apod.), jazyk přijímaný TS, jazyk rozhodovaný TS, turingovsky vyčíslovaná funkce, Church-Turingova teze.Varianty TS: TS s oboustranně nekonečnou páskou, vícepáskový TS a jejich ekvivalence se základní verzí TS.Univerzální TS: Definice, popis činnosti.Jazyky a problémy: Částečně rekurzivní a rekurzivní jazyky, rozhodovací problémy, převoditelnost rozhodovacích problémů na jazyky, existence jazyků, které nejsou částečně rekurzivní.Jazyky, které nejsou rekurzivní, a problémy, které nejsou řešitelné: Problém zastavení TS, Postův problém přiřazení a jeho aplikace.Další modely výpočtů: Postovy stroje, nedeterministické TS, pravděpodobnostní TS.Složitost: složitost algoritmu a problému.Základní třídy složitostí: Třída P, třída NP, NP-úplné problémy, vybrané NP-úplné problémy, dokazování NP-úplnosti.Užití obtížně řešitelných problémů: Kryptografie, metoda RSA.
Získané způsobilosti
1. ZnalostRozpoznej neřešitelné a řešitelné problémy a jejich výpočetní složitost.
Literatura
Kozen D. C. Automata and Computability. Springer, 1997. ISBN 0-387-94907-0.Papadimitriou, C. H. Computational Complexity. Addison-Wesley, Reading (MA), 1995. ISBN 0201530821.Lewis H. R., Papadimitriou C. H. Computational Complexity. Reading (Mass.), Addison Wesley, 1994. ISBN 0-201-53082-1.Hopcroft J. E., Motwani R., Ullmann J. D. Introduction to Automata Theory, Languages, and Computation. Pearson Education, 2003. ISBN 0-321-21029-8.Sipser M. Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA, 1997. ISBN 0-534-94728-X.Kučera L. Kombinatorické algoritmy. Praha, SNTL, 1989. Koubková, A., Pavelka, J. Úvod do teoretické informatiky. Matfyzpress, Praha, 1998. ISBN 8085863332.
Požadavky
Aktivní účast v hodině. Plnění zadaných úkolů. Složení ústní (příp. písemné) zkoušky.
Garant
prof. RNDr. Radim Bělohlávek, Ph.D., DSc.
Vyučující
Mgr. Jan Konečný, Ph.D.Mgr. Jan Konečný, Ph.D.