Create a free account to unlock full content!
By registering, you agree to our Privacy Statement and Terms and Conditions.
Program Overview
Theory of Computation
The course explores what can and cannot be solved on a computer, how quickly, with how much memory, and on which type of computational model. The class is divided into two major parts: computability theory and complexity theory. Computability theory deals primarily with the question of whether a problem is solvable at all on a computer. Complexity theory considers how efficiently the problem can be solved. Two major aspects are considered: time complexity and space complexity, which respectively address a problem of how many steps does it take to perform a computation, and how much memory is required to perform that computation.
Objectives
The class introduces the fundamental mathematical properties of computer hardware, software, and certain applications thereof.
Teaching Mode
The course is taught in presence.
Learning Methods
The theory subjects have strong connections with engineering practice. In addition to theory lectures, the course will offer practical exercises and labs which will involve experimentation with various tools.
Examination Information
There will be a written final exam covering both theory and practice of computability and complexity theories.
Bibliography
- Compulsory: Sipser, Michael. Introduction to the theory of computation. 3rd, international edition. Boston Mass.: Thomson Course Technology, 2013.
Education
- Bachelor of Science in Informatics, Lecture, Elective, 3rd year
Course Details
- Semester: Spring
- Academic Year:
- ECTS: 6.0
- Language: English
Additional Information
The course is part of the Bachelor of Science in Informatics program.