FI:IB107 Vyčíslitelnost a složitost - Informace o předmětu
IB107 Vyčíslitelnost a složitost
Fakulta informatikypodzim 2013
- Rozsah
- 2/1. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: z.
- Vyučující
- prof. RNDr. Luboš Brim, CSc. (přednášející)
doc. RNDr. Milan Češka, Ph.D. (cvičící) - Garance
- prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Luboš Brim, CSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky - Rozvrh
- St 12:00–13:50 D2
- Rozvrh seminárních/paralelních skupin:
IB107/02: Čt 13:00–13:50 G330, M. Češka
IB107/03: Út 17:00–17:50 B411, M. Češka - Předpoklady
- IB005 FJA || IB102 Automaty, gramatiky, složitost
- 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
- předmět má 23 mateřských oborů, zobrazit
- Cíle předmětu
- Smyslem kurzu je objasnit základní přístupy a metody klasifikace
problémů z hlediska možnosti jejich algoritmického řešení a provést
základní klasifikaci. Současně chce kurz poukázat na teoretické a
praktické meze využití počítačů a důsledky, které tato omezení mají
pro rozvoj informačních technologií.
Po skončení kurzu budou studenti schopni: porozumět základním pojmům formalizujícím algoritmickou řešitelnost; zvládnout klasifikační techniky redukce, diagonalizace a uzávěrové vlastnosti; umět tyto techniky aplikovat na jednoduche situace. - Osnova
- Algoritmus jako výpočetní model. Churchova teze.
- Klasifikace problémů. Rozhodnutelné, nerozhodnutelné a částečně rozhodnutelné problémy. Vyčíslitelné funkce.
- Uzávěrové vlastnosti, Riceovy věty.
- Výpočetní složitost problémů. Výpočetně těžké a lehké problémy.
- Redukce a úplnost v třídách problémů. Redukce a polynomiální redukce. Úplné problémy z hlediska rozhodnutelnosti, NP-úplné problémy. Aplikace.
- Literatura
- KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
- SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
- BOVET, D. a Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info
- KFOURY, A. J., Robert N. MOLL a Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982, viii, 251. ISBN 0-387-90743-2. info
- Výukové metody
- přednáška, cvičení, domácí úkoly
- Metody hodnocení
- Přednáška je doplněna povinnými cvičeními. Během semestru jsou studentům zadávány domácí úkoly. Zkouška je písemná. Požadavkem k připuštění ke zkoušce je získání daného počtu bodů za domácí úkoly. Tyto body se rovněž započítavájí do celkového hodnocení. Pomocné materiály nejsou při zkoušce povoleny.
- Navazující předměty
- Informace učitele
- http://www.fi.muni.cz/usr/brim/IB107
- Další komentáře
- Studijní materiály
Předmět je vyučován každoročně. - Nachází se v prerekvizitách jiných předmětů
- Statistika zápisu (podzim 2013, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2013/IB107