Theory of Computation (CSEN 502)
Offered By:
Media Engineering and Technology Faculty
Description
The theory of computation comprises the mathematical underpinnings of computer science. It introduces three major topics: formal languages and automata theory, computability theory, and complexity theory. This course focuses on the first two, and provides an introduction to the third. Complexity theory classifies problems with respect to their intrinsic degree of hardness, or the amount of computational resources (in terms of space and time) required to solve them. Computability theory addresses a more fundamental issue: is a given problem solvable (by a computer) in the first place? The theory of formal languages and automata investigates mathematical models of computation, and classifies them with respect to their computational power. These models are used to answer questions and prove results in both computability and complexity theory. In addition to its foundational role, the theory of computation had had vast applications in various areas of computing. These include the specification of the syntax of programming languages, compiler construction, string processing, and cryptography.