|
Vyučující
|
-
Beránek Ladislav, prof. Ing. CSc., MBA
-
Houda Michal, Mgr. Ph.D.
-
Klán Petr, doc. Mgr. Ing. CSc.
|
|
Obsah předmětu
|
Témata: 1. Motivační příklad. Definice Turingova stroje, varianty TS. 2. Převod k-páskového Turingova stroje na jednopáskový. RAM a jeho ekvivalence s Turingovými stroji. 3. Algoritmus jako výpočetní model. Churchova teze. 4. Klasifikace problémů. Rozhodnutelné, nerozhodnutelné a částečně rozhodnutelné problémy. Vyčíslitelné funkce. 5. Uzávěrové vlastnosti, Riceovy věty. Výpočetní složitost problémů. 6. Redukce a úplnost v třídách problémů. 7. Redukce a polynomiální redukce. 8. Úplné problémy z hlediska rozhodnutelnosti, NP-úplné problémy. 9. Třída paměťové složitosti PSPACE a NPSPACE-úplné problémy. 10. Aproximační algoritmy a schémata. 11. Aplikace
|
|
Studijní aktivity a metody výuky
|
|
Monologická (výklad, přednáška, instruktáž), Práce s textem (učebnicí, knihou)
|
|
Výstupy z učení
|
Cílem předmětu 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. Studenti porozumí základním pojmům formalizujícím algoritmickou řešitelnost budou umět aplikovat probírané techniky na některé situace, porozumí teoretickým a praktickým mezím využití počítačů a důsledkům, které tato omezení mají pro rozvoj informačních technologií.
Studenti porozumí základním pojmům formalizujícím algoritmickou řešitelnost budou umět aplikovat probírané techniky na některé situace, porozumí teoretickým a praktickým mezím využití počítačů a důsledkům, které tato omezení mají pro rozvoj informačních technologií.
|
|
Předpoklady
|
Základní znalosti algoritmů a diskrétní matematiky.
|
|
Hodnoticí metody a kritéria
|
Kombinovaná zkouška, Seminární práce, Průběžné hodnocení
Vypracování zadaných úloh z cvičení, aktivní účast na cvičeních formou prezentace studentských řešení problémů.
|
|
Doporučená literatura
|
-
ARORA, Sanjeev a Boaz BARAK. Computational complexity: a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 978-0-521-42426-4.
-
DEMUTH, Osvald, Antonín KUČERA a Rudolf KRYL. Teorie algoritmů. 2. vyd. Praha: Státní pedagogické nakladatelství, 1989.
-
SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing, 1997. ISBN 0-534-94728-X.
|