FPF:UINK118 Teorie vyčíslitelnosti a složi - Informace o předmětu

UINK118 Teorie vyčíslitelnosti a složitosti

Rozsah

6/6/0. Přednáška 6 HOD/SEM, Cvičení 6 HOD/SEM. 6 kr. Ukončení: zk.

Vyučující

doc. Ing. Petr Sosík, Dr. (přednášející)
doc. Ing. Petr Sosík, Dr. (cvičící)

Garance

doc. Ing. Petr Sosík, Dr.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě

Předpoklady

( UIAI019 Zákl. teoretické informat. II || UIAI219 Základy teoretické informatiky || UIBUC09 Teorie jazyků a automatů II || UINK106 Teorie jazyků a automatů II || UIN1006 Teorie jazyků a automatů II ) && TYP_STUDIA ( B ) && ! UIAI232 Teorie vyčíslitelnosti a složi
- 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

• Aplikovaná informatika (program FPF, B1802 AplI)
• Informatika a výpočetní technika (program FPF, B1801 Inf)

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.

Výstupy z učení

Studenti budou schopni rozlišit v praxi počítačově vyčíslitelné a nevyčíslitelné problémy. Budou schopni určit alespoň v základních rysech výpočetní složitost daného problému a přizpůsobit tomu způsob jeho algoritmického řešení.

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.
  

Literatura

doporučená literatura
• Arora, S., Barak, B. Complexity Theory: A Modern Approach. Cambridge University Press, 2009. info
• Kozen, D. Theory of Computation. Berlin: Springer-Verlag, 2006. info
• Hopcroft, J. E., Motwani, R., Ullman, J. D. Introduction to Automata Theory, Languages and Computation. Upper Saddle River: Pearson Education Inc.,, 2003. info
• Wiedermann, J. Teorie složitosti sekvenčních a paralelních výpočtů. Online studijní text. ÚI AV ČR, Praha, 2003. info
• 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

neurčeno
• Sipser, M. Introduction to the Theory of Computation. Boston, 2006. ISBN 978-0-619-21764-2. 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 (nejnovější)
  
• Permalink: https://is.slu.cz/predmet/fpf/zima2022/UINK118