Enumerable functions, possible definitions, properties. Recursive and recursively enumerable sets and semirecursive predicates. Time and space complexity.
Last update: T_KNM (19.05.2008)
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.
Aim of the course -
Last update: T_KNM (19.05.2008)
The course gives students a knowledge of enumerable and recursive functions.
Last update: T_KNM (19.05.2008)
Studenti se seznámí s algoritmicky vyčíslitelnými a rekursivními funkcemi.
Literature - Czech
Last update: T_KNM (19.05.2008)
Davis M.: Computability and unsolvability. Mc Graw Hill, N.Y., 1958
Rogers H. jr.: Theory of recursive functions and effective computability. Mc Graw Hill, N.Y., 1967
Teaching methods -
Last update: T_KNM (19.05.2008)
Lectures in a lecture hall.
Last update: T_KNM (19.05.2008)
Přednášky v posluchárně.
Requirements to the exam -
Last update: T_KNM (19.05.2008)
Examination according to the syllabus.
Last update: T_KNM (19.05.2008)
Zkouška dle sylabu.
Syllabus -
Last update: T_KNM (19.05.2008)
Enumerable functions, their properties, equivalence of their various mathematical definitions. Recursive and recursively enumerable sets and predicates.
Turing Machines' ability to compute all recursive functions. Recursive functions, primitive recursive functions, predicates and sets. Emulation of Turing Machine by primitive recursive functions and predicates. Kleene's theorems. Semirecursive predicates. Predicates that are not recursive. Predicates that are not semirecursive. Creative and simple functions.
Last update: T_KNM (19.05.2008)
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.
