The Course Provides an Introduction to Computatbility and Complexity, Including# Deterministic Automaton and Regular Languages, Nondeterministic Automaton, Context-free Languages and Push-down Automaton, Algorithms On Automata, Turing Machine, and Decidability. In Complexity Theory The Course Covers The Classes P, Np, Np-hard, Np-complete, and Pspace. Learning Outcome# At The End of The Course The Students 1. Will Know Fundamental Concepts in Computability, Including Automata Theory, Turing Machines, Regular Languages and Decidability. 2. Will Know Fundamental Concepts in Complexity Theory, Including The Major Complexity Classes of P, Np, Np-c and Pspace. 3. Will Know How to Prove Membership of a Problem in a Complexity Class, and How to Prove That a Problem Is Decidable Or Undecidable. 4. Will Be Familiar With The Argument of Why The Number of Decidable Problems Is Countable, Whereas The Number of Undecidable Problems Is Uncountable.

Faculty: Industrial Engineering and Management
|Undergraduate Studies |Graduate Studies

Pre-required courses

94224 - Data Structures and Algorithms or 234247 - Algorithms 1

Course with no extra credit

236343 - Theory of Computation 237343 - Theory of Computation

Course with no extra credit (contained)

94250 - Introduction to Computability

Semestrial Information