离散数学（英文版）（第5版）

　　PREFACE　　111
　　TO THE STUDENT　viii
　　1　AN INTRODUCTION TO COMBINATORIAL PROBLEMS AND
　　TECHNIQUES 1
　　1.1　TheTime to Complete a Project　2
　　1.2　A Matching Problem　10
　　1.3　A Knapsack Problem　16
　　1.4　Algorithms andTheir Efficiency　23
　　Historical Notes　35
　　Supplementary Exercises　37
　　Computer Projects　39
　　Suggested Readings　40
　　2　SETS, RELATIONS, AND FUNCTIONS　41
　　2.1　Set Operations　41
　　2.2　Equivalence Relations　47
　　2.3* Partial Ordering Relations　54
　　2.4　Functions　65
　　2.5　Mathematical Induction　76
　　2.6　Applications　84
　　Historical Notes　93
　　Supplementary Exercises　95
　　Computer Projects　98
　　Suggested Readings　98
　　3　CODING THEORY　99
　　3.1　Congruence　100
　　3.2 The Euclidean Algorithm　106
　　3.3 The RSA Method　113
　　3.4　Error-Detecting and Error-Correcting Codes　122
　　3.5　Matrix Codes　132
　　3.6　Matrix Codes that Correct All Single-Digit Errors　140
　　Historical Notes　147
　　Supplementary Exercises　149
　　Computer Projects　152
　　Suggested Readings　153
　　4 GRAPHS 154
　　4.1　Graphs andTheir Representations　154
　　4.2　Paths and Circuits　164
　　4.3　Shortest Paths and Distance　181
　　4.4　Coloringa Graph　193
　　4.5　Directed Graphs and Multigraphs　202
　　Historical Notes　219
　　Supplementary Exercises　220
　　Computer Projects　226
　　Suggested Readings　227
　　5 TREES 228
　　5.1　Properties of Trees　228
　　5.2　Spanning Trees　238
　　5.3　Depth-First Search　253
　　5.4　Rooted Trees　266
　　5.5　Binary Trees and Traversals　274
　　5.6　Optimal Binary Trees and Binary Search Trees　287
　　Historical Notes　306
　　Supplementary Exercises　308
　　Computer Projects　311
　　Suggested Readings　312
　　6　MATCHING　313
　　6.1　Systems of Distinct Representatives　313
　　6.2　Matchings in Graphs　319
　　6.3 A Matching Algorithm　327
　　6.4 Applications of the Algorithm　337
　　6.5 The Hungarian Method　346
　　Historical Notes　354
　　Supplementary Exercises　355
　　Computer Projects　357
　　Suggested Readings　357
　　7　NETWORK FLOWS　358
　　7.1　Flows and Cuts　358
　　7.2　A Flow Augmentation Algorithm　369
　　7.3 The Max-Flow Min-CutTheorem　382
　　7.4　Flows and Matchings　389
　　Historical Notes　397
　　Supplementary Exercises　397
　　Computer Projects　400
　　Suggested Readings　401
　　8　COUNTING TECHNIQUES　402
　　8.1　Pascals Triangle and the Binomial Theorem　402
　　8.2　Three Fundamental Principles　406
　　8.3　Permutations and Combinations　416
　　8.4　Arrangements and Selections with Repetitions　421
　　8.5　Probability　428
　　8.6* The Principle of Inclusion-Exclusion　434
　　8.7* Generating Permutations and r-Combinations　445
　　Historical Notes　452
　　Supplementary Exercises　453
　　Computer Projects　456
　　Suggested Readings　457
　　9　RECURRENCE RELATIONS AND GENERATING FUNCTIONS　458
　　9.1　Recurrence Relations　458
　　9.2　The Method of Iteration　470
　　9.3　Linear Difference Equations with Constant Coefficients　482
　　9.4* Analyzing the Efficiency of Algorithms with Recurrence
　　Relations　494
　　9.5 Counting with Generating Functions　506
　　9.6 TheAIgebra of Generating Functions　513
　　Historical Notes　523
　　Supplementary Exercises　524
　　Computer Projects　527
　　Suggested Readings　528
　　10　COMBINATORIAL CIRCUITS AND FINITE STATE MACHINES　529
　　10.1 Logical Gates　529
　　10.2 Creating Combinatorial Circuits　538
　　10.3 Karnaugh Maps　546
　　10.4 Finite State Machines　560
　　Historical Notes　569
　　Supplementary Exercises　570
　　Computer Projects　573
　　Suggested Readings　573
　　A　AN INTRODUCTION TO LOGICAND PROOF　574
　　A.1　Statements and Connectives　574
　　A.2　Logical Equivalence　583
　　A.3　Methods of Proof　587
　　Historical Notes　593
　　Supplementary Exercises　594
　　Suggested Readings　596
　　B　MATRICES　597
　　Historical Notes　604
　　C　THE ALGORITHMS INTHIS BOOK　607
　　BIBLIOGRAPHY　613
　　ANSWERS TO ODD-NUMBERED EXERCISES　618
　　PHOTO CREDITS　658
　　INDEX　659

　　本书凝聚了作者多年的研究成果和实践经验，是一本优秀的离散数学入门教材。本书充分考虑到初学者的需要，内容、例题、习题都经过精心的挑选和组织，讲解细致，循序渐进，实例贴近日常生活或计算机应用。本书注重算法，且算法描述独立于某种具体的编程语言。教师可根据学生的层次和兴趣来灵活拓展和组织讲解内容。
　　本书可作为计算机专业或其他相关专业的离散数学教材或教学参考书，也可作为自学者的参考用书。