I000 Induction and Recursion

Faculty of Informatics
Autumn 1999
Extent and Intensity
2/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Jiří Zlatuška, CSc. (lecturer)
Mgr. Tomáš Dudaško (assistant)
doc. RNDr. Vojtěch Řehák, Ph.D. (assistant)
Mgr. Oldřich Stražovský (assistant)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
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.
Literature
  • WAND, Mitchell. Induction, recursion, and programming. New York: North Holland, 1980, 202 s. ISBN 0444003223. info
Language of instruction
Czech
Further Comments
The course is taught annually.
The course is taught: every week.
The course is also listed under the following terms Autumn 1995, Autumn 1996, Autumn 1997, Autumn 1998, Autumn 2000, Autumn 2001.
  • Enrolment Statistics (Autumn 1999, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn1999/I000