UIMOIBK017 Vyčíslitelnost a složitost výpočtů

Filozoficko-přírodovědecká fakulta v Opavě
zima 2021
Rozsah
12 hod/sem. 6 kr. Ukončení: zk.
Vyučující
doc. Ing. Petr Sosík, Dr. (přednášející)
Garance
doc. Ing. Petr Sosík, Dr.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Předpoklady
Teorie jazyků a automatů I
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
Předmět se zabývá problémy strojové vyčíslitelnosti a obtížnosti problémů. V první části předmětu - teorii vyčíslitelnosti, se zkoumá, které problémy je možno na počítačích vyřešit a které ne. Druhá část předmětu - teorie složitosti - pak studuje podrobněji řešitelné problémy. Budeme se zajímat, kolik času a paměti je na jejich vyřešení zapotřebí a podle toho rozdělíme problémy do různých tříd podle jejich obtížnosti.
Výstupy z učení
Student bude po absolvování předmětu schopen:
- popsat třídu problémů, které lze strojově vyřešit
- analyzovat situaci, kdy problém strojově řešitelný není
- porovnat jednotlivé problémy z hlediska složitosti jejich řešení
Osnova
  • 1. Turingův stroj - model mechanického výpočtu
  • 2. Rekurzívní a rekurzívně spočetné množiny, metoda diagonalizace
  • 3. Rozhodnutelné a nerozhodnutelné problémy, metoda redukce
  • 4. Riceho věta
  • 5. Úvod do výpočetní složitosti, asymptotiky
  • 6. Časová a prostorová složitost algoritmů
  • 7. Stroj RAM: realistický model počítače
  • 8. Výpočetní složitost běžných programů
  • 9. Základní složitostní třídy
  • 10. Vztahy mezi složitostními třídami
  • 11. NP-úplné problémy
  • 12. Aplikace: Dynamické programování
Literatura
    povinná literatura
  • SOSÍK, P. Teorie vyčíslitelnosti. Online studijní text. Opava: FPF SU, 2017
  • SIPSER, Michael. Introduction to the theory of computation. 3rd ed. Boston, MA: Course Technology CengageLearning, 2012. ISBN 978-1-133-18779-0. info
    doporučená literatura
  • HOPCROFT, JOHN E, Rajeev MOTWANI a JEFFREY D ULLMAN. Introduction to automata theory, languages, and computation. Harlow: Pearson Addison-Wesley, 2014. ISBN 978-1-292-03905-3. info
  • DU, Dingzhu a Ker-I KO. Theory of computational complexity. Second edition. Hoboken, New Jersey: Wiley, 2014. ISBN 978-1-118-30608-6. info
  • Černá, I. Úvod do teórie zložitosti. Brno: FI MU, 1993. info
Výukové metody
Přednášení
Přednáška s aktivizací
Metody hodnocení
Zápočet:
- vypracování Turingova stroje dle individuálního zadání
- dílčí zápočtové písemky na seminářích
Zkouška:
- písemná zkouška, semestrální práce, individuální projekt
Předmět je zařazen také v obdobích zima 2020, zima 2022, zima 2023, zima 2024.