FPF:UIDI011 Teorie vyčíslitelnosti a složi - Informace o předmětu
UIDI011 Teorie vyčíslitelnosti a složitosti
Filozoficko-přírodovědecká fakulta v Opavěléto 2019
- Rozsah
- 0/0. 0 kr. Ukončení: dzk.
- Garance
- doc. Ing. Petr Sosík, Dr.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě - Předpoklady
- - základy teorie formálních jazyků a automatů
- základní kurs algebry a matematické analýzy
- základy výrokové logiky
- základy teorie grafů
- procedurální programování a znalost základních algoritmů (třídění, vyhledávání, grafové algoritmy)
- Omezení zápisu do předmětu
- Předmět je nabízen i studentům mimo mateřské obory.
- Mateřské obory/plány
- Autonomní systémy (program FPF, P1801 Inf) (2)
- Autonomous Systems (program FPF, P1801 Inf) (2)
- Cíle předmětu
- Jsou předvedeny základní abstraktní modely výpočtu - Turingův stroj a stroj RAM. Na jejich bázi je vybudován koncept strojové vyčíslitelnosti, ukázána existence nevyčíslitelných problémů a jejich typické příklady. Dále je zavedena asymptotická výpočetní složitost algoritmů, umožňující porovnávat spotřebu paměti a strojového času bez vazby na konkrétní počítač. Obsahová náplň cvičení vychází a časově sleduje obsahovou náplň přednášky.
- Osnova
- Charakterizace mechanických výpočtů, Turingova - Churchova teze.
2. Turingův stroj a jeho varianty, univerzální Turingův stroj.
3. Rekurzívní a rekurzívně spočetné množiny, metoda diagonalizace.
4. Rozhodnutelné a nerozhodnutelné problémy, metoda redukce.
5. Riceova věta, aplikace teorie vyčíslitelnosti v praxi.
6. Výpočet spotřeby času a paměti počítačových algoritmů.
7. Třídy DTIME a DSPACE. Nedeterministický Turingův stroj, třídy NTIME a NSPACE.
8. Stroj RAM a jeho výpočetní síla. Vztahy Turingova stroje a RAM.
9. Věta o urychlení a věta o kompresi, základní složitostní třídy.
10. Časová a prostorová hierarchie.
11. Vztahy časových a prostorových složitostních tříd.
12. Redukovatelnost a úplnost, NP-úplné problémy.
- Charakterizace mechanických výpočtů, Turingova - Churchova teze.
- Literatura
- povinná literatura
- Sosík, P. Teorie vyčíslitelnosti. Online studijní text. Opava: FPF SU, 1996. info
- Černá, I. Úvod do teórie zložitosti. Brno: FI MU, 1993. info
- doporučená literatura
- Hopcroft, J. E., Motwani, R., Ullman, J. D. Introduction to Automata Theory, Languages and Computation. Upper Saddle River: Pearson Education Inc.,, 2003. info
- Výukové metody
- Přednášení
Přednáška s aktivizací
Přednáška s analýzou videozáznamu - Metody hodnocení
- Zkouška
- Informace učitele
- Zápočet:
- vypracování Turingova stroje dle individuálního zadání
- nejméně 50% bodů z dílčích zápočtových písemek na seminářích
Zkouška:
- nejméně 50% bodů ze zkouškové písemky zahrnující celý rozsah látky - Další komentáře
- Předmět je dovoleno ukončit i mimo zkouškové období.
- Statistika zápisu (léto 2019, nejnovější)
- Permalink: https://is.slu.cz/predmet/fpf/leto2019/UIDI011