Jntu college of engineering (autonomous):: kakinada




Скачать 126.85 Kb.
НазваниеJntu college of engineering (autonomous):: kakinada
страница2/9
Дата09.10.2012
Размер126.85 Kb.
ТипДокументы
1   2   3   4   5   6   7   8   9

JNTU COLLEGE OF ENGINEERING (AUTONOMOUS):: KAKINADA


M.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.

1   2   3   4   5   6   7   8   9

Похожие:

Jntu college of engineering (autonomous):: kakinada iconLakireddy bali reddy college of engineering (autonomous), mylavaram 521230

Jntu college of engineering (autonomous):: kakinada iconLakireddy bali reddy college of engineering (autonomous), mylavaram 521230

Jntu college of engineering (autonomous):: kakinada iconLakireddy bali reddy college of engineering (autonomous), mylavaram 521230

Jntu college of engineering (autonomous):: kakinada iconLakireddy bali reddy college of engineering (autonomous), mylavaram 521230

Jntu college of engineering (autonomous):: kakinada iconLakireddy bali reddy college of engineering (autonomous), mylavaram 521230

Jntu college of engineering (autonomous):: kakinada iconThiagarajar college (autonomous) madurai – 9

Jntu college of engineering (autonomous):: kakinada iconThiagarajar college (autonomous), madurai – 9

Jntu college of engineering (autonomous):: kakinada iconST. joseph’s college (autonomous) bangalore

Jntu college of engineering (autonomous):: kakinada iconJawaharlal nehru tenhnological university kakinada: kakinada

Jntu college of engineering (autonomous):: kakinada iconJamal mohamed college (autonomous), tiruchirappalli 20

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница