SubjectsSubjects(version: 920)
Course, academic year 2022/2023
   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
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Additional information:
Guarantor: RNDr. Vojtěch Jákl
Classification: Informatics > Theoretical Computer Science
Is interchangeable with: NLTM020
Annotation -
Last update: T_KNM (19.05.2008)
Enumerable functions, possible definitions, properties. Recursive and recursively enumerable sets and semirecursive predicates. Time and space complexity.
Aim of the course -
Last update: T_KNM (19.05.2008)

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

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.

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

Examination according to the syllabus.

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.

Entry requirements -
Last update: T_KNM (19.05.2008)

There are no special entry requirements.

Registration requirements - Czech
Last update: RNDr. Vojtěch Jákl (24.02.2016)

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

Charles University | Information system of Charles University |