FI:I000 Induction and Recursion - Course Information

I000 Induction and Recursion

Faculty of Informatics
Autumn 1997

Extent and Intensity

3/0. 3 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).

Teacher(s)

prof. RNDr. Jiří Zlatuška, CSc. (lecturer)

Guaranteed by

Contact Person: prof. RNDr. Jiří Zlatuška, CSc.

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

Syllabus

Introduction into the mathematical constructions relevant to study of programs as mathematical objects: induction and recursion in non-trivial domains, connection between the formal language and its semantics, operational semantics of recursive programs, universal machine and the Halting Problem.
Basic notions: functions, graphs, equivalence relation, trees.
Induction and its applications: defining sets and functions using induction.
Data types, lists, and implementation of general data types using lists.
Languages over data types and their semantics: terms, conditionals, functions; semantics of call-by-value and call-by-name.
Programming using induction, proving recursive programs correct.
Universal machine for the language of recursive programs, undecidability of the Halting Problem.

Language of instruction

Czech