FPF:UIINK25 Vyčíslitelnost a složit. výp. - Informace o předmětu

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

Rozsah

12/0/0. Přednáška 12 HOD/SEM. 6 kr. Ukončení: zk.

Vyučující

Mgr. Daniel Valenta, Ph.D. (přednášející)
Mgr. Jan Schreier (cvičící)

Garance

Mgr. Daniel Valenta, Ph.D.
Ú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 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

Studijní materiály
Předmět je dovoleno ukončit i mimo zkouškové období.

• Statistika zápisu (nejnovější)
  
• Permalink: https://is.slu.cz/predmet/fpf/zima2024/UIINK25