460-6004/04 – Teorie algoritmů (TA)
| Garantující katedra | Katedra informatiky | Kredity | 10 |
| Garant předmětu | doc. Ing. Zdeněk Sawa, Ph.D. | Garant verze předmětu | doc. Ing. Zdeněk Sawa, Ph.D. |
| Úroveň studia | postgraduální | Povinnost | povinně volitelný typu B |
| Ročník | | Semestr | zimní + letní |
| | Jazyk výuky | angličtina |
| Rok zavedení | 2019/2020 | Rok zrušení | 2024/2025 |
| Určeno pro fakulty | USP, FEI | Určeno pro typy studia | doktorské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Student po úspěšném absolvování předmětu:
- rozumí základním pojmům v oblasti algoritmické vyčíslitelnosti a výpočetní složitosti
- umí navrhovat vhodné algoritmy pro praktické problémy
- umí analyzovat složitost algoritmů a zařazovat problémy do tříd složitosti
- zvládá i návrh a analýzu aproximačních, pravděpodobnostních a paralelních algoritmů
- prokáže schopnost samostatně zvládnout a odprezentovat pokročilou partii v oblasti teorie algoritmů
Vyučovací metody
Přednášky
Individuální konzultace
Projekt
Anotace
V kursu se stručně zopakuje základ teorie vyčíslitelnosti a složitosti, který studenti měli získat v magisterském studiu. Klade se ovšem důraz na exaktní přístup a hlubší pochopení. Dále je kurs věnován pokročilým partiím, jako je např. rozhodování logických teorií, aproximační algoritmy, pravděpodobnostní algoritmy, paralelní výpočty apod.
Povinná literatura:
M.Sipser: Introduction to the Theory of Computation (2nd ed.), Thomson 2006
Doporučená literatura:
D. Kozen: Automata and Computability, Springer 1997
D. Kozen: Theory of Computation; Springer 2006
I. Wegener: Complexity Theory; Springer 2005
Handbook of theoretical computer science (ed. Leeuwen J.); Vol. A : Algorithms and complexity; North-Holland 1990
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Student sepíše stručný, ale výstižný a srozumitelný, článek o vybraném pokročilém tématu, které v rámci kurzu odprezentuje.
Ústní zkouška.
E-learning
Konzultace prostřednictvím MS Teams.
Další požadavky na studenta
Žádné další požadavky na studenta nejsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Intuitivní pojem algoritmu a efektivní vyčíslitelné funkce.
Různé matematické formalizace těchto pojmů (především Turingovy stroje a částečně rekurzivní funkce).
Idea univerzálního algoritmu. Hlavní myšlenky důkazu ekvivalence uvedených matematických formalizací, Churchova teze.
Problém zastavení (Halting problem), Postův korespondenční problém a další algoritmicky nerozhodnutelné problémy.
Univerzální funkce, Kleeneho věta o normální formě. Rekurzivní a rekurzivně spočetné množiny, Postova věta.
Věta o rekurzi, Riceova věta. Rekurzivní převeditelnost. Kreativní množiny.
Rozhodnutelnost logických teorií.
Časová a prostorová složitost algoritmů a problémů. P-NP problém.
NP-úplnost a PSPACE-úplnost.
EXPTIME, EXPSPACE, dokazatelně nezvládnutelné problémy.
Aproximační algoritmy, pravděpodobnostní algoritmy.
Paralelní a distribuované algoritmy.
Další témata (např. alternace, kryptografie, ...)
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.