Jntu college of engineering (autonomous):: kakinada
Скачать 126.85 Kb.
|
JNTU COLLEGE OF ENGINEERING (AUTONOMOUS):: KAKINADAM.Tech. ( Computer Science & Engineering ) MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE UNIT-I: Mathematical Logic: Statements and Notations, Connectives, Well Formed Formulas, Truth Tables, Tautology, Equivalence, Implication, Normal Forms, Predicative logic, Rules of Inference, Consistency, Proof by Contradiction, Automatic Theorem Proving. UNIT-II: Elementary Combinatorics: Basis of counting, Combinations & Permutations, with repetitions, Constrained repetitions, Binomial Coefficients, Binomial Multinomial theorems, the principles of Inclusion – Exclusion, Pigeon hole principles and its application. UNIT-III: Recurrence Relations: Generating Functions, Function of Sequences, Calculating Coefficient of generating function, Recurrence relations, Solving recurrence relation by substitution and Generating functions. Characteristic roots , Solution of homogeneous Recurrence Relation. UNIT-IV: Graph Theory: Representation of Graph, DFS, BFS, Spanning Trees, Planar Graphs, Graph Theory Applications, Basic Concepts of Isomorphism, Sub Graphs, Multi Graphs, Euler Graphs, Hamiltonian Graphs, Chromatic Numbers, partial ordering relations, Hasse diagrams, Lattice and its Properties UNIT V: Finite Automata: deterministic finite automaton and non-deterministic finite automaton, transition diagrams and Language recognizers, NFA with transitions, equivalence between NFA with and without transitions, NFA to DFA conversion, minimization of Finite Automata, equivalence between two Finite Automata, Moore and Melay machines. UNIT VI: Regular Languages: Regular sets, regular expressions, identity rules, inter-conversion of Finite Automata and Regular expressions. Pumping lemma of regular sets, closure properties of regular sets Regular grammars-right linear and left linear grammars, inter conversion of regular grammar and FA (proofs not required). UNIT VII: Context Free Grammars and Push Down Automata: Context free grammar, Derivations of strings, sentential forms, Ambiguity, Minimization of CFG, CNF and GNF, Enumeration of properties of CFL, Push down automata, acceptance of CFL, Acceptance by final state and acceptance by empty stack and its equivalence. Equivalence of CFL and PDA, interconversion. (Proofs not required). UNIT VIII: Turing Machines: Turing Machine, definition, model, design of TM, Computable functions, recursively enumerable languages. Church’s hypothesis, counter machine, types of Turing machines, Desidable and undecidable problems. (proofs not required). TEXT BOOKS: 1. Discrete Mathematical Structures with applications to computer science Trembly J.P. & Manohar .P, TMH 2. Introduction to Automata Theory, Languages and Computation, Hopcroft H.E. and Ullman J. D. Pearson Education REFERENCE BOOKS: 1. Discrete Mathematics for Computer Scientists & Mathematicians Prentice Hall, 1986 J.L. Mott, A. Kandel, T.P. Baker. 2. Discrete Mathematical Structures, Bernand Kolman, Roberty C. Busby, Sharn Cutter Ross, Pearson Education/PHI. 3. Mathematical Foundations of computer science Dr D.S.Chandrasekharaiaha Prism books Pvt Ltd. 4. Introduction to languages and the Theory of Computation ,John C Martin, TMH 5. Elements of Theory of Computation, Lewis H.P. & Papadimition C.H. Pearson /PHI. 6. Theory of Computer Science – Automata languages and computation -Mishra and Chandrashekaran, 3nd edition, PHI 7. Introduction to Theory of Computation –Sipser 2nd edition Thomson 8. Introduction to Computer Theory, Daniel I.A. Cohen, John Wiley. |
