Discrete Mathematics
- Publisher's listprice GBP 14.99
-
6 767 Ft (6 445 Ft + 5% VAT)
The price is estimated because at the time of ordering we do not know what conversion rates will apply to HUF / product currency when the book arrives. In case HUF is weaker, the price increases slightly, in case HUF is stronger, the price goes lower slightly.
- Discount 10% (cc. 677 Ft off)
- Discounted price 6 091 Ft (5 801 Ft + 5% VAT)
Subcribe now and take benefit of a favourable price.
Subscribe
6 767 Ft
Availability
Only to order.
Why don't you give exact delivery time?
Delivery time is estimated on our previous experiences. We give estimations only, because we order from outside Hungary, and the delivery time mainly depends on how quickly the publisher supplies the book. Faster or slower deliveries both happen, but we do our best to supply as quickly as possible.
Product details:
- Publisher OUP India
- Date of Publication 10 February 2011
- ISBN 9780198065432
- Binding Paperback
- No. of pages552 pages
- Size 241x184x23 mm
- Weight 812 g
- Language English
- Illustrations 260 Line drawings 0
Categories
Short description:
Discrete Mathematics is designed to serve as a textbook for undergraduate engineering students of computer science and postgraduate students of computer applications. The book would also prove useful to post graduate students of mathematics. It seeks to provide a thorough understanding of the subject and present its practical applications tol computer science.
MoreLong description:
Discrete Mathematics is designed to serve as a textbook for undergraduate engineering students of computer science and postgraduate students of computer applications. The book would also prove useful to post graduate students of mathematics. The book seeks to provide a thorough understanding of the subject and present its practical applications to computer science.
Beginning with an overview of basic concepts like Sets, Relation and Functions, and Matrices, the book delves into core concepts of discrete mathematics like Combinatorics, Logic and Truth Tables, Groups, Order Relation and Lattices, Boolean Algebra, Trees, and Graphs. Special emphasis is also laid on certain advanced topics like Complexity and Formal Language and Automata. Algorithms and programmes have been used wherever required to illustrate the applications.
Written in a simple, student-friendly style, the book provides numerous solved examples and chapter end exercises to help students apply the mathematical tools to computer-related concepts.
Table of Contents:
CHAPTER 1: SET RELATION FUNCTION
INTRODUCTION
SETS
Representation of a Set
Sets of Special Status
Universal Set and Empty Set
Subsets
Power set
Cardinality of a Set
ORDERED PAIRS
Cartesian Product of Sets
Properties of Cartesian Product
VENN DIAGRAMS
OPERATIONS ON SETS
Union of Sets
Intersections of Set
Complements
Symmetric Difference
COUNTABLE AND UNCOUNTABLE SETS
ALGEBRA OF SETS
MULTISET
Operations on Multisets
FUZZY SET
Operations on Fuzzy Set
GROWTH OF FUNCTION
COMPUTER REPRESENTATION OF SETS
INTRODUCTION
BINARY RELATION
CLASSIFICATION OF RELATIONS
Reflexive Relation
Symmetric Relation
Antisymmetric Relation
Transitive Relation
Equivalence Relation
Associative Relation
COMPOSITION OF RELATIONS
INVERSE OF A RELATION
REPRESENTATION OF RELATIONS ON A SET
CLOSURE OPERATION ON RELATIONS
Reflexive Closure
Symmetric Closure
MATRIX REPRESENTATION OF RELATION
DIGRAPHS
Transitive Closure
Warshall's Algorithm
PARTIAL ORDERING RELATION
n-ARY RELATIONS AND THEIR APPLICATIONS
RELATIONAL MODEL FOR DATABASES
INTRODUCTION
ADDITION AND MULTIPLICATION OF FUNCTIONS
CLASSIFICATION OF FUNCTIONS
One-to-one (Injective) Function
Onto (Surjective) Functions
One-to-one, Onto (Bijective) Function
Identity Function
Constant Function
COMPOSITION OF FUNCTION
Associativity of Composition of Functions
INVERSE FUNCTION
Invertible Function
Image of a Subset
HASH FUNCTION
RECURSIVELY DEFINED FUNCTIONS
SOME SPECIAL FUNCTIONS
Floor and Ceiling Functions
Integer and Absolute Value Functions
Remainder Function
FUNCTIONS OF COMPUTER SCIENCE
Partial and Total Functions
Primitive Recursive Function
Ackermann Function
THE INCLUSION-EXCLUSION PRINCIPLE
Applications of Inclusion - Exclusion Principle
SEQUENCE AND SUMMATION
Sequence
Summation
Summary
Exercise 1
CHAPTER 2 COMBINATORICS
INTRODUCTION
BASIC PRINCIPLES OF COUNTING
Multiplication Principle (The Principles of Sequential Counting)
Addition Rule ( The Principle of Disjunctive Counting)
FACTORIAL NOTATION
BINOMIAL THEOREM
Pascal's Triangle
Multinomial Theorem
PERMUTATIONS (Arrangements of Objects)
Permutations with Repetitions
Circular Permutations
COMBINATIONS (Selection of Objects)
Combinations of n Different Objects
Combinations with Repetitions
DISCRETE PROBABILITY
Terminology (Basic Concepts)
FINITE PROBABILITY SPACES
PROBABILITY OF AN EVENT
Axioms of Probability
Odds in favour and Odds against an Event
Addition Principle
CONDITIONAL PROBABILITY
Multiplication Rule
INDEPENDENT REPEATED TRIALS, BINOMIAL DISTRIBUTION
Repeated Trials with Two Outcomes, Bernoulli Trials
RANDOM VARIABLES
Probability Distribution of a Random Variable
Expectation of a Random Variable
Variance and Standard Deviation of a Random Variable
Binomial Distribution
RECURSION
Recursively Defined Sequences
Recursive Definitions
Recursively Defined Sets
Recursively Defined Functions
RECURENCE RELATION
Order and Degree of Recurrence Relation
Linear Homogenous and Non-homogeneous Recurrence Relations
Solution of Linear Recurrence Relation with Constant Coefficients
Homogenous Solution
Particular Solution
GENERATING FUNCTIONS
COUNTING (COMBINATORIAL) METHOD
THE PIGEONHOLE PRINCPLE
Generalized Pigeonhole Principle
Summary
Exercise 2
CHAPTER 3 MATHEMATICAL LOGIC
INTRODUCTION
STATEMENT (PROPOSITIONS)
LAWS OF FORMAL LOGIC
Law of Contradiction
Law of Intermediate Exclusion
BASIC SET OF LOGICAL OPERATORS /OPERATIONS
Conjunction (AND, )
Disjunction (OR, )
Negation (NOT, ~ )
PROPOSITIONS AND TRUTH TABLES
Connectives
Compound Propositions
Conditional Statement
Converse, Contrapositive, and Inverse
Biconditional Statement
ALGEBRA OF PROPOSITIONS
PROPOSITIONAL FUNCTIONS
TAUTOLOGIES AND CONTRADICTIONS
LOGICAL EQUIVALENCE
De Morgan Laws
LOGICAL IMPLICATION
NORMAL FORMS
Disjunctive Normal Form (dnf)
Conjunctive Normal Form (cnf)
ARGUMENTS
RULES OF INFERENCE
Law of Detachment (or Modus Pones)
Law of Contraposition (Modus tollens)
Disjunctive Syllogism
Hypothetical Syllogism
WELL FORMED FORMULAE
PREDICATE CALCULUS
QUANTIFIER
Universal Quantifier
Existential Quantifier
INTRODUCTION TO PROOFS
Brief Status of Terminology
Methods of Proof
Direct Proof
Consistency
Method of Proof by Contraposition
Proof by Contradiction (reduction ad absurdum)
Proof by Mathematical Induction
Proof by Cases
Summary
Exercise 3
CHAPTER 4 ALGEBRAIC STRUCTURE
INTRODUCTION
BINARY OPERATIONS
Properties of Binary Operations
GROUPS
Abelian Group
Properties of Groups
Products and Quotients of Groups
SEMIGROUPS
Isomorphism and Homomorphism
Products and Quotients of Semigroups
SUBGROUP
CYCLIC GROUP
PERMUTATION GROUPS
Equality of Permutations
Permutation Identity
Composition of Permutations (or, Product of Permutations)
Inverse Permutation
Cyclic Permutations
Transposition
Even and Odd Permutations
SYMMETRIC GROUP
COSETS
Properties of Cosets
NORMAL SUBGROUP
LAGRANGE'S THEOREM
GROUP CODES
Coding of Binary Information
Parity and Generator Matrices
Decoding and Error Correction
ALGEBRAIC SYSTEMS WITH TWO BINARY OPERATIONS
Rings
Elementary Properties of a Ring
Special kinds of Rings
Integral Domain
Field
SUBRING
Ideal
Quotient Ring
Morphisms of Rings
Properties of Homomorphism of Ring
Summary
Exercise 4
Chapter 5 MATRIX ALGEBRA
INTRODUCTION
DEFINITION OF A MATRIX
TYPES OF MATRICES
Rectangular and Square Matrices
Row matrix or a row vector
Column matrix or a column vector
Zero or Null matrix
Diagonal elements of a matrix
Diagonal matrix
Scalar matrix
Unit Matrix or Identity Matrix
Comparable Matrices
Equal Matrices
Upper Triangular Matrix
Lower Triangular Matrix
OPERATIONS ON MATRICES
Addition of Matrices
Subtraction of Matrices
Scalar Multiple of a Matrix
Multiplication of Matrices
Properties of Matrix Multiplication
Positive Integral Powers of Matrices
Sub Matrix
Partition of Matrices
RELATED MATRICES
Transpose of a Matrix
Symmetric and Skew-Symmetric Matrix
Complex Matrices
Conjugate of a Matrix
Conjugate Transpose of a Matrix
Hermitian and Skew-Hermitian Matrices
DETERMINANT OF A MATRIX
Minor and Co-factor
Expansion of the determinant ( )
Difference between a Matrix and a Determinant
TYPICAL SQUARE MATRICES
Orthogonal Matrix
Unitary Matrix
Involutory Matrix
Idempotent Matrix
Nilpotent Matrix
ADJOINT AND INVERSE OF A MATRIX
Singular and Non-singular Matrices
Adjoint of a Square Matrix
Properties of Adjoint of a Matrix
INVERSE OF A MATRIX
Properties of Inverse of a Matrix
RANK OF A MATRIX
Elementary transformations (operations) of a matrix
BOOLEAN MATRIX OR A ZERO-ONE MATRIX
Operations on Zero-one Matrices
Boolean product of matrices
Echelon Matrix (Row Reduced Echelon Form)
Normal form of a Matrix
Procedure of reduction of a matrix A to its normal form
SOLUTION OF LINEAR AL GEBRAIC EQUATIONS
Linear Homogenous Equations (Ax = 0)
Linear Non-homogenous Equations (Ax = b)
Consistent and Inconsistent Equations
EIGEN VALUES AND EIGEN VECTORS
Determination of Eigen values and Eigen vectors
Linear Transformations
Properties of Eigen values and Eigen vectors
CAYLEY - HAMILTON THOREM
Inverse of the Matrix
Summary
Exercise 5
Chapter 6 ORDER RELATION AND LATTICE
INTRODUCTION
PARTIALLY ORDERED SET
Comparability of Elements
Linearly ordered set
HASSE DIAGRAM
Topological Sorting
Chain
Antichain
ISOMORPHISM
Isomorphic Ordered Sets
LEXICOGRAPHIC ORDERING
EXTREMAL ELEMENTS OF POSETS
Maximal Element
Minimal Element
Greatest and Least Elements
Upper and Lower Bounds
Least Upper Bound (Supremum)
Greatest Lower Bound (Infimum)
WELL-ORDERED SET
CONSISTENT ENUMERATIONS
LATTICES
Principle of Duality
Isotonocity Property
SUB LATTICES
DIRECT PRODUCT OF LATTICES
SOME SPECIAL CLASS OF LATTICES
Complete Lattice
Bounded Lattice
Properties of Bounded Lattice
Distributive Lattice
Modular Lattice
Complemented Lattices
Isomorphic Lattices
Join-irreducible
Meet-irreducible
LATTICE HOMOMORPHISM
Summary
Exercise 6
CHAPTER-7 BOOLEAN ALGEBRA
INTRODUCTION
LAWS ON BOOLEAN ALGEBRA
TRUTH TABLES ON BOOLEAN OPERATIONS
UNIQUE FEATURES OF BOOLEAN ALGEBRA
MINTERM AND MAXTERM
Boolean Expression in Sum of Products(SOP) and Product of
Sums(POS) Form or Normal Form
BOOLEAN FUNCTION
SWITICHING NETWORK FROM BOOLEAN EXPRESSION USING LOGIC GATES
KARNAUGH MAP
Rules used by K-map for simplification
Labeling of K-map Squares
Summary
Exercise 7
CHAPTER-8 COMPLEXITY
INTRODUCTION
ALGORITHM
Basic Criteria of Algorithm
DATA STRUCTURE
Operations on Data Structure
Categorizations of Data structure
Array as Non-primitive Data Structure
Structure as Non-primitive Data Structure
Abstract Data Type
Linear and Non-linear Data Structure
COMPLEXITY
Idea on Complexity Function of any Algorithm
Asymptote and Its Behavior
Why Asymptotic Notations to Express Inexact Running Time ?
Counting Strategy for Operations in Algorithm
Discussion on Order of Complexity
Mathematical Definitions of Some Useful Asymptotic Notations
Big oh
Big Omega
Theta
Little Oh and Little Omega
Standard Cases
Some Properties of Time Complexity Functions
Complexity of Recursive Procedures
Solving Recurrence Relation T(n) = aT(n/b) +f(n) , a ? 1 , b > 0
Comparison of Complexity
SEARCHING AND SORTING
Searching
Linear Search
Binary Search
Sorting
Merge Sorting
Bubble Sorting
Summary
Exercise 8
CHAPTER -9 GRAPH
INTRODUCTION
GRAPH AND BASIC TERMINOLOGIES
TYPES OF GRAPH
SUB-GRAPH AND ISOMORPHIC GRAPH
OPERATIONS ON GRAPH
REPRESENTATION OF GRAPH
Matrix Representation
Adjacency List Representation
Advantages and Disadvantages of Matrix and Linked list representations
Incidence Matrix Representation of Graph
GRAPH ALGORITHMS
BFS
DFS
Single Source Shortest Path Problem, Dijkstra's Algorithm
EULER GRAPH FLEURY'S ALGORITHM
Some Useful Results on Euler Graph
HAMILTONIAN GRAPH
Useful Hints on Hamiltonian circuit
PLANAR GRAPH
COLOURING OF GRAPH
COMPONENT
CUT VERTEX
FLOW NETWORK
Ford-Fulkerson Algorithm
Summary
Exercise 9
CHAPTER -10 TREE
INTRODUCTION
TREE
Common Terminologies on Tree
Labeled Tree
Some Diagrams of Directed and Undirected Trees
Summary of the Basic Properties of Tree
m-ary Tree, Complete Binary Tree, Full Binary Tree
Why skewed tree are considered as binary tree?
SOME IMPORTANT RESULTS ON TREE
SEQUENTIAL REPRESENTATION OF BINARY TREE
OPERATIONS ON TREE
Tree Traversal
More Discussions on Tree Traversals
Construction of unique Binary Tree when Pre-order and In-order
Traversal Sequences are given
Algorithm to Construct Unique Binary Tree using Pre-order and In-order Sequences
BINARY SEARCH TREE (BST)
Linked List Representation of Binary Tree
Construction of Binary Search Tree
RECURSIVE PROCEDURE FOR BINARY TREE TRAVERSAL
Analysis of Time Complexities for Some Operations on Binary Tree
PREDECESSOR AND SUCCESSOR NODE
EXPRESSION TREE
AVL TREE
SPANNING TREE
Minimum Spanning Tree(MST), Prim's and Kruskal's algorithm
GENERAL TREE
Conversion of General Tree to Binary Tree
Pre- order Traversal for General Tree
SOME IMPORTANT APPLICATIONS OF TREE
Summary
Exercise 10
CHAPTER-11 FORMAL LANGUAGE AND AUTOMATA
INTRODUCTION
MATHEMATICAL PRELIMINARIES
AUTOMATA
Basic Categories of Automata
State Transition Graph
Finite Automaton and Its Types
Deterministic Finite Automaton(DFA)
Non-deterministic Finite Automaton(NDFA)
Importance of NDFA
Graphical Notations Used in this Chapter in Drawing Finite Automata
Discussion on Designing of Some Basic FA's
Some Basic Tips to Design FA
Conversion Strategy from NDFA to DFA
Finite Automaton with Output
Transformation of Moore m/c to Mealy m/c
Transformation of Mealy m/c to Moore m/c
REGULAR EXPRESSION
Minimization of FA
Brief Discussion to Derive R.Es
Solved Problems on R.E.
The Identities on Regular Expression
Rules for Constructing NDFA from Regular Expression
Tips to Get Quick Answer of Some Special Problems on FA and R.E.
Pumping Lemma for Regular Language
Applications of Finite Automata and Regular Expression
GRAMMAR
Formal Defination of Grammar
The Chomsky Hierarchy
Derivation(Parsing)
Parsing Techniques
Ambiguous Grammar
Demerits of Ambiguous Grammar
Making Disambiguous Grammar
PUSHDOWN AUTOMATON (PDA)
Types of PDA
TURING MACHINE (TM)
Improvement in TM
Variations of TMs
Halting Problem
Turing Acceptable Language
Properties of Recursive and Recursively Enumerable Languages
Church Thesis
POST CORRESPONDENCE PROBLEM(PCP)
CLASSES OF PROBLEMS
WHAT IS CELLULAR AUTOMATA ?
FUZZY SETS AND LOGIC
RUSSELL'S PARADOX
History of the paradox
Summary
Exercise 11
Appendix 1
References
