IB107 Vyčíslitelnost a složitost

Fakulta informatiky
podzim 2006
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. Jan Bouda, Ph.D. (cvičící)
prof. RNDr. Jan Strejček, Ph.D. (cvičící)
RNDr. Jakub Chaloupka, Ph.D. (pomocník)
Mgr. Pavel Moravec (pomocník)
RNDr. Pavel Šimeček, 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.
Rozvrh
Čt 10:00–11:50 D2
  • Rozvrh seminárních/paralelních skupin:
IB107/01: St 14:00–14:50 B007, J. Bouda
IB107/02: St 15:00–15:50 B007, J. Bouda
IB107/03: Čt 12:00–12:50 B007, J. Strejček
IB107/04: Čt 13:00–13:50 B007, J. Strejček
Předpoklady
IB005 FJA I || I005 FJA I || I505 FJA 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
Cíle předmětu
Cílem 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í.
Osnova
  • Problémy a algoritmy.
  • Algoritmus jako výpočetní model. Základní výpočetní modely. Churchova teze.
  • Klasifikace problémů. Rozhodnutelné, nerozhodnutelné a částečně rozhodnutelné problémy.
  • Postův korespondenční problém. Vybrané nerozhodnutelné problémy z teorie jazyků.
  • 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.
  • Nesekvenční výpočetní modely. Paralelní výpočtová teze.
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
Metody hodnocení
Zkouška je písemná a ústní. V případě zadání průběžných testů během semestru, mají tyto podíl nejvýše 30% na závěrečném hodnocení. Pomocné materiály nejsou povoleny.
Navazující předměty
Informace učitele
http://www.fi.muni.cz/usr/brim/IB107
Další komentáře
Předmět je vyučován každoročně.
Nachází se v prerekvizitách jiných předmětů
Předmět je zařazen také v obdobích podzim 2003, podzim 2004, podzim 2005, podzim 2007, podzim 2008, podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.