Anna university Coimbatore Syllabus
080230026 Theory of Computation CSE 6th Semester Anna University Coimbatore Syllabus Regulation 2008
Department of Computer science and Engineering
Meant for Anna University Coimbatore,trichy,trinelveli
Syllabus
(Regulation 2008/2010)
___________________________________________________________________________________
Details:
University:Anna University
Year: third Year
Department: B.E Computer Science and Engineering
Semester: (VI)
Content: 080230026 Theory of Computation CSE 6th Semester Anna University Coimbatore Syllabus Regulation 2008
Subject code: 080230026
Subject Name: Theory of Computation
Regulation: 2008 or 2010
Post Type: Syllabus
ATTACHMENT Download
For All Subject Syllabus-Download Link
For All Subject Question Papers -Download Link
Related Searches:
Anna University Coimbatore CSE syllabus
Anna University Coimbatore CSE 6th semester syllabus
Cse syllabus for Anna university coimbatore
080230026 Theory of Computation Syllabus
Syllabus for 080230026
Syllabus for Theory of Computation
Affiliated institutions CSE 6th sem AU coimbatore syllabus
BE cse syllabus for anna university coimbatore
AU coimbatore cse syllabus
AU coimbatore cse fifth semester syllabus
CSE fifth semester syllabus for Anna university coimbatore
UNIT I
Church-Turing thesis: Turing machines – Variants of Turing Machines – Hilbert’s problems. Decidability: Decidable languages – Halting problem.
UNIT II
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 – NP-
completeness – Additional NP-complete Problems.
UNIT IV
Space Complexity: Savitch’s Theorem – The Class PSPACE – PSPACE-completeness
– The classes L and NL – NL-completeness – NL equals coNL. Intractability:
Hierarchy
Theorems – Relativization – Circuit Complexity.
UNIT V
Advanced topics in complexity theory: Approximation
Algorithms – Probabilistic Algorithms
– Alternation – Interactive Proof Systems – Parallel Computation – Cryptography
TUTORIAL 15
TOTAL : 60
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.
Like our Facebook Page to get regular Updates
ATTACHMENT Download
For All Subject Syllabus-Download Link
For All Subject Question Papers -Download Link
Related Searches:
Anna University Coimbatore CSE syllabus
Anna University Coimbatore CSE 6th semester syllabus
Cse syllabus for Anna university coimbatore
080230026 Theory of Computation Syllabus
Syllabus for 080230026
Syllabus for Theory of Computation
Affiliated institutions CSE 6th sem AU coimbatore syllabus
BE cse syllabus for anna university coimbatore
AU coimbatore cse syllabus
AU coimbatore cse fifth semester syllabus
CSE fifth semester syllabus for Anna university coimbatore
0 comments:
Post a Comment