Models of Computation
(lectures -- 3 hours per week)
Course objectives :
This course aims to familiarize students with the basic models of computation, their properties, and the interrelationships between models. A study of these models provides the student with an insight into the process of ‘computation’ and the various methods of establishing properties of computations. A conceptual understanding of what is meant by a ‘computation’ should surely be expected from any Computer Scientist. Also, in practice, it is hoped that knowledge of these models and their properties would allow a student to model and verify the correctness of a proposed solution to a computational problem, before proceeding to its implementation in hardware and/or software.
Course contents :
Review of basic concepts: Countable and uncountable sets; relations and closure. Regular expressions, regular languages, deterministic and non-deterministic finite automata, and their properties. Context free languages, push down automata, parsing. Turing machines and their variants; non-determinism; Universal Turing machine and undecidability. Computational complexity, the classes P and NP, polynomial reductions and NP-completeness.
Reference books :
‘Elements of the Theory of Computation’, by Lewis & Papadimitriou, Pearson Education .
‘Introduction to Automata Theory, Languages and Computation’, by Hopcroft, Motwani & Ullman, Pearson Education.
‘The Theory of Computation’, by Bernard Moret, Pearson Education.
‘Introduction to Languages and the Theory of Computation’, by John Martin, McGraw Hill.