图书简介

CHAPTER 1: SET RELATION FUNCTION; 1.1 INTRODUCTION; 1.2 SETS; 1.2.1 Representation of a Set; 1.2.2 Sets of Special Status; 1.2.3 Universal Set and Empty Set; 1.2.4 Subsets; 1.2.5 Power set; 1.2.6 Cardinality of a Set; 1.3 ORDERED PAIRS; 1.3.1 Cartesian Product of Sets; 1.3.2 Properties of Cartesian Product; 1.4 VENN DIAGRAMS; 1.5 OPERATIONS ON SETS; 1.5.1 Union of Sets; 1.5.2 Intersections of Set; 1.5.3 Complements; 1.5.4 Symmetric Difference; 1.6 COUNTABLE AND UNCOUNTABLE SETS; 1.7 ALGEBRA OF SETS; 1.8 MULTISET; 1.8.1 Operations on Multisets; 1.9 FUZZY SET; 1.9.1 Operations on Fuzzy Set; 1.10 GROWTH OF FUNCTION; 1.11 COMPUTER REPRESENTATION OF SETS; 1.12 INTRODUCTION; 1.13 BINARY RELATION; 1.14 CLASSIFICATION OF RELATIONS; 1.14.1 Reflexive Relation; 1.14.2 Symmetric Relation; 1.14.3 Antisymmetric Relation; 1.14.4 Transitive Relation; 1.14.5 Equivalence Relation; 1.14.6 Associative Relation; 1.15 COMPOSITION OF RELATIONS; 1.16 INVERSE OF A RELATION; 1.17 REPRESENTATION OF RELATIONS ON A SET; 1.18 CLOSURE OPERATION ON RELATIONS; 1.18.1 Reflexive Closure; 1.18.2 Symmetric Closure; 1.19 MATRIX REPRESENTATION OF RELATION; 1.20 DIGRAPHS; 1.20.1 Transitive Closure; 1.20.2 Warshall’s Algorithm; 1.21 PARTIAL ORDERING RELATION; 1.22 n-ARY RELATIONS AND THEIR APPLICATIONS; 1.23 RELATIONAL MODEL FOR DATABASES; 1.24 INTRODUCTION; 1.25 ADDITION AND MULTIPLICATION OF FUNCTIONS; 1.26 CLASSIFICATION OF FUNCTIONS; 1.26.1 One-to-one (Injective) Function; 1.26.2 Onto (Surjective) Functions; 1.26.3 One-to-one, Onto (Bijective) Function; 1.26.4 Identity Function; 1.26.5 Constant Function; 1.27 COMPOSITION OF FUNCTION; 1.27.1 Associativity of Composition of Functions; 1.28 INVERSE FUNCTION; 1.28.1 Invertible Function; 1.28.2 Image of a Subset; 1.29 HASH FUNCTION; 1.30 RECURSIVELY DEFINED FUNCTIONS; 1.31 SOME SPECIAL FUNCTIONS; 1.31.1 Floor and Ceiling Functions; 1.31.2 Integer and Absolute Value Functions; 1.31.3 Remainder Function; 1.32 FUNCTIONS OF COMPUTER SCIENCE; 1.32.1 Partial and Total Functions; 1.32.2 Primitive Recursive Function; 1.32.3 Ackermann Function; 1.33 THE INCLUSION-EXCLUSION PRINCIPLE; 1.33.1 Applications of Inclusion - Exclusion Principle; 1.34 SEQUENCE AND SUMMATION; 1.34.1 Sequence; 1.34.2 Summation; Summary; Exercise 1; CHAPTER 2 COMBINATORICS; 2.1 INTRODUCTION; 2.2 BASIC PRINCIPLES OF COUNTING; 2.2.1 Multiplication Principle (The Principles of Sequential Counting); 2.2.2 Addition Rule ( The Principle of Disjunctive Counting); 2.3 FACTORIAL NOTATION; 2.4 BINOMIAL THEOREM; 2.4.1 Pascal’s Triangle; 2.4.2 Multinomial Theorem; 2.5 PERMUTATIONS (Arrangements of Objects); 2.5.1 Permutations with Repetitions; 2.5.2 Circular Permutations; 2.6 COMBINATIONS (Selection of Objects); 2.6.1 Combinations of n Different Objects; 2.6.2 Combinations with Repetitions; 2.7 DISCRETE PROBABILITY; 2.7.1 Terminology (Basic Concepts); 2.8 FINITE PROBABILITY SPACES; 2.9 PROBABILITY OF AN EVENT; 2.9.1 Axioms of Probability; 2.9.2 Odds in favour and Odds against an Event; 2.9.3. Addition Principle; 2.10 CONDITIONAL PROBABILITY; 2.10.1 Multiplication Rule; 2.11 INDEPENDENT REPEATED TRIALS, BINOMIAL DISTRIBUTION; 2.11.1 Repeated Trials with Two Outcomes, Bernoulli Trials; 2.12 RANDOM VARIABLES; 2.12.1 Probability Distribution of a Random Variable; 2.12.2 Expectation of a Random Variable; 2.12.3 Variance and Standard Deviation of a Random Variable; 2.12.4 Binomial Distribution; 2.13 RECURSION; 2.13.1 Recursively Defined Sequences; 2.13.2 Recursive Definitions; 2.13.3 Recursively Defined Sets; 2.13.4 Recursively Defined Functions; 2.14 RECURENCE RELATION; 2.14.1 Order and Degree of Recurrence Relation; 2.14.2 Linear Homogenous and Non-homogeneous Recurrence Relations; 2.14.3 Solution of Linear Recurrence Relation with Constant Coefficients; 2.14.4 Homogenous Solution; 2.14.5 Particular Solution; 2.15 GENERATING FUNCTIONS; 2.16 COUNTING (COMBINATORIAL) METHOD; 2.17 THE PIGEONHOLE PRINCPLE; 2.17.1 Generalized Pigeonhole Principle; Summary; Exercise 2; CHAPTER 3 MATHEMATICAL LOGIC; 3.1 INTRODUCTION; 3.2 STATEMENT (PROPOSITIONS); 3.3 LAWS OF FORMAL LOGIC; 3.3.1 Law of Contradiction; 3.3.2 Law of Intermediate Exclusion; 3.4 BASIC SET OF LOGICAL OPERATORS /OPERATIONS; 3.4.1 Conjunction (AND, ); 3.4.2 Disjunction (OR, ); 3.4.3 Negation (NOT, ~ ); 3.5 PROPOSITIONS AND TRUTH TABLES; 3.5.1 Connectives; 3.5.2 Compound Propositions; 3.5.3 Conditional Statement; 3.5.4 Converse, Contrapositive, and Inverse; 3.5.5 Biconditional Statement; 3.6 ALGEBRA OF PROPOSITIONS; 3.7 PROPOSITIONAL FUNCTIONS; 3.8 TAUTOLOGIES AND CONTRADICTIONS; 3.9 LOGICAL EQUIVALENCE; 3.9.1 De Morgan Laws; 3.10 LOGICAL IMPLICATION; 3.11 NORMAL FORMS; 3.11.1 Disjunctive Normal Form (dnf); 3.11.2 Conjunctive Normal Form (cnf); 3.12 ARGUMENTS; 3.13 RULES OF INFERENCE; 3.13.1 Law of Detachment (or Modus Pones); 3.13.2 Law of Contraposition (Modus tollens); 3.13.3 Disjunctive Syllogism; 3.13.4 Hypothetical Syllogism; 3.14 WELL FORMED FORMULAE; 3.15 PREDICATE CALCULUS; 3.16 QUANTIFIER; 3.16.1 Universal Quantifier; 3.16.2 Existential Quantifier; 3.17 INTRODUCTION TO PROOFS; 3.17.1 Brief Status of Terminology; 3.17.2 Methods of Proof; 3.17.3 Direct Proof; 3.17.4 Consistency; 3.17.5 Method of Proof by Contraposition; 3.17.6 Proof by Contradiction (reduction ad absurdum); 3.17.7 Proof by Mathematical Induction; 3.17.8 Proof by Cases; Summary; Exercise 3; CHAPTER 4 ALGEBRAIC STRUCTURE; 4.1 INTRODUCTION; 4.2 BINARY OPERATIONS; 4.2.1 Properties of Binary Operations; 4.3 GROUPS; 4.3.1 Abelian Group; 4.3.2 Properties of Groups; 4.3.3 Products and Quotients of Groups; 4.4 SEMIGROUPS; 4.4.1 Isomorphism and Homomorphism; 4.4.2 Products and Quotients of Semigroups; 4.5 SUBGROUP; 4.6 CYCLIC GROUP; 4.7 PERMUTATION GROUPS; 4.7.1 Equality of Permutations; 4.7.2 Permutation Identity; 4.7.3 Composition of Permutations (or, Product of Permutations); 4.7.4 Inverse Permutation; 4.7.5 Cyclic Permutations; 4.7.6 Transposition; 4.7.7 Even and Odd Permutations; 4.8 SYMMETRIC GROUP; 4.9 COSETS; 4.9.1 Properties of Cosets; 4.10 NORMAL SUBGROUP; 4.11 LAGRANGE’S THEOREM; 4.12 GROUP CODES; 4.12.1 Coding of Binary Information; 4.12.2 Parity and Generator Matrices; 4.12.3 Decoding and Error Correction; 4.13 ALGEBRAIC SYSTEMS WITH TWO BINARY OPERATIONS; 4.13.1 Rings; 4.13.2 Elementary Properties of a Ring; 4.13.3 Special kinds of Rings; 4.13.4 Integral Domain; 4.13.5 Field; 4.14 SUBRING; 4.14.1 Ideal; 4.14.2 Quotient Ring; 4.14.3 Morphisms of Rings; 4.14.4 Properties of Homomorphism of Ring; Summary; Exercise 4; Chapter 5 MATRIX ALGEBRA; 5.1 INTRODUCTION; 5.2 DEFINITION OF A MATRIX; 5.3 TYPES OF MATRICES; 5.3.1 Rectangular and Square Matrices; 5.3.2 Row matrix or a row vector; 5.3.3 Column matrix or a column vector; 5.3.4 Zero or Null matrix; 5.3.5 Diagonal elements of a matrix; 5.3.6 Diagonal matrix; 5.3.7 Scalar matrix; 5.3.8 Unit Matrix or Identity Matrix; 5.3.9 Comparable Matrices; 5.3.10 Equal Matrices; 5.3.11 Upper Triangular Matrix; 5.3.12 Lower Triangular Matrix; 5.4 OPERATIONS ON MATRICES; 5.4.1 Addition of Matrices; 5.4.2 Subtraction of Matrices; 5.4.3 Scalar Multiple of a Matrix; 5.4.4 Multiplication of Matrices; 5.4.5 Properties of Matrix Multiplication; 5.4.6 Positive Integral Powers of Matrices; 5.4.7 Sub Matrix; 5.4.8 Partition of Matrices; 5.5 RELATED MATRICES; 5.5.1 Transpose of a Matrix; 5.5.2 Symmetric and Skew-Symmetric Matrix; 5.5.3 Complex Matrices; 5.5.4 Conjugate of a Matrix; 5.5.5 Conjugate Transpose of a Matrix; 5.5.6 Hermitian and Skew-Hermitian Matrices; 5.6 DETERMINANT OF A MATRIX; 5.6.1 Minor and Co-factor; 5.6.2 Expansion of the determinant ( ); 5.6.3 Difference between a Matrix and a Determinant; 5.7 TYPICAL SQUARE MATRICES; 5.7.1 Orthogonal Matrix; 5.7.2 Unitary Matrix; 5.7.3 Involutory Matrix; 5.7.4 Idempotent Matrix; 5.7.5 Nilpotent Matrix; 5.8 ADJOINT AND INVERSE OF A MATRIX; 5.8.1 Singular and Non-singular Matrices; 5.8.2 Adjoint of a Square Matrix; 5.8.3 Properties of Adjoint of a Matrix; 5.9 INVERSE OF A MATRIX; 5.9.1 Properties of Inverse of a Matrix; 5.10 RANK OF A MATRIX; 5.10.1 Elementary transformations (operations) of a matrix; 5.11 BOOLEAN MATRIX OR A ZERO-ONE MATRIX; 5.11.1 Operations on Zero-one Matrices; 5.11.2 Boolean product of matrices; 5.11.3 Echelon Matrix (Row Reduced Echelon Form); 5.11.4 Normal form of a Matrix; 5.11.5 Procedure of reduction of a matrix A to its normal form; 5.12 SOLUTION OF LINEAR AL GEBRAIC EQUATIONS; 5.12.1 Linear Homogenous Equations (Ax = 0); 5.12.2 Linear Non-homogenous Equations (Ax = b); 5.12.3 Consistent and Inconsistent Equations; 5.13 EIGEN VALUES AND EIGEN VECTORS; 5.13.1 Determination of Eigen values and Eigen vectors; 5.13.2 Linear Transformations; 5.13.3 Properties of Eigen values and Eigen vectors; 5.14 CAYLEY - HAMILTON THOREM; 5.14.1 Inverse of the Matrix; Summary; Exercise 5; Chapter 6 ORDER RELATION AND LATTICE; 6.1 INTRODUCTION; 6.2 PARTIALLY ORDERED SET; 6.2.1 Comparability of Elements; 6.2.2 Linearly ordered set; 6.3 HASSE DIAGRAM; 6.3.1 Topological Sorting; 6.3.2 Chain; 6.3.3 Antichain; 6.4 ISOMORPHISM; 6.4.1 Isomorphic Ordered Sets; 6.5 LEXICOGRAPHIC ORDERING; 6.6 EXTREMAL ELEMENTS OF POSETS; 6.6.1 Maximal Element; 6.6.2 Minimal Element; 6.6.3 Greatest and Least Elements; 6.6.4 Upper and Lower Bounds; 6.6.5 Least Upper Bound (Supremum); 6.6.6 Greatest Lower Bound (Infimum); 6.7 WELL-ORDERED SET; 6.8 CONSISTENT ENUMERATIONS; 6.9 LATTICES; 6.9.1 Principle of Duality; 6.9.2 Isotonocity Property; 6.10 SUB LATTICES; 6.11 DIRECT PRODUCT OF LATTICES; 6.12 SOME SPECIAL CLASS OF LATTICES; 6.12.1 Complete Lattice; 6.12.2 Bounded Lattice; 6.12.3 Properties of Bounded Lattice; 6.12.4 Distributive Lattice; 6.12.5 Modular Lattice; 6.12.6 Complemented Lattices; 6.12.7 Isomorphic Lattices; 6.12.8 Join-irreducible; 6.12.9 Meet-irreducible; 6.13 LATTICE HOMOMORPHISM; Summary; Exercise 6; CHAPTER-7 BOOLEAN ALGEBRA; 7.1 INTRODUCTION; 7.2 LAWS ON BOOLEAN ALGEBRA; 7.3 TRUTH TABLES ON BOOLEAN OPERATIONS; 7.4 UNIQUE FEATURES OF BOOLEAN ALGEBRA; 7.5 MINTERM AND MAXTERM; 7.5.1 Boolean Expression in Sum of Products(SOP) and Product of; 7.5.2 Sums(POS) Form or Normal Form; 7.6 BOOLEAN FUNCTION; 7.7 SWITICHING NETWORK FROM BOOLEAN EXPRESSION USING LOGIC GATES; 7.8 KARNAUGH MAP; 7.8.1 Rules used by K-map for simplification; 7.8.2 Labeling of K-map Squares; Summary; Exercise 7; CHAPTER-8 COMPLEXITY; 8.1 INTRODUCTION; 8.2 ALGORITHM; 8.2.1. Basic Criteria of Algorithm; 8.3. DATA STRUCTURE; 8.3.1. Operations on Data Structure; 8.3.2. Categorizations of Data structure; 8.3.2.1. Array as Non-primitive Data Structure; 8.3.2.2 Structure as Non-primitive Data Structure; 8.3.3 Abstract Data Type; 8.3.4 Linear and Non-linear Data Structure; 8.4. COMPLEXITY; 8.4.1. Idea on Complexity Function of any Algorithm; 8.4.2 Asymptote and Its Behavior; 8.4.3. Why Asymptotic Notations to Express Inexact Running Time ?; 8.4.4. Counting Strategy for Operations in Algorithm; 8.4.5 Discussion on Order of Complexity; 8.4.6 Mathematical Definitions of Some Useful Asymptotic Notations; 8.4.6.1. Big oh; 8.4.6.2. Big Omega; 8.4.6.3 Theta; 8.4.6.4. Little Oh and Little Omega; 8.4.7. Standard Cases; 8.4.8. Some Properties of Time Complexity Functions; 8.4.9 Complexity of Recursive Procedures; 8.4.10 Solving Recurrence Relation T(n) = aT(n/b) +f(n) , a ? 1 , b > 0; 8.4.11. Comparison of Complexity; 8.5. SEARCHING AND SORTING; 8.5.1. Searching; 8.5.1.1 Linear Search; 8.5.1.2. Binary Search; 8.5.2. Sorting; 8.5.2.1. Merge Sorting; 8.5.2.2. Bubble Sorting; Summary; Exercise 8; CHAPTER -9 GRAPH; 9.1. INTRODUCTION; 9.2 GRAPH AND BASIC TERMINOLOGIES; 9.3. TYPES OF GRAPH; 9.4 SUB-GRAPH AND ISOMORPHIC GRAPH; 9.5 OPERATIONS ON GRAPH; 9.6. REPRESENTATION OF GRAPH; 9.6.1. Matrix Representation; 9.6.2. Adjacency List Representation; 9.6.3. Advantages and Disadvantages of Matrix and Linked list representations; 9.6.4 Incidence Matrix Representation of Graph; 9.7. GRAPH ALGORITHMS; 9.7.1. BFS; 9.7.2 DFS; 9.7.3 Single Source Shortest Path Problem, Dijkstra’s Algorithm; 9.8 EULER GRAPH FLEURY’S ALGORITHM; 9.8.1 Some Useful Results on Euler Graph; 9.9 HAMILTONIAN GRAPH; 9.9.1 Useful Hints on Hamiltonian circuit; 9.10 PLANAR GRAPH; 9.11 COLOURING OF GRAPH; 9.12 COMPONENT; 9.13. CUT VERTEX; 9.14. FLOW NETWORK; 9.14.1 Ford-Fulkerson Algorithm; Summary; Exercise 9; CHAPTER -10 TREE; 10.1. INTRODUCTION; 10.2. TREE; 10.2.1. Common Terminologies on Tree; 10.2.2. Labeled Tree; 10.2.3 Some Diagrams of Directed and Undirected Trees; 10.2.4 Summary of the Basic Properties of Tree; 10.2.5 m-ary Tree, Complete Binary Tree, Full Binary Tree; 10.2.6. Why skewed tree are considered as binary tree?; 10.3. SOME IMPORTANT RESULTS ON TREE; 10.4. SEQUENTIAL REPRESENTATION OF BINARY TREE; 10.5. OPERATIONS ON TREE; 10.5.1. Tree Traversal; 10.5.2 More Discussions on Tree Traversals; 10.5.3 Construction of unique Binary Tree when Pre-order and In-order; 10.5.4 Traversal Sequences are given; 10.5.5. Algorithm to Construct Unique Binary Tree using Pre-order and In-order Sequences; 10.6. BINARY SEARCH TREE (BST); 10.6.1 Linked List Representation of Binary Tree; 10.6.2. Construction of Binary Search Tree; 10.6.3. Useful Results from Binary Search Tree ; 10.7. RECURSIVE PROCEDURE FOR BINARY TREE TRAVERSAL; 10.7.1. Analysis of Time Complexities for Some Operations on Binary Tree; 10.8. PREDECESSOR AND SUCCESSOR NODE; 10.9. EXPRESSION TREE; 10.10. AVL TREE; 10.11. SPANNING TREE; 10.11.1 Minimum Spanning Tree(MST), Prim’s and Kruskal’s algorithm; 10.12. GENERAL TREE; 10.12.1. Conversion of General Tree to Binary Tree; 10.12.2. Pre- order Traversal for General Tree; 10.13. SOME IMPORTANT APPLICATIONS OF TREE; Summary; Exercise 10; CHAPTER-11 FORMAL LANGUAGE AND AUTOMATA; 11.1 INTRODUCTION; 11. 2 MATHEMATICAL PRELIMINARIES; 11. 3 AUTOMATA; 11.3.1 Basic Categories of Automata; 11.3.1.1. State Transition Graph; 11.3.2 Finite Automaton and Its Types; 11.3.2.1 Deterministic Finite Automaton(DFA); 11.3.2.2 Non-deterministic Finite Automaton(NDFA); 11.3.3 Importance of NDFA; 11.3.4 Graphical Notations Used in this Chapter in Drawing Finite Automata; 11.3.5 Discussion on Designing of Some Basic FA’s; 11.3.6 Some Basic Tips to Design FA; 11.3.7 Conversion Strategy from NDFA to DFA; 11.3.8 Finite Automaton with Output; 11.3.8.1 Transformation of Moore m/c to Mealy m/c; 11.3.8.2 Transformation of Mealy m/c to Moore m/c; 11.4 REGULAR EXPRESSION; 11.4.1 Minimization of FA; 11.4.2 Brief Discussion to Derive R.Es; 11.4.3 Solved Problems on R.E.; 11. 4. 4 The Identities on Regular Expression; 11. 4. 5 Rules for Constructing NDFA from Regular Expression; 11. 4. 6 Tips to Get Quick Answer of Some Special Problems on FA and R.E.; 11.4.7 Pumping Lemma for Regular Language; 11. 4. 8 Applications of Finite Automata and Regular Expression; 11.5 GRAMMAR; 11. 5. 1 Formal Defination of Grammar; 11. 5. 2 The Chomsky Hierarchy; 11. 5. 3 Derivation(Parsing); 11. 5. 4 Parsing Techniques; 11. 5. 5 Ambiguous Grammar; 11. 5. 5.1 Demerits of Ambiguous Grammar; 11. 5. 5.2 Making Disambiguous Grammar; 11. 6 PUSHDOWN AUTOMATON (PDA); 11.6.1 Types of PDA; 11. 7 TURING MACHINE (TM); 11.7.1 Improvement in TM; 11.7.2 Variations of TMs; 11.7.3 Halting Problem; 11.7.4 Turing Acceptable Language; 11.7.5 Properties of Recursive and Recursively Enumerable Languages; 11.7.6 Church Thesis; 11.8 POST CORRESPONDENCE PROBLEM(PCP); 11.9 CLASSES OF PROBLEMS; 11.10 WHAT IS CELLULAR AUTOMATA ?; 11.11 FUZZY SETS AND LOGIC; 11.12 RUSSELL’S PARADOX; 11.12.1 History of the paradox; Summary; Exercise 11; Appendix 1; References

Trade Policy 买家须知