Předmět Vyčíslitelnost a složitost (IB107)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu IB107 - Vyčíslitelnost a složitost, Fakulta informatiky, Masarykova univerzita (MU).

Materiál	Typ	Datum	Počet stažení

Cíl

Smyslem kurzu je objasnit základní přístupy a metody klasifikaceproblémů z hlediska možnosti jejich algoritmického řešení a provéstzákladní klasifikaci. Současně chce kurz poukázat na teoretické apraktické 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 0-387-94907-0. infoSIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. infoBOVET, D. a Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994. xi, 282 s. ISBN 0-13-915380-2. infoKFOURY, 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

Požadavky

IB005 FJA || IB102 Automaty, gramatiky, složitost

Garant

prof. RNDr. Mojmír Křetínský, CSc.

Vyučující

prof. RNDr. Luboš Brim, CSc.Bc. Tomáš EffenbergerMgr. Bc. Tomáš JaníkBc. Samuel Pastva