UIIABP0022 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 B3a
  • Rozvrh seminárních/paralelních skupin:
UIIABP0022/A: St 18:05–19:40 B3b, J. Schreier
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 2023.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.slu.cz/predmet/fpf/zima2024/UIIABP0022