|
EOE-038 / EOE-048 :
DISCRETE MATHEMATICS
|
|
LTP
|
|
31 0
|
|
UNIT-I
|
|
Set Theory
|
|
: Definition of Sets, Venn Diagrams, complements,
cartesian products, power
|
|
sets, counting principle, cardinality and countability
(Countable and Uncountable sets),
|
|
proofs of some general identitites on sets, pigeonhole
principle.
|
|
Relation:
|
|
Definition, types of relation, composition of
relations, domain and range of a
|
|
relation, pictorial representation of relation,
properties of relation, partial ordering relation.
|
|
Function:
|
|
Definition and types of function, composition of
functions, recursively defined
|
|
UNIT-II
|
|
Propositional logic:
|
|
Proposition logic, basic logic, logical connectives,
truth tables,
|
|
tautologies, contradiction , normal forms(conjunctive
and disjunctive), modus ponens and
|
|
modus tollens, validity, predicate logic, universal
and existential quantification.
|
|
Notion of proof:
|
|
proof by implication, converse, inverse,
contrapositive, negation, and
|
|
contradiction, direct proof, proof by using truth
table, proof by counter example.
|
|
7
|
|
UNIT-III
|
|
Combinatories:
|
|
Mathematical induction, recursive mathematical
definitions, basics of
|
|
counting, permutations, combinations,
inclusion-exclusion, recurrence relations (n
|
|
order
|
|
th
|
|
recurrence relation with constant coefficients,
Homogeneous recurrence relations,
|
|
Inhomogeneous recurrence relation), generating
function (closed form expression,
properties
|
|
of G.F.,
solution of recurrence relation using G.F, solution of combinatorial problem
using
|
|
G.F.)
|
|
7
|
|
Unit-IV
|
|
Algebraic Structure:
|
|
Binary composition and its properties definition of algebraic structure;
|
|
Groyas Semi group, Monoid Groups, Abelian Group,
properties of groups, Permutation
|
|
Groups, Sub Group, Cyclic Group, Rings and Fields
(definition and standard results).
|
|
6
|
|
UNIT-V
|
|
Graphs:
|
|
Graph terminology, types of graph connected graphs,
components of graph, Euler graph,
|
|
Hamiltonian path and circuits, Graph coloring,
Chromatic number.
|
|
Tree:
|
|
Definition, types of tree(rooted, binary), properties
of trees, binary search tree, tree
|
|
traversing (preorder, inorder, postorder).
|
|
Finite Automata:
|
|
Basic concepts of Automation theory, Deterministic
finite
|
|
Automation(DFA), transition function, transition
table, Non Deterministic Finite Automata
|
|
(NDFA), Mealy and Moore Machine, Minimization of
finite Automation.
|
|
10
|
|
Text/Reference Books:
|
|
1. Kenneth H.
Rosen, “Discrete Mathematics and its Applications”, Mc.Graw Hill, 2002.
|
|
2. J.P.Tremblay
& R. Manohar, “Discrete Mathematical Structure with Applications to
|
|
Computer Science” Mc.Graw Hill, 1975.
|
|
3. V.
Krishnamurthy, “Combinatories:Theory and Applications”, East-West Press.
|
|
4. Seymour
Lipschutz, M.Lipson, “Discrete
Mathemataics” Tata Mc Graw Hill, 2005.
|
No comments:
Post a Comment