Vyčíslitelnost a složitost

Zkratka předmětu KMI/VS
Název předmětu Vyčíslitelnost a složitost
Akademický rok 2020/2021
Pracoviště / Zkratka KMI/VS
Název Vyčíslitelnost a složitost
Akreditováno/Kredity Ano/6
Rozsah hodin Přednáška 2 HOD/TYD Cvičení 2 HOD/TYD
Vyučovací jazyk čeština
Nahrazovaný předmět
Vyloučené předměty
Podmiňující
Způsob zakončení Zkouška
Forma zakončení Kombinovaná
Zápočet před zkouškou Ano
Vyučovaný semestr Zimní
Cíle předmětu (anotace)

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í.

Požadavky na studenta

Vypracování zadaných úloh z cvičení, aktivní účast na cvičeních formou prezentace studentských řešení problémů.

Obsah

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

Předpoklady - další informace k podmíněnosti studia předmětu

Základní znalosti algoritmů a diskrétní matematiky.

Získané způsobilosti

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í.

Garanti a vyučující
  • Garanti: doc. Ing. Ladislav Beránek, CSc.
  • Přednášející: doc. Ing. Ladislav Beránek, CSc.
  • Cvičící: doc. Ing. Ladislav Beránek, CSc., Mgr. Michal Houda, Ph.D.
Literatura
  • null
  • DEMUTH, Osvald, Antonín KUČERA a Rudolf KRYL. Teorie algoritmů. 2. vyd. Praha: Státní pedagogické nakladatelství, 1989.
  • ARORA, Sanjeev a Boaz BARAK. Computational complexity: a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 978-0-521-42426-4.
  • SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing, 1997. ISBN 0-534-94728-X.
Vyučovací metody

Monologická (výklad, přednáška, instruktáž), Práce s textem (učebnicí, knihou)

Hodnotící metody

Kombinovaná zkouška, Seminární práce, Průběžné hodnocení

Stáhnout jako PDF