Theory of Computation ((4 Credits))

Catalog description

Theory of Computation is a capstone course for computer science. It is concerned with theoretical aspects such as regular languages, finite automata, context-free languages, pushdown automata, the Church-Turing thesis, Turing machines, decidability, the halting problem, time complexity, and P and NP classes. Students will improve their ability to learn mathematics independently and improve their ability to create proofs. Prerequisite (must complete before registering): Discrete Mathematics Assumptions about surrounding courses: It is essential to know general methods of proof and have some prior experience with proving theorems. To achieve this, the contents of Discrete Math taken at the advanced level are essential. A course in proofs is recommended. Notes: Theory of Computation is usually a requirement for graduate school in Computer Science.