CPSCI-380 Theory of Computation

This course provides a thorough examination of the fundamental concepts underpinning all of computation. The course introduces the ideas of formal languages and computational models, and uses them to discuss computability and the existence of unsolvable problems. We develop increasingly complex models of computation, including finite automata, regular expressions, context-free grammars, and Turing machines. The course concludes with a high-level discussion of the computational complexity classes P and NP.

Maximum Enrollment

Standard Course (40)

Credits

1

Prerequisite

123 or 230

Offered

Fall