My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
Syllabus of Andhra University MCA - MCA 2.1.1 Theory of Computation
Posted Date: 16 Feb 2008 Resource Type: Articles/Knowledge Sharing Category: General
|
Posted By: rajasekhar Member Level: Gold
Rating:  Points: 5
|
|
|
Syllabus of Andhra University MCA - MCA 2.1.1 Theory of Computation
With effect from 2004-05 admitted batch
Instruction: 3 Periods/week
Sessional Marks: 50
Univ-Exam-Marks:100
Time: 3 Hours
1. Introduction To Finite Automata : Alphabets and languages- Finite Representation of Languages. Deterministic Finite Automata – Non- deterministic Finite Automata – Equivalenceof Deterministic and Non-Finite Automata – Properties of the Languages Accepted by Finite Automata – Finite Automata and Regular Expressions – Proofs those Languages Are and Are Not Regular.
2. Context free languages: Context –Free Grammar – Regular Languages and Context-FreeGrammar – Pushdown Automata – Pushdown Automata and Context-Free Grammar – Properties of Context-Free Languages – Closure Properties – Periodicity Properties – Determinism and Parsing – Deterministic Pushdown Automata and Context – Free Languages – Top- down Parsing– Bottom – Up parsing.
3. Turing machines: The Definition of Turing Machine – Computing with Turing Machines –Combining Turing Machines – some Examples of More Powerful Turing Machines.
4. Church’ Thesis : Church’s Thesis – The Primitive Recursive functions – Godelization – Them-Recursive Functions – Turing – Computability of the m-Recursive functions – Universal Turing Machines.
5. Uncomputability: The Halting Problem – Turing-Enumerability, Turing –Acceptability, and Turing - Decidability – Unsolved problems about Turing machines and m-Recursive Functions - Post’s correspondence problem.
6. Computational complexity: Time-bounded Turing Machines – Rate of Growth offunctions – Time-Bounded simulations – The Classes P and NP – NP-Completeness –Some NP-complete Problems – Integer Programming – The Traveling SalesmanProblem.
7. The Prepositional Calculus : Introduction – Syntax of the Prepositional Calculus –Truth-Assignments – Validity and Satisfiability – Equivalence and Normal Forms –resolution in Prepositional Calculus.
8. The predicate calculus: Syntax of the Predicate Calculate Calculus – Structures and Satisfiability – Equivalence – Unsolvability and NP-Completeness- Resolution in the Predicate Calculus.
Text Book:
Elemets Of The Theory Of Computation, Harry R Lewis, Cristos h. Papadimitriou, Pearson Education / Prentice-Hall of India Private Limited.
Reference:
Introduction to Automata Theory, Languages, and Computation, Hopcroft. J.E and J.D.Ullman. Addison-Wesley, Reading, Mass. 1979.
|
Responses
|
No responses found. Be the first to respond and make money from revenue sharing program.
|
|
Watch TV Channels
|