The Theory of Computation
Shai Simonson
Lectures |
Problem Sets |
Exams |
Course Evaluation
Course Description
A theoretical treatment of what can be computed and how fast it can be
done. Applications to compilers, string searching, and control circuit
design will be discussed. The hierarchy of finite state machines,
pushdown machines, context free grammars and Turing machines will be
analyzed, along with their variations. The notions of decidability,
complexity theory and a complete discussion of NP-Complete problems
round out the course.
Text: Introduction to the Theory of Computation, Michael Sipser.
Reference: Introduction to Automata Theory, Languages and Computation
by Hopcroft, Motwani and Ullman.
Requirements: Two exams, five problem sets.
| 
