Discrete Mathematics and Applied Modern Algebra

Description

Title Preface Contents 1. Group Codes 1.1 Examples of Codes 1.2 Error-Correcting Codes 1.3 Group Codes 1.4 Construction of Group Codes 1.5 Construction of Error-Correcting Codes 1.6 Efficient Error Correction 2. Groups 2.1 Groups of Symmetries 2.2 The Definition of a Group 2.3 Modular Number Systems; Products 2.4 Elementary Properties of Groups 2.5 Subgroups 2.6 Permutation Groups 3. Relations 3.1 Relations; Equivalence Relations 3.2 Lagrange's Theorem 3.3 Burnside's Theorem 3.4 Partial Orders 4. Graph Theory 4.1 Graphs: Directed Graphs 4.2 Trees 4.3 Directed Trees 5. Boolean Algebras 5.1 Examples and Definitions 5.2 Boolean Polynomials, Switching Circuits, and Logic 5.3 Disjunctive Normal Form 5.4 Finite Boolean Algebras 6. Fast Sorting and Fast Addition 6.1 Sorting 6.2 Series and Parallel Adders 6.3 How Good Are the Adders? 6.4 Addition in ZN 6.5 The Chinese Remainder Theorem 7. Finite-State Machines 7.1 Definitions and Examples 7.2 State Diagrams 7.3 Limitations of Finite Machines 7.4 State Reduction 7.5 Simulation and Homomorphism 7.6 Monoids. Semigroups, and Machines 8. Formal Languages 8.1 Examples 8.2 Context-Free Languages 8.3 Regular Languages 8.4 An Algebraic Characterization of Regular Languages 9. Rings and Fields 9.1 The Euclidean Algorithm 9.2 Rings; Polynomial Rings 9.3 The Fast Fourier Transform 9.4 Fast Multiplication 9.5 Fields; Finite Fields 9.6 Polynomial Codes; BCH Codes Appendix: Mathematical Induction A.1 Statement and Examples A.2 Applications to the Text Answers to Selected Exercises Index