IT422 - Models of Computation
(MOC)

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.