SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
Computability - NLTM021
Title: Vyčíslitelnost
Guaranteed by: Network and Labs Management Center (32-SISAL)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Additional information:
Guarantor: RNDr. Vojtěch Jákl
Classification: Informatics > Theoretical Computer Science
Is interchangeable with: NLTM020
Annotation -
Enumerable functions, possible definitions, properties. Recursive and recursively enumerable sets and semirecursive predicates. Time and space complexity.
Last update: T_KNM (19.05.2008)
Aim of the course -

The course gives students a knowledge of enumerable and recursive functions.

Last update: T_KNM (19.05.2008)
Literature - Czech

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

Last update: T_KNM (19.05.2008)
Teaching methods -

Lectures in a lecture hall.

Last update: T_KNM (19.05.2008)
Requirements to the exam -

Examination according to the syllabus.

Last update: T_KNM (19.05.2008)
Syllabus -

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)
Entry requirements -

There are no special entry requirements.

Last update: T_KNM (19.05.2008)
Registration requirements - Czech

tento předmět se již nevyučuje

Last update: Jákl Vojtěch, RNDr. (24.02.2016)
Charles University | Information system of Charles University |