Sylabus
Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Rekursivní a rekursivně spočetné množiny a predikáty. Časová a prostorová složitost algoritmů a problémů, NP-úplnost.
Turingův stroj. Rekursivní funkce. Primitivně rekursivní funkce. Kleeneho věta o normální formě. Semirekursivní predikáty. Kleeneho enumerační věta.
Anotace
Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Rekursivní a rekursivně spočetné množiny a predikáty. Časová a prostorová složitost algoritmů a problémů, NP-úplnost.