离散数学（英文版•第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　Pascal's 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