UIN1018 Teorie vyčíslitelnosti a složitosti

Filozoficko-přírodovědecká fakulta v Opavě
zima 2014
Rozsah
2/2/0. 6 kr. Ukončení: zk.
Vyučující
doc. Ing. Petr Sosík, Dr. (přednášející)
RNDr. Miroslav Langer, Ph.D. (cvičící)
Jesús Miró, PhD. (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
- 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
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.
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
    neurčeno
  • Sipser, M. Introduction to the Theory of Computation. Boston, 2006. ISBN 978-0-619-21764-2. info
  • Wiedermann, J. Teorie složitosti sekvenčních a paralelních výpočtů. Online studijní text. ÚI AV ČR, Praha, 2003. info
Metody hodnocení
Známkou
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 1993, zima 1994, zima 1995, zima 1996, zima 1997, zima 1998, zima 1999, zima 2000, zima 2001, zima 2002, zima 2003, zima 2004, zima 2006, zima 2007, zima 2008, zima 2009, zima 2010, zima 2011, zima 2012, zima 2013, zima 2015, zima 2016, zima 2017, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022.