[套装书]离散数学及其应用（原书第8版）+算法导论(原书第3版)（2册）
| 作者 |
| [美]肯尼思·H. 罗森（Kenneth H. Rosen）(美)Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest Clifford Stein |
| 丛书名 |
| 计算机科学丛书 |
| 出版社 |
| 机械工业出版社 |
| ISBN |
| 9781911041656 |
| 简要 |
| 简介 |
| 内容简介书籍计算机书籍 ---------------------------离散数学及其应用（原书第8版）--------------------------- 本书是经典的离散数学教材，被全球数百所大学广为采用。书中全面而系统地介绍了离散数学的理论和方法，主要包括：逻辑和证明，集合、函数、序列、求和与矩阵，算法，数论和密码学，归纳与递归，计数，离散概率，关系，图，树，布尔代数，计算模型。全书取材广泛，除包括定义、定理的严格陈述外，还配备大量的例题、图表、应用实例和练习。第8版做了与时俱进的更新，成为更加实用的教学工具。本书可作为高等院校数学、计算机科学和计算机工程等专业的教材，也可作为科技领域从业人员的参考书。 ---------------------------算法导论(原书第3版)--------------------------- 在有关算法的书中，有一些叙述非常严谨，但不够全面；另一些涉及了大量的题材，但又缺乏严谨性。本书将严谨性和全面性融为一体，深入讨论各类算法，并着力使这些算法的设计和分析能为各个层次的读者接受。全书各章自成体系，可以作为独立的学习单元；算法以英语和伪代码的形式描述，具备初步程序设计经验的人就能看懂；说明和解释力求浅显易懂，不失深度和数学严谨性。 《算法导论(原书第3版)》选材经典、内容丰富、结构合理、逻辑清晰，对本科生的数据结构课程和研究生的算法课程都是非常实用的教材，在IT专业人员的职业生涯中，本书也是一本案头必备的参考书或工程实践手册。 第3版的主要变化： 新增了van Emde Boas树和多线程算法，并且将矩阵基础移至附录。 修订了递归式（现在称为“分治策略”）那一章的内容，更广泛地覆盖分治法。 . 移除两章很少讲授的内容：二项堆和排序网络。 修订了动态规划和贪心算法相关内容。 流网络相关材料现在基于边上的全部流。 由于关于矩阵基础和Strassen算法的材料移到了其他章，矩阵运算这一章的内容所占篇幅更小。 修改了对Knuth-Morris-Pratt字符串匹配算法的讨论。 新增100道练习和28道思考题，还更新并补充了参考文献。 |
| 目录 |
---------------------------离散数学及其应用（原书第8版）--------------------------- 出版者的话 译者序 前言 在线资源 致学生 作者简介 符号表 第1章 基础：逻辑和证明1 1.1 命题逻辑1 1.1.1 引言1 1.1.2 命题1 1.1.3 条件语句4 1.1.4 复合命题的真值表7 1.1.5 逻辑运算符的优先级8 1.1.6 逻辑运算和比特运算8 练习9 1.2 命题逻辑的应用15 1.2.1 引言15 1.2.2 语句翻译15 1.2.3 系统规范说明16 1.2.4 布尔搜索16 1.2.5 逻辑谜题17 1.2.6 逻辑电路18 练习20 1.3 命题等价式23 1.3.1 引言23 1.3.2 逻辑等价式23 1.3.3 德·摩根律的运用25 1.3.4 构造新的逻辑等价式26 1.3.5 可满足性28 1.3.6 可满足性的应用28 1.3.7 可满足性问题求解30 练习31 1.4 谓词和量词34 1.4.1 引言34 1.4.2 谓词34 1.4.3 量词37 1.4.4 有限域上的量词39 1.4.5 受限域的量词39 1.4.6 量词的优先级40 1.4.7 变量绑定40 1.4.8 涉及量词的逻辑等价式40 1.4.9 量化表达式的否定41 1.4.10 语句到逻辑表达式的翻译42 1.4.11 系统规范说明中量词的使用43 1.4.12 选自路易斯·卡罗尔的例子44 1.4.13 逻辑程序设计45 练习46 1.5 嵌套量词51 1.5.1 引言51 1.5.2 理解涉及嵌套量词的语句51 1.5.3 量词的顺序52 1.5.4 数学语句到嵌套量词语句的翻译53 1.5.5 嵌套量词到自然语言的翻译54 1.5.6 汉语语句到逻辑表达式的翻译54 1.5.7 嵌套量词的否定55 练习56 1.6 推理规则62 1.6.1 引言62 1.6.2 命题逻辑的有效论证62 1.6.3 命题逻辑的推理规则63 1.6.4 使用推理规则建立论证65 1.6.5 消解律66 1.6.6 谬误66 1.6.7 量化命题的推理规则67 1.6.8 命题和量化命题推理规则的组合使用68 练习69 1.7 证明导论72 1.7.1 引言72 1.7.2 一些专用术语72 1.7.3 理解定理是如何陈述的73 1.7.4 证明定理的方法73 1.7.5 直接证明法73 1.7.6 反证法74 1.7.7 归谬证明法76 1.7.8 证明中的错误78 1.7.9 良好的开端79 练习80 1.8 证明的方法和策略81 1.8.1 引言81 1.8.2 穷举证明法和分情形证明法81 1.8.3 存在性证明84 1.8.4 唯一性证明86 1.8.5 证明策略87 1.8.6 寻找反例89 1.8.7 证明策略实践90 1.8.8 拼接90 1.8.9 开放问题的作用92 1.8.10 其他证明方法93 练习94 关键术语和结论96 复习题97 补充练习98 计算机课题100 计算和探索101 写作课题101 第2章 基本结构：集合、函数、序列、求和与矩阵102 2.1 集合102 2.1.1 引言102 2.1.2 文氏图104 2.1.3 子集105 2.1.4 集合的大小106 2.1.5 幂集107 2.1.6 笛卡儿积107 2.1.7 使用带量词的集合符号109 2.1.8 真值集和量词109 练习109 2.2 集合运算112 2.2.1 引言112 2.2.2 集合恒等式114 2.2.3 扩展的并集和交集116 2.2.4 集合的计算机表示117 2.2.5 多重集118 练习119 2.3 函数123 2.3.1 引言123 2.3.2 一对一函数和映上函数125 2.3.3 反函数和函数合成128 2.3.4 函数的图130 2.3.5 一些重要的函数130 2.3.6 部分函数133 练习133 2.4 序列与求和138 2.4.1 引言138 2.4.2 序列138 2.4.3 递推关系139 2.4.4 特殊的整数序列141 2.4.5 求和144 练习147 2.5 集合的基数150 2.5.1 引言150 2.5.2 可数集合151 2.5.3 不可数集合153 练习155 2.6 矩阵157 2.6.1 引言157 2.6.2 矩阵算术158 2.6.3 矩阵的转置和幂159 2.6.4 0-1矩阵160 练习161 关键术语和结论164 复习题166 补充练习166 计算机课题168 计算和探索169 写作课题169 第3章 算法170 3.1 算法170 3.1.1 引言170 3.1.2 搜索算法172 3.1.3 排序174 3.1.4 字符串匹配176 3.1.5 贪婪算法177 3.1.6 停机问题179 练习180 3.2 函数的增长183 3.2.1 引言183 3.2.2 大O记号184 3.2.3 一些重要函数的大O估算187 3.2.4 函数组合的增长190 3.2.5 大Ω与大Θ记号191 练习192 3.3 算法的复杂度196 3.3.1 引言196 3.3.2 时间复杂度196 3.3.3 矩阵乘法的复杂度198 3.3.4 算法范型199 3.3.5 理解算法的复杂度201 练习203 关键术语和结论207 复习题208 补充练习209 计算机课题211 计算和探索211 写作课题212 第4章 数论和密码学213 4.1 整除性和模算术213 4.1.1 引言213 4.1.2 除法213 4.1.3 除法算法214 4.1.4 模算术215 4.1.5 模m算术217 练习218 4.2 整数表示和算法220 4.2.1 引言220 4.2.2 整数表示220 4.2.3 整数运算算法223 4.2.4 模指数运算225 练习226 4.3 素数和最大公约数229 4.3.1 引言229 4.3.2 素数229 4.3.3 试除法230 4.3.4 埃拉托斯特尼筛法231 4.3.5 关于素数的猜想和开放问题235 4.3.6 最大公约数和最小公倍数236 4.3.7 欧几里得算法238 4.3.8 gcd的线性组合表示239 练习242 4.4 求解同余方程245 4.4.1 引言245 4.4.2 线性同余方程245 4.4.3 中国剩余定理247 4.4.4 大整数的计算机算术248 4.4.5 费马小定理249 4.4.6 伪素数250 4.4.7 原根和离散对数251 练习252 4.5 同余的应用255 4.5.1 散列函数255 4.5.2 伪随机数256 4.5.3 校验码257 练习259 4.6 密码学260 4.6.1 引言260 4.6.2 古典密码学261 4.6.3 公钥密码学263 4.6.4 RSA密码系统265 4.6.5 RSA加密265 4.6.6 RSA解密266 4.6.7 用RSA作为公钥系统266 4.6.8 密码协议267 4.6.9 同态加密268 练习269 关键术语和结论271 复习题273 补充练习273 计算机课题275 计算和探索276 写作课题276 第5章 归纳与递归278 5.1 数学归纳法278 5.1.1 引言278 5.1.2 数学归纳法279 5.1.3 为什么数学归纳法是有效的280 5.1.4 选择正确的基础步骤280 5.1.5 运用数学归纳法进行证明的原则281 5.1.6 数学归纳法的优点与缺点281 5.1.7 利用数学归纳法证明的例子281 5.1.8 使用数学归纳法时犯的错误290 练习291 5.2 强归纳法与良序性296 5.2.1 引言296 5.2.2 强归纳法296 5.2.3 利用强归纳法证明的例子298 5.2.4 计算几何学中使用强归纳法300 5.2.5 利用良序性证明302 练习302 5.3 递归定义与结构归纳法306 5.3.1 引言306 5.3.2 递归地定义函数307 5.3.3 递归地定义集合与结构309 5.3.4 结构归纳法312 5.3.5 广义归纳法315 练习315 5.4 递归算法320 5.4.1 引言320 5.4.2 证明递归算法的正确性322 5.4.3 递归与迭代323 5.4.4 归并排序324 练习327 5.5 程序正确性329 5.5.1 引言329 5.5.2 程序验证329 5.5.3 推理规则330 5.5.4 条件语句330 5.5.5 循环不变量332 练习333 关键术语和结论334 复习题335 补充练习336 计算机课题340 计算和探索341 写作课题341 第6章 计数342 6.1 计数的基础342 6.1.1 引言342 6.1.2 基本的计数原则342 6.1.3 比较复杂的计数问题346 6.1.4 减法法则（两个集合的容斥原理）347 6.1.5 除法法则349 6.1.6 树图349 练习350 6.2 鸽巢原理354 6.2.1 引言354 6.2.2 广义鸽巢原理355 6.2.3 鸽巢原理的几个简单应用357 练习359 6.3 排列与组合361 6.3.1 引言361 6.3.2 排列361 6.3.3 组合362 练习365 6.4 二项式系数和恒等式367 6.4.1 二项式定理368 6.4.2 帕斯卡恒等式和三角形370 6.4.3 其他的二项式系数 恒等式371 练习372 6.5 排列与组合的推广375 6.5.1 引言375 6.5.2 有重复的排列375 6.5.3 有重复的组合375 6.5.4 具有不可区别物体的集合的排列378 6.5.5 把物体放入盒子379 练习382 6.6 生成排列和组合385 6.6.1 引言385 6.6.2 生成排列385 6.6.3 生成组合386 练习387 关键术语和结论388 复习题389 补充练习390 计算机课题393 计算和探索394 写作课题394 第7章 离散概率395 7.1 离散概率引论395 7.1.1 引言395 7.1.2 有限概率395 7.1.3 事件组合的概率398 7.1.4 概率的推理399 练习399 7.2 概率论402 7.2.1 引言402 7.2.2 概率指派402 7.2.3 事件的组合403 7.2.4 条件概率404 7.2.5 独立性405 7.2.6 伯努利试验与二项分布406 7.2.7 随机变量407 7.2.8 生日问题408 7.2.9 蒙特卡罗算法409 7.2.10 概率方法411 练习412 7.3 贝叶斯定理414 7.3.1 引言414 7.3.2 贝叶斯定理415 7.3.3 贝叶斯垃圾邮件过滤器417 练习420 7.4 期望值和方差422 7.4.1 引言422 7.4.2 期望值422 7.4.3 期望的线性性质424 7.4.4 平均情形下的计算复杂度425 7.4.5 几何分布427 7.4.6 独立随机变量428 7.4.7 方差429 7.4.8 切比雪夫不等式431 练习433 关键术语和结论435 复习题436 补充练习437 计算机课题440 计算和探索441 写作课题441 第8章 高级计数技术442 8.1 递推关系的应用442 8.1.1 引言442 8.1.2 用递推关系构造模型443 8.1.3 算法与递推关系447 练习450 8.2 求解线性递推关系453 8.2.1 引言453 8.2.2 求解常系数线性齐次递推关系454 8.2.3 求解常系数线性非齐次递推关系458 练习460 8.3 分治算法和递推关系463 8.3.1 引言463 8.3.2 分治递推关系463 练习469 8.4 生成函数471 8.4.1 引言471 8.4.2 关于幂级数的有用事实471 8.4.3 计数问题与生成函数474 8.4.4 使用生成函数求解递推关系477 8.4.5 使用生成函数证明恒等式478 练习479 8.5 容斥484 8.5.1 引言484 8.5.2 容斥原理484 练习487 8.6 容斥原理的应用488 8.6.1 引言488 8.6.2 容斥原理的另一种形式488 8.6.3 埃拉托色尼筛489 8.6.4 映上函数的个数490 8.6.5 错位排列490 练习492 关键术语和结论493 复习题494 补充练习495 计算机课题497 计算和探索498 写作课题498 第9章 关系500 9.1 关系及其性质500 9.1.1 引言500 9.1.2 函数作为关系501 9.1.3 集合的关系501 9.1.4 关系的性质502 9.1.5 关系的组合504 练习506 9.2 n元关系及其应用510 9.2.1 引言510 9.2.2 n元关系510 9.2.3 数据库和关系511 9.2.4 n元关系的运算512 9.2.5 SQL514 9.2.6 数据挖掘中的关联规则514 练习516 9.3 关系的表示518 9.3.1 引言518 9.3.2 用矩阵表示关系518 9.3.3 用图表示关系521 练习522 9.4 关系的闭包524 9.4.1 引言524 9.4.2 不同类型的闭包524 9.4.3 有向图中的路径525 9.4.4 传递闭包526 9.4.5 沃舍尔算法529 练习531 9.5 等价关系533 9.5.1 引言533 9.5.2 等价关系533 9.5.3 等价类534 9.5.4 等价类与划分536 练习538 9.6 偏序542 9.6.1 引言542 9.6.2 字典顺序544 9.6.3 哈塞图545 9.6.4 极大元与极小元546 9.6.5 格548 9.6.6 拓扑排序550 练习551 关键术语和结论556 复习题557 补充练习558 计算机课题561 计算和探索562 写作课题562 第10章 图563 10.1 图和图模型563 10.1.1 图模型565 练习570 10.2 图的术语和几种特殊的图573 10.2.1 引言573 10.2.2 基本术语573 10.2.3 一些特殊的简单图575 10.2.4 二分图576 10.2.5 二分图和匹配577 10.2.6 特殊类型图的一些应用580 10.2.7 从旧图构造新图582 练习584 10.3 图的表示和图的同构587 10.3.1 引言587 10.3.2 图的表示588 10.3.3 邻接矩阵588 10.3.4 关联矩阵590 10.3.5 图的同构590 10.3.6 判定两个简单图是否同构591 练习593 10.4 连通性598 10.4.1 引言598 10.4.2 通路598 10.4.3 无向图的连通性600 10.4.4 图是如何连通的601 10.4.5 有向图的连通性603 10.4.6 通路与同构604 10.4.7 计算顶点之间的通路数605 练习606 10.5 欧拉通路与哈密顿通路611 10.5.1 引言611 10.5.2 欧拉通路与欧拉回路611 10.5.3 哈密顿通路与哈密顿回路615 10.5.4 哈密顿回路的应用618 练习619 10.6 最短通路问题623 10.6.1 引言623 10.6.2 最短通路算法625 10.6.3 旅行商问题629 练习630 10.7 平面图633 10.7.1 引言633 10.7.2 欧拉公式634 10.7.3 库拉图斯基定理637 练习638 10.8 图着色640 10.8.1 引言640 10.8.2 图着色的应用644 练习645 关键术语和结论648 复习题650 补充练习651 计算机课题656 计算和探索656 写作课题657 第11章 树658 11.1 树的概述658 11.1.1 有根树659 11.1.2 树作为模型662 11.1.3 树的性质663 练习666 11.2 树的应用668 11.2.1 引言668 11.2.2 二叉搜索树668 11.2.3 决策树671 11.2.4 前缀码672 11.2.5 博弈树674 练习678 11.3 树的遍历681 11.3.1 引言681 11.3.2 通用地址系统681 11.3.3 遍历算法682 11.3.4 中缀、前缀和后缀记法688 练习690 11.4 生成树693 11.4.1 引言693 11.4.2 深度优先搜索694 11.4.3 宽度优先搜索696 11.4.4 回溯的应用698 11.4.5 有向图中的深度优先搜索700 练习701 11.5 最小生成树704 11.5.1 引言704 11.5.2 最小生成树算法704 练习707 关键术语和结论709 复习题710 补充练习711 计算机课题714 计算和探索714 写作课题715 第12章 布尔代数716 12.1 布尔函数716 12.1.1 引言716 12.1.2 布尔表达式和布尔函数717 12.1.3 布尔代数恒等式718 12.1.4 对偶性720 12.1.5 布尔代数的抽象定义720 练习721 12.2 布尔函数的表示722 12.2.1 积之和展开式723 12.2.2 函数完备性724 练习724 12.3 逻辑门电路725 12.3.1 引言725 12.3.2 门的组合726 12.3.3 电路的例子726 12.3.4 加法器728 练习729 12.4 电路的极小化731 12.4.1 引言731 12.4.2 卡诺图732 12.4.3 无须在意的条件737 12.4.4 奎因-莫可拉斯基方法737 练习741 关键术语和结论743 复习题744 补充练习744 计算机课题746 计算和探索746 写作课题747 第13章 计算模型748 13.1 语言和文法748 13.1.1 引言748 13.1.2 短语结构文法749 13.1.3 短语结构文法的类型751 13.1.4 派生树752 13.1.5 巴克斯-诺尔范式754 练习755 13.2 带输出的有限状态机758 13.2.1 引言758 13.2.2 带输出的有限状态机759 练习762 13.3 不带输出的有限状态机764 13.3.1 引言764 13.3.2 串的集合764 13.3.3 有限状态自动机765 13.3.4 有限状态机的语言识别766 13.3.5 非确定性的有限状态自动机771 练习773 13.4 语言的识别777 13.4.1 引言777 13.4.2 克莱因定理778 13.4.3 正则集合和正则文法781 13.4.4 一个不能由有限状态自动机识别的集合783 13.4.5 一些更强大的机器783 练习784 13.5 图灵机786 13.5.1 引言786 13.5.2 图灵机的定义787 13.5.3 用图灵机识别集合789 13.5.4 用图灵机计算函数790 13.5.5 不同类型的图灵机790 13.5.6 丘奇-图灵论题791 13.5.7 计算复杂度、可计算性和可判定性791 练习794 关键术语和结论796 复习题797 补充练习798 计算机课题800 计算和探索800 写作课题800 附录A 实数和正整数的公理802 附录B 指数与对数函数807 附录C 伪代码809 推荐读物813 参考文献817 奇数编号练习答案 请访问华章网站www.hzbook.com下载。 ---------------------------算法导论(原书第3版)--------------------------- 《算法导论(原书第3版)》 出版者的话 译者序 前言 第一部分 基础知识 第1章 算法在计算中的作用3 1.1 算法3 1.2 作为一种技术的算法6 思考题8 本章注记8 第2章 算法基础9 2.1 插入排序9 2.2 分析算法13 2.3 设计算法16 2.3.1 分治法16 2.3.2 分析分治算法20 思考题22 本章注记24 第3章 函数的增长25 3.1 渐近记号25 3.2 标准记号与常用函数30 思考题35 本章注记36 第4章 分治策略37 4.1 最大子数组问题38 4.2 矩阵乘法的Strassen算法43 4.3 用代入法求解递归式47 4.4 用递归树方法求解递归式50 4.5 用主方法求解递归式53 4.6 证明主定理55 4.6.1 对b的幂证明主定理56 4.6.2 向下取整和向上取整58 思考题60 本章注记62 第5章 概率分析和随机算法65 5.1 雇用问题65 5.2 指示器随机变量67 5.3 随机算法69 5.4 概率分析和指示器随机变量的进一步使用73 5.4.1 生日悖论73 5.4.2 球与箱子75 5.4.3 特征序列76 5.4.4 在线雇用问题78 思考题79 本章注记80 第二部分 排序和顺序统计量 第6章 堆排序84 6.1 堆84 6.2 维护堆的性质85 6.3 建堆87 6.4 堆排序算法89 6.5 优先队列90 思考题93 本章注记94 第7章 快速排序95 7.1 快速排序的描述95 7.2 快速排序的性能97 7.3 快速排序的随机化版本100 7.4 快速排序分析101 7.4.1 最坏情况分析101 7.4.2 期望运行时间101 思考题103 本章注记106 第8章 线性时间排序107 8.1 排序算法的下界107 8.2 计数排序108 8.3 基数排序110 8.4 桶排序112 思考题114 本章注记118 第9章 中位数和顺序统计量119 9.1 最小值和最大值119 9.2 期望为线性时间的选择算法120 9.3 最坏情况为线性时间的选择算法123 思考题125 本章注记126 第三部分 数据结构 第10章 基本数据结构129 10.1 栈和队列129 10.2 链表131 10.3 指针和对象的实现134 10.4 有根树的表示137 思考题139 本章注记141 第11章 散列表142 11.1 直接寻址表142 11.2 散列表143 11.3 散列函数147 11.3.1 除法散列法147 11.3.2 乘法散列法148 11.3.3 全域散列法148 11.4 开放寻址法151 11.5 完全散列156 思考题158 本章注记160 第12章 二叉搜索树161 12.1 什么是二叉搜索树161 12.2 查询二叉搜索树163 12.3 插入和删除165 12.4 随机构建二叉搜索树169 思考题171 本章注记173 第13章 红黑树174 13.1 红黑树的性质174 13.2 旋转176 13.3 插入178 13.4 删除183 思考题187 本章注记191 第14章 数据结构的扩张193 14.1 动态顺序统计193 14.2 如何扩张数据结构196 14.3 区间树198 思考题202 本章注记202 第四部分 高级设计和分析技术 第15章 动态规划204 15.1 钢条切割204 15.2 矩阵链乘法210 15.3 动态规划原理215 15.4 最长公共子序列222 15.5 最优二叉搜索树226 思考题231 本章注记236 第16章 贪心算法237 16.1 活动选择问题237 16.2 贪心算法原理242 16.3 赫夫曼编码245 16.4 拟阵和贪心算法250 16.5 用拟阵求解任务调度问题253 思考题255 本章注记257 第17章 摊还分析258 17.1 聚合分析258 17.2 核算法261 17.3 势能法262 17.4 动态表264 17.4.1 表扩张265 17.4.2 表扩张和收缩267 思考题270 本章注记273 第五部分 高级数据结构 第18章 B树277 18.1 B树的定义279 18.2 B树上的基本操作281 18.3 从B树中删除关键字286 思考题288 本章注记289 第19章 斐波那契堆290 19.1 斐波那契堆结构291 19.2 可合并堆操作292 19.3 关键字减值和删除一个结点298 19.4 最大度数的界300 思考题302 本章注记305 第20章 van Emde Boas树306 20.1 基本方法306 20.2 递归结构308 20.2.1 原型van Emde Boas结构310 20.2.2 原型van Emde Boas结构上的操作311 20.3 van Emde Boas树及其操作314 20.3.1 van Emde Boas树315 20.3.2 van Emde Boas树的操作317 思考题322 本章注记323 第21章 用于不相交集合的数据结构324 21.1 不相交集合的操作324 21.2 不相交集合的链表表示326 21.3 不相交集合森林328 *21.4 带路径压缩的按秩合并的分析331 思考题336 本章注记337 第六部分 图算法 第22章 基本的图算法341 22.1 图的表示341 22.2 广度优先搜索343 22.3 深度优先搜索349 22.4 拓扑排序355 22.5 强连通分量357 思考题360 本章注记361 第23章 最小生成树362 23.1 最小生成树的形成362 23.2 Kruskal算法和Prim算法366 思考题370 本章注记373 第24章 单源最短路径374 24.1 BellmanFord算法379 24.2 有向无环图中的单源最短路径问题381 24.3 Dijkstra算法383 24.4 差分约束和最短路径387 24.5 最短路径性质的证明391 思考题395 本章注记398 第25章 所有结点对的最短路径问题399 25.1 最短路径和矩阵乘法400 25.2 FloydWarshall算法404 25.3 用于稀疏图的Johnson算法409 思考题412 本章注记412 第26章 最大流414 26.1 流网络414 26.2 FordFulkerson方法418 26.3 最大二分匹配428 26.4 推送重贴标签算法431 26.5 前置重贴标签算法438 思考题446 本章注记449 第七部分 算法问题选编 第27章 多线程算法453 27.1 动态多线程基础454 27.2 多线程矩阵乘法465 27.3 多线程归并排序468 思考题472 本章注记476 第28章 矩阵运算478 28.1 求解线性方程组478 28.2 矩阵求逆486 28.3 对称正定矩阵和最小二乘逼近489 思考题493 本章注记494 第29章 线性规划495 29.1 标准型和松弛型499 29.2 将问题表达为线性规划504 29.3 单纯形算法507 29.4 对偶性516 29.5 初始基本可行解520 思考题525 本章注记526 第30章 多项式与快速傅里叶变换527 30.1 多项式的表示528 30.2 DFT与FFT531 30.3 高效FFT实现536 思考题539 本章注记541 第31章 数论算法543 31.1 基础数论概念543 31.2 最大公约数547 31.3 模运算550 31.4 求解模线性方程554 31.5 中国余数定理556 31.6 元素的幂558 31.7 RSA公钥加密系统561 31.8 素数的测试565 31.9 整数的因子分解571 思考题574 本章注记576 第32章 字符串匹配577 32.1 朴素字符串匹配算法578 32.2 RabinKarp算法580 32.3 利用有限自动机进行字符串匹配583 32.4 KnuthMorrisPratt算法588 思考题594 本章注记594 第33章 计算几何学595 33.1 线段的性质595 33.2 确定任意一对线段是否相交599 33.3 寻找凸包604 33.4 寻找最近点对610 思考题613 本章注记615 第34章 NP完全性616 34.1 多项式时间619 34.2 多项式时间的验证623 34.3 NP完全性与可归约性626 34.4 NP完全性的证明633 34.5 NP完全问题638 34.5.1 团问题638 34.5.2 顶点覆盖问题640 34.5.3 哈密顿回路问题641 34.5.4 旅行商问题644 34.5.5 子集和问题645 思考题647 本章注记649 第35章 近似算法651 35.1 顶点覆盖问题652 35.2 旅行商问题654 35.2.1 满足三角不等式的旅行商问题654 35.2.2 一般旅行商问题656 35.3 集合覆盖问题658 35.4 随机化和线性规划661 35.5 子集和问题663 思考题667 本章注记669 第八部分 附录：数学基础知识 附录A 求和672 A.1 求和公式及其性质672 A.2 确定求和时间的界674 思考题678 附录注记678 附录B 集合等离散数学内容679 B.1 集合679 B.2 关系682 B.3 函数683 B.4 图685 B.5 树687 B.5.1 自由树688 B.5.2 有根树和有序树689 B.5.3 二叉树和位置树690 思考题691 附录注记692 附录C 计数与概率693 C.1 计数693 C.2 概率696 C.3 离散随机变量700 C.4 几何分布与二项分布702 *C.5 二项分布的尾部705 思考题708 附录注记708 附录D 矩阵709 D.1 矩阵与矩阵运算709 D.2 矩阵基本性质712 思考题714 附录注记715 参考文献716 索引732 |
有问题微信扫码联系
推荐
- ※[套装书]嵌入式计算与机电一体化技术：基于PIC32微控制器+FPGA应用开发和仿真（2册）
- ※[套装书]嵌入式计算与机电一体化技术：基于PIC32微控制器+RT-Thread内核实现与应用开发实战指南：基于STM32（2册）
- ※[套装书]Python深度学习：基于PyTorch+Python大规模机器学习（2册）
- ※[套装书]聊天机器人：入门、进阶与实战+神经网络与深度学习实战：Python+Keras+TensorFlow（2册）
- ※[套装书]离散数学及其应用（原书第8版）+深入理解计算机系统（原书第3版）（2册）
- ※[套装书]离散数学及其应用（原书第8版）+算法导论(原书第3版)（2册）
- ※[套装书]智能物联网的存储器设计与实现+从M2M到物联网：架构、技术及应用（2册）
- ※[套装书]嵌入式计算与机电一体化技术：基于PIC32微控制器+FFmpeg从入门到精通（2册）
- ※[套装书]嵌入式计算与机电一体化技术：基于PIC32微控制器+密码技术与物联网安全：mbedtls开发实战（2册）
- ※[套装书]嵌入式计算与机电一体化技术：基于PIC32微控制器+FreeRTOS内核实现与应用开发实战指南：基于STM32（2册）
- ※区块链与实体产业 重新定义数字经济