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, ...)
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, ...)