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

Filozoficko-přírodovědecká fakulta v Opavě
zima 2023
Rozsah
2/2/0. 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ě
Rozvrh
St 9:45–11:20 B3b
  • Rozvrh seminárních/paralelních skupin:
UIIABP0022/A: St 11:25–13:00 B3b, P. Sosík
Předpoklady
- základy výrokové logiky - základy teorie grafů - základy procedurálního programování
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. 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
  • 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
  • SIPSER, Michael. Introduction to the theory of computation. 3rd ed. Boston, MA: Course Technology CengageLearning, 2012. ISBN 978-1-133-18779-0. info
  • Sosík, P. Teorie vyčíslitelnosti. Online studijní text. Opava: FPF SU, 1996. 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áška, cvičení
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 2024.