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

Filozoficko-přírodovědecká fakulta v Opavě
zima 2024
Rozsah
2/2/0. 6 kr. Ukončení: zk.
Vyučující
doc. Ing. Petr Sosík, Dr. (přednášející)
Mgr. Daniel Valenta, Ph.D. (přednášející)
Mgr. Jan Schreier (cvičící)
doc. Ing. Petr Sosík, Dr. (cvičící)
Mgr. Daniel Valenta, Ph.D. (cvičící)
Garance
doc. Ing. Petr Sosík, Dr.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Rozvrh
St 14:45–16:20 B3b
  • Rozvrh seminárních/paralelních skupin:
UIMOIBP017/A: St 18:05–19:40 B3b, J. Schreier
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
Další komentáře
Studijní materiály
Předmět je zařazen také v obdobích zima 2020, zima 2021, zima 2022, zima 2023.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.slu.cz/predmet/fpf/zima2024/UIMOIBP017