(特价书)离散数学及其应用（英文版·原书第8版）

3.2 The Growth of Functions........................................216
3.3 Complexity of Algorithms........................................231
End-of-Chapter Materia........................................244
4 Number Theory and Cryptography..................................251
4.1 Divisibility and Modular Arithmetic........................................251
4.2 Integer Representations and Algorithms........................................260
4.3 Primes and Greatest Common Divisors........................................271
4.4 Solving Congruences........................................290
4.5 Applications of Congruences........................................303
4.6 Cryptography........................................310
End-of-Chapter Materia........................................324
5 Induction and Recursion........................................331
5.1 Mathematical Induction........................................331
5.2 Strong Induction and Well-Ordering........................................354
5.3 Recursive Definitions and Structural Induction..................................365
5.4 Recursive Algorithms........................................381
5.5 Program Correctness........................................393
End-of-Chapter Materia........................................398
6 Counting........................................405
6.1 The Basics of Counting........................................405
6.2 The Pigeonhole Principle........................................420
6.3 Permutations and Combinations........................................428
6.4 Binomial Coeficients and Identities........................................437
6.5 Generalized Permutations and Combinations...................................445
6.6 Generating Permutations and Combinations....................................457
End-of-Chapter Materia........................................461
7 Discrete Probability........................................469
7.1 An Introduction to Discrete Probability........................................469
7.2 Probability Theory........................................477
7.3 Bayes’Theorem........................................494
7.4 Expected Valueand Variance........................................503
End-of-Chapter Materia........................................520
8 Advanced Counting Techniques.....................................527
8.1 Applications of Recurrence Relations........................................527
8.2 Solving Linear Recurrence Relations........................................540
8.3 Divide-and-Conquer Algorithms and Recurrence Relations......................553
8.4 Generating Functions........................................563
8.5 Inclusion–Exclusion........................................579
8.6 Applications of Inclusion–Exclusion........................................585
End-of-Chapter Materia........................................592
9 Relations........................................599
9.1 Relations and Their Properties........................................599
9.2 n-ary Relations and Their Applications........................................611
9.3 Representing Relations........................................621
9.4 Closures of Relations........................................628
9.5 Equivalence Relations........................................638
9.6 Partial Orderings........................................650
End-of-Chapter Materia........................................665
10 Graphs........................................673
10.1 Graphs and Graph Models........................................673
10.2 Graph Terminology and Special Types of Graphs...............................685
10.3 Representing Graphs and Graph Isomorphism..................................703
10.4 Connectivity........................................714
10.5 Euler and Hamilton Paths........................................728
10.6 Shortest-Path Problems........................................743
10.7 Planar Graphs........................................753
10.8 Graph Coloring........................................762
End-of-Chapter Materia........................................771
11 Trees........................................781
11.1 Introduction to Trees........................................781
11.2 Applications of Trees........................................793
11.3 Tree Traversal........................................808
11.4 Spanning Trees........................................821
11.5 Minimum Spanning Trees........................................835
End-of-Chapter Materia........................................841
12 Boolean Algebra........................................847
12.1 Boolean Functions........................................847
12.2 Representing Boolean Functions........................................855
12.3 Logic Gates........................................858
12.4 Minimization of Circuits........................................864
End-of-Chapter Materia........................................879
13 Modeling Computation ........................................885
13.1 Languages and Grammars........................................885
13.2 Finite-State Machines with Output........................................897
13.3 Finite-State Machines with NoOutput........................................904
13.4 Language Recognition........................................917
13.5 Turing Machines........................................927
End-of-Chapter Materia........................................938
Appendices........................................A-1
1 Axioms for the Real Numbers and the Positive Integers..........................A-1
2 Exponential and Logarithmic Functions........................................A-7
3 Pseudocode........................................A-11
Suggested ReadingsB-1
Answers to Odd-Numbered Exercises S-1
Index of BiographiesI-1
IndexI-2