THEORY OF COMPUTATION Anna University Coimbatore Syllabus

THEORY OF COMPUTATION


UNIT I Church-Turing thesis: Turing machines – Variants of Turing Machines – Hilbert’s problems. Decidability: Decidable languages – Halting problem.

UNIT II 9

Reducibility: Undecidable problems from Language theory – A simple Undecidable problem – Mapping Reducibility. Advanced topics in Computability Theory: The Recursion Theorem – Decidability of logical theories – Turing Reducibility.

UNIT III

Time Complexity: Measuring Complexity – The Class P – The class NP – NPcompleteness – Additional NP-complete Problems.

UNIT IV 9
Space Complexity: Savitch’s Theorem – The Class PSPACE – PSPACE-completeness – The classes L and NL – NL-completeness – NL equals coNL. Intractability: Hierarchy Theorems – Relativization – CircuitComplexity.

UNIT V

Advanced topics in complexity theory: Approximation Algorithms – Probabilistic Algorithms – Alternation – Interactive Proof Systems – Parallel Computation – Cryptography


TEXT BOOKS:
1. Michael Sipser, Introduction to the Theory of Computation, Thomson Brook/cole, 1997.(2006)
2. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, 3/E, Pearson Education, 2009.
REFERENCES
1. Peter Linz, An Introduction to formal Languages and Automata, 4/ E, Jones & Bartlett Pub, 2006.
2 Kamala Krithivasan, Rama R, Introduction to Formal Languages, Automata Theory and Computation, Pearson, 2009
3. Dr. B. N. Srinivasa Murthy, Formal Languages and Automata Theory, Sanguine Publishers, 2006.
Share on Google Plus
    Rejinpaul.com Comment
    Facebook Comment

0 comments :

Post a Comment

Post Your comments,Views and thoughts Here, Give Us Time To Respond Your Queries