|
Vyučující
|
-
Jančar Petr, prof. RNDr. CSc.
|
|
Obsah předmětu
|
Ú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. </ol>
|
|
Studijní aktivity a metody výuky
|
|
Přednášení, Demonstrace
|
|
Výstupy z učení
|
Studenti se seznámí se základními pojmy z vyčíslitelnosti a složitosti.
1. Znalost Rozpoznej neřešitelné a řešitelné problémy a jejich výpočetní složitost.
|
|
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
|
-
Copeland B.J. et al. (2015). Computability: Turing, Goedel, Church, and Beyond. MIT Press.
-
Hopcroft J. E., Motwani R., Ullmann J. D. (2003). Introduction to Automata Theory, Languages, and Computation. Pearson Education.
-
Koubková, A., Pavelka, J. (1998). Úvod do teoretické informatiky. Matfyzpress, Praha.
-
Kozen D. C. (1997). Automata and Computability. Springer.
-
Kučera, L. (1989). Kombinatorické algoritmy. SNTL, Praha.
-
Lewis, H. R., Papadimitriou, C. H. (1998). Elements of the Theory of Computation. Prentice Hall, Upper Saddle River (NJ).
-
Papadimitriou, C. H. (1995). Computational Complexity. Addison-Wesley, Reading (MA).
-
Sipser M. (1997). Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA.
|