| Uniform title | Diskrete mathematik. English |
| Contents |
Prefaces -- pt. 1. Counting -- ch. 1. Fundamentals -- 1.1. Elementary counting principles -- 1.2. The fundamental counting coefficients -- 1.3. Permutations -- 1.4. Recurrence equations -- 1.5. Discrete probability -- 1.6. Existence theorems -- Exercises for Chapter 1 -- ch. 2. Summation -- 2.1. Direct methods -- 2.2. The calculus of finite differences -- 2.3. Inversion -- 2.4. Inclusion-exclusion -- Exercises for Chapter 2 -- ch. 3. Generating functions -- 3.1. Definitions and examples -- 3.2. Solving recurrences -- 3.3. Generating functions of exponential type -- Exercises for Chapter 3 -- ch. 4. Counting patterns -- 4.1. Symmetries -- 4.2. Statement of the problem -- 4.3. Patterns and the cycle indicator -- 4.4. Pólya's theorem -- Exercises for Chapter 4 -- ch. 5. Asymptotic analysis -- 5.1. The growth of functions -- 5.2. Order of magnitude of recurrence relations -- 5.3. Running times of algorithms -- Exercises for Chapter 5 -- Bibliography for Part 1 -- |
| Contents |
pt. 2. Graphs and algorithms -- ch. 6. Graphs -- 6.1. Definitions and examples -- 6.2. Representation of graphs -- 6.3. Paths and circuits -- 6.4. Directed graphs -- Exercises for Chapter 6 -- ch. 7. Trees -- 7.1. What is a tree? -- 7.2. Breadth-frist and depth-first search -- 7.3. Minimal spanning trees -- 7.4. The shortest path in an graph-- Exercises for Chapter 7 -- ch. 8. Matchings and networks -- 8.1. Matchings in bipartite graphs -- 8.2. Construction of optimal matchings -- 8.3. Flows in networks -- 8.4. Eulerian graphs and the traveling salesman problem -- 8.5. The complexity classes P and NP -- Exercises for Chapter 8 -- ch. 9. Searching and sorting -- 9.1. Search problems and decision trees -- 9.2. The fundamental theorem of search theory -- 9.3. Sorting lists -- 9.4. Binary search trees -- Exercises for Chapter 9 -- ch. 10. General optimization methods -- 10.1. Backtracking -- 10.2. Dynamic programming -- 10.3. The Greedy algorithm -- Exercises for Chapter 10 -- Bibliography for Part 2 -- |
| Contents |
pt. 3. Algebraic systems -- ch. 11. Boolean algebras -- 11.1. Definition and properties -- 11.2. Propositional logic and Boolean functions -- 11.3. Logical nets -- 11.4. Boolean lattices, orders, and hypergraphs -- Exercises for Chapter 11 -- ch. 12. Modular arithmetic -- 12.1. Calculating with congruences -- 12.2. Finite fields -- 12.3. Latin squares -- 12.4. Combinatorial designs -- Exercises for Chapter 12 -- ch. 13. Coding -- 13.1. Statement of the problem -- 13.2. Source encoding -- 13.3. Error detection and correction -- 13.4. Linear codes -- 13.5. Cyclic codes -- Exercises for Chapter 13 -- ch. 14. Cryptography -- 14.1. Cryptosystems -- 14.2. Linear shift registers -- 14.3. Public-key cryptosystems -- 14.4. Zero-knowledge protocols -- Exercises for Chapter 14 -- ch. 15. Linear optimization -- 15.1. Examples and definitions -- 15.2. Duality -- 15.3. The fundamental theorem of linear optimization -- 15.4. Admissible solutions and optimal solutions -- 15.5. The simplex algorithm -- 15.6. Integer linear optimization -- Exercises for Chapter 15 -- Bibliography for Part 3 -- Solutions to selected exercises -- Index. |
| Bibliography note | Includes bibliographical references and index. |
| LCCN | 2006052285 |
| ISBN | 9780821841518 (alk. paper) |
| ISBN | 0821841513 (alk. paper) |
