FPF:UIINP25 Vyčíslitelnost a složitost výp - Informace o předmětu

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

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:

UIINP25/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

• Informatika (program FPF, INFOR-bpk)

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 (nejnovější)
  
• Permalink: https://is.slu.cz/predmet/fpf/zima2024/UIINP25