IB107 Vyčíslitelnost a složitost

Fakulta informatiky
podzim 2015
Rozsah
2/2. 4 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í)
Bc. Tomáš Effenberger (cvičící)
Mgr. Bc. Tomáš Janík (cvičící)
Mgr. Samuel Pastva (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
Út 10:00–11:50 D1
  • Rozvrh seminárních/paralelních skupin:
IB107/T01: Út 22. 9. až Út 22. 12. Út 15:00–16:35 KOM 116, T. Janík, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IB107/01: Čt 14:00–15:50 B204, S. Pastva
IB107/02: Čt 12:00–13:50 B411, T. Effenberger
IB107/03: Pá 8:00–9:50 C416, S. Pastva
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
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ě.
Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2006, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2016, podzim 2017.

Nahoru | Aktuální datum a čas: 22. 9. 2017 20:49, 38. (sudý) týden

Kontakty: istech(zavináč/atsign)fi(tečka/dot)muni(tečka/dot)cz, studijní odd., správci práv, is-technici, e-technici, IT podpora | Použití cookies | Více o Informačním systému