Předmět Vyčíslitelnost a složitost (KMI / VS)
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 / VS - 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.Vztah rekurzivních a částečně rekurzivních jazyků k jazykům Chomského hierarchie.Další výsledky: Riceova věta, věta o rekurzi a jejich 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.Další třídy složitostí: Třída PSPACE, třída NPSPACE, PSPACE-úplné problémy.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. Elements of the Theory of Computation. Prentice Hall, Upper Saddle River (NJ), 1998. ISBN 0132624788.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. SNTL, Praha, 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.