King Abdullah II School of Information Technology - The University of Jordan - Theory of Computation and Complexity

  King Abdullah II School of Information Technology - Department of Computer Science

( Theory of Computation and Complexity)
Course Description :

Finite Automata and Regular Languages, Properties of Finite Automata, Regular Expressions, The Pumping Lemma and Closure Properties; Universal Models of Computation, Encoding Instances, Choosing a Model of Computation, Model Independence, Turing Machines as Enumerators and Acceptors; Computability Theory, Primitive Recursive Functions, Partial Recursive Functions, Arithmetization: Encoding a Turing Machine, Programming Systems, Recursive and R.E. Sets, Rice's Theorem and the Recursion Theorem, Degrees of Unsolvability; Complexity Theory, Reductions, Classes of Complexity, Complete Problems; Some Important NP-Complete Problems, The Complexity of Approximation, Models of Parallel Computation, Communication and Complexity, Interactive Proofs and Probabilistic Proof Checking

Pre Request :
Credit Hour :
Department :Computer Science
Program :MSc. of Computer Science
Course Level :Master
Course Outline :