Předmět Teorie vyčíslitelnosti a složitosti (UI / N1018)
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 UI / N1018 - Teorie vyčíslitelnosti a složitosti, Filozoficko-přírodovědecká fakulta, Slezská univerzita v Opavě (SU).
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
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.
Získané způsobilosti
Teoretické porozumění tématům obsahového vymezení předmětu. Praktické dovednosti při práci s jednotlivými tématy.
Literatura
Sosík, P. Teorie vyčíslitelnosti. Online studijní text. Opava: FPF SU, 1996. Černá, I. Úvod do teórie zložitosti. Brno: FI MU, 1993. Sipser, M. Introduction to the Theory of Computation. Boston, 2006. ISBN 978-0-619-21764-2.Wiedermann, J. Teorie složitosti sekvenčních a paralelních výpočtů. Online studijní text. ÚI AV ČR, Praha, 2003. Hopcroft, J. E., Motwani, R., Ullman, J. D. Introduction to Automata Theory, Languages and Computation. Upper Saddle River: Pearson Education Inc.,, 2003.
Požadavky
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áříchZkouška:- nejméně 50% bodů ze zkouškové písemky zahrnující celý rozsah látky
Garant
Doc. Ing. Petr SOSÍK, Dr.
Vyučující
Doc. Ing. Petr SOSÍK, Dr.RNDr. Miroslav LANGER, Ph.D.Jesús MIRÓ, PhD.