FI:IB107 Vyčíslitelnost a složitost - Informace o předmětu
IB107 Vyčíslitelnost a složitost
Fakulta informatikypodzim 2012
- 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í)
RNDr. Mgr. Jana Dražanová, Ph.D. (cvičící)
doc. RNDr. Milan Češka, Ph.D. (pomocník) - 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
- Čt 10:00–11:50 D2
- Rozvrh seminárních/paralelních skupin:
IB107/02: Čt 15:00–15:50 G123, J. Dražanová
IB107/03: Čt 16:00–16:50 G123, J. Dražanová - Předpoklady
- IB005 FJA I || IB102 Automaty a gramatiky
- 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
- Aplikovaná informatika (program FI, B-AP)
- Bioinformatika (program FI, B-AP)
- Informatika a druhý obor (program FI, B-BI)
- Informatika a druhý obor (program FI, B-EB)
- Informatika a druhý obor (program FI, B-FY)
- Informatika a druhý obor (program FI, B-GE)
- Informatika a druhý obor (program FI, B-GK)
- Informatika a druhý obor (program FI, B-CH)
- Informatika a druhý obor (program FI, B-IO)
- Informatika a druhý obor (program FI, B-MA)
- Informatika a druhý obor (program FI, B-SO)
- Informatika a druhý obor (program FI, B-TV)
- Informatika (program FI, B-IN)
- Matematická informatika (program FI, B-IN)
- Paralelní a distribuované systémy (program FI, B-IN)
- Počítačová grafika a zpracování obrazu (program FI, B-IN)
- Počítačové sítě a komunikace (program FI, B-IN)
- Počítačové systémy a zpracování dat (program FI, B-IN)
- Programovatelné technické struktury (program FI, B-IN)
- Programovatelné technické struktury (program FI, N-IN)
- Služby - výzkum, řízení a inovace (program FI, N-AP)
- Sociální informatika (program FI, B-AP)
- Umělá inteligence a zpracování přirozeného jazyka (program FI, B-IN)
- 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í.
Hlavní cíle kurzu jsou: 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 2012, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/podzim2012/IB107