UIBUC15 Teorie vyčíslitelnosti a složitosti

Filozoficko-přírodovědecká fakulta v Opavě
zima 2013
Rozsah
2/2/0. 5 kr. Ukončení: zk.
Vyučující
doc. Ing. Petr Sosík, Dr. (přednášející)
RNDr. Miroslav Langer, Ph.D. (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
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
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.
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í.
Předmět je zařazen také v obdobích zima 2010, zima 2011, zima 2012, zima 2014, zima 2015, zima 2016, zima 2017, zima 2018, zima 2019, zima 2020, zima 2021.