FPF:UIINP25 Vyčíslitelnost a složitost výp - Informace o předmětu
UIINP25 Vyčíslitelnost a složitost výpočtů
Filozoficko-přírodovědecká fakulta v Opavězima 2019
- Rozsah
- 2/2/0. 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
- TYP_STUDIA ( B )&& UIINP11 Teorie jazyků a automatů I
- Omezení zápisu do předmětu
- Předmět je otevřen studentům libovolného oboru.
- 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
- Předmět je dovoleno ukončit i mimo zkouškové období.
- Statistika zápisu (zima 2019, nejnovější)
- Permalink: https://is.slu.cz/predmet/fpf/zima2019/UIINP25