FI:U320 Výpočetní modely I - Course Information

U320 Výpočetní modely I

Extent and Intensity

2/1. 0 credit(s). Type of Completion: z (credit).

Teacher(s)

doc. Ing. Lenka Carr Motyčková, CSc. (lecturer)

Guaranteed by

Contact Person: doc. Ing. Lenka Carr Motyčková, 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

• Upper Secondary School Teacher Training in Informatics (programme FI, M-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)

Syllabus

• The course gives a survey of basic computational models: sequential, parallel and distributed. Complexity issues are considered including relations between models.
• Turing machine, nondeterministic, multitape.
• Recognizable languages.
• Unrecognizable languages.
• Decidable languages and problems.
• Halting problem and reductions of other undecidable problems.
• Partial recursive functions.
• Turing-Church thesis.
• Complexity, speed up theorem.
• The class P (RAM model)
• The class NP, P - NP problem.
• Completeness, Cook's theorem.
• Reductions of NP-complete problems.

Language of instruction

Czech

• Enrolment Statistics (recent)
  
• Permalink: https://is.muni.cz/course/fi/autumn1997/U320