| 作者 |
| [美] 约翰·A. 多西（John A. Dossey）艾伯特·D. 奥托（Albert D. Otto）劳伦斯·E. 思朋斯（Lawrence E. Spence）查尔斯·范登·艾登（Charles Vanden Eynden） |
| 丛书名 |
| 经典原版书库 |
| 出版社 |
| 机械工业出版社 |
| ISBN |
| 9787111671831 |
| 简要 |
| 简介 |
| 内容简介书籍数学书籍 本书充分考虑到初学者的需要，内容、例题、习题都经过精心的挑选和组织，讲解细致，循序渐进，实例贴近日常生活或计算机应用。本书注重算法，且算法描述独立于某种具体的编程语言。教师可根据学生的层次和兴趣来灵活拓展和组织讲解内容。 本书可作为计算机专业或其他相关专业的离散数学教材或教学参考书，也可作为自学者的参考用书 |
| 目录 |
| 第1章 组合问题与组合技术引论 1 1.1 工程完成时间的问题 2 1.2 匹配问题 10 1.3 背包问题 16 1.4 算法及其效率 23 历史注记 35 补充习题 37 计算机题 39 推荐读物 40 第2章 集合、关系和函数 41 2.1 集合运算 41 2.2 等价关系 47 *2.3 偏序关系 54 2.4 函数 65 2.5 数学归纳法 76 2.6 应用 84 历史注记 93 补充习题 95 计算机题 98 推荐读物 98 第3章 编码理论 99 3.1 同余 100 3.2 欧几里得算法 106 3.3 RSA方法 113 3.4 检错码和纠错码 122 3.5 矩阵码 132 3.6 单纠错矩阵码 140 历史注记 147 补充习题 149 计算机题 152 推荐读物 153 第4章 图 154 4.1 图及其表示 154 4.2 通路和回路 164 4.3 最短通路和距离 181 4.4 图着色 193 4.5 有向图和有向多重图 202 历史注记 219 补充习题 220 计算机题 226 推荐读物 227 第5章 树 228 5.1 树的性质 228 5.2 生成树 238 5.3 深度优先搜索 253 5.4 根树 266 5.5 二叉树和遍历 274 5.6 最优二叉树和二叉搜索树 287 历史注记 306 补充习题 308 计算机题 311 推荐读物 312 第6章 匹配 313 6.1 相异代表系 313 6.2 图中的匹配 319 6.3 匹配算法 327 6.4 算法的应用 337 6.5 匈牙利方法 346 历史注记 354 补充习题 355 计算机题 357 推荐读物 357 第7章 网络流 358 7.1 流和割 358 7.2 流增广算法 369 7.3 最大流最小割定理 382 7.4 流和匹配 389 历史注记 397 补充习题 397 计算机题 400 推荐读物 401 第8章 计数技术 402 8.1 帕斯卡三角形和二项式定理 402 8.2 3个基本原理 406 8.3 排列和组合 416 8.4 允许重复的排列和组合 421 8.5 概率 428 *8.6 容斥原理 434 *8.7 排列和r组合的生成 445 历史注记 452 补充习题 453 计算机题 456 推荐读物 457 第9章 递推关系与生成函数 458 9.1 递推关系 458 9.2 迭代法 470 9.3 常系数线性差分方程 482 *9.4 用递推关系分析算法的效率 494 9.5 用生成函数计数 506 9.6 生成函数的代数 513 历史注记 523 补充习题 524 计算机题 527 推荐读物 528 第10章 组合电路和有限状态机 529 10.1 逻辑门 529 10.2 构造组合电路 538 10.3 卡诺图 546 10.4 有限状态机 560 历史注记 569 补充习题 570 计算机题 573 推荐读物 573 附录A 逻辑和证明简介 574 A.1 命题和联结词 574 A.2 逻辑等价 583 A.3 证明的方法 587 历史注记 593 补充习题 594 推荐读物 596 附录B 矩阵 597 历史注记 604 附录C 本书中的算法 607 参考文献 613 奇数号习题答案 618 图片来源 658 Contents 1AN INTRODUCTION TO COMBINATORIAL PROBLEMS AND TECHNIQUES1 1.1 The Time to Completea Project 2 1.2 A Matching Problem 10 1.3 A Knapsack Problem 16 1.4 Algorithms and Their 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 and Their Representations 154 4.2 Pathsand 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-Cut Theorem 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 The Algebra 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 LOGIC AND 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 IN THIS BOOK 607 BIBLIOGRAPHY 613 ANSWERS TO ODD-NUMBERED EXERCISES 618 PHOTO CREDITS 658 |