Program Overview

Theory of Computation

The class introduces the fundamental mathematical properties of computer hardware, software, and certain applications thereof. It 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. The subjects have strong connections with engineering practice. Practical exercises will involve experimentation with various tools.

People

• Sharygina N.: Course director
• Asadi S.: Assistant
• Marescotti M.: Assistant

Description and Requirements

Prerequisites

• Algorithms & Data Structures
• Automata & Formal Languages

Recommended Courses

• Algorithms & Data Structures 2

Education

The Theory of Computation is an elective course within the Bachelor of Science in Informatics, offered as a lecture in the 3rd year.

Additional Information

• Semester: Spring
• Academic year: Not specified
• ECTS: 6.0
• Language: English