460-6004/03 – Teorie algoritmů (TA)
| Garantující katedra | Katedra informatiky | Kredity | 10 |
| Garant předmětu | prof. RNDr. Petr Jančar, CSc. | 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 | čeština |
| Rok zavedení | 2019/2020 | Rok zrušení | |
| Určeno pro fakulty | FEI, USP | 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
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
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í.