算法导论 第2版PDF电子书下载
- 电子书积分:21 积分如何计算积分?
- 作 者:(美)科曼(Cormen,T.H.)等著;潘金贵等译
- 出 版 社:北京:机械工业出版社
- 出版年份:2006
- ISBN:7111187776
- 页数:754 页
第一部分 基础知识 1
引言 1
第1章 算法在计算中的作用 3
1.1 算法 3
1.2 作为一种技术的算法 6
第2章 算法入门 9
2.1 插入排序 9
2.2 算法分析 12
2.3 算法设计 16
2.3.1 分治法 16
2.3.2 分治法分析 20
第3章 函数的增长 26
3.1 渐近记号 26
3.2 标准记号和常用函数 31
第4章 递归式 38
4.1 代换法 38
4.2 递归树方法 40
4.3 主方法 43
4.4 主定理的证明 45
4.4.1 取正合幂时的证明 45
4.4.2 上取整函数和下取整函数 48
第5章 概率分析和随机算法 54
5.1 雇用问题 54
5.2 指示器随机变量 56
5.3 随机算法 58
5.4 概率分析和指示器随机变量的进一步使用 62
5.4.1 生日悖论 62
5.4.2 球与盒子 64
5.4.3 序列 64
5.4.4 在线雇用问题 66
第二部分 排序和顺序统计学 71
引言 71
第6章 堆排序 73
6.1 堆 73
6.2 保持堆的性质 74
6.3 建堆 76
6.4 堆排序算法 78
6.5 优先级队列 80
第7章 快速排序 85
7.1 快速排序的描述 85
7.2 快速排序的性能 88
7.3 快速排序的随机化版本 90
7.4 快速排序分析 91
7.4.1 最坏情况分析 91
7.4.2 期望的运行时间 92
第8章 线性时间排序 97
8.1 排序算法时间的下界 97
8.2 计数排序 98
8.3 基数排序 100
8.4 桶排序 102
第9章 中位数和顺序统计学 108
9.1 最小值和最大值 108
9.2 以期望线性时间做选择 109
9.3 最坏情况线性时间的选择 112
第三部分 数据结构 117
引言 117
第10章 基本数据结构 119
10.1 栈和队列 119
10.2 链表 121
10.3 指针和对象的实现 124
10.4 有根树的表示 127
第11章 散列表 132
11.1 直接寻址表 132
11.2 散列表 133
11.3 散列函数 137
11.3.1 除法散列法 138
11.3.2 乘法散列法 138
11.3.3 全域散列 139
11.4 开放寻址法 142
11.5 完全散列 146
第12章 二叉查找树 151
12.1 二叉查找树 151
12.2 查询二叉查找树 153
12.3 插入和删除 155
12.4 随机构造的二叉查找树 158
第13章 红黑树 163
13.1 红黑树的性质 163
13.2 旋转 165
13.3 插入 167
13.4 删除 172
第14章 数据结构的扩张 181
14.1 动态顺序统计 181
14.2 如何扩张数据结构 184
14.3 区间树 186
第四部分 高级设计和分析技术 191
导论 191
第15章 动态规划 192
15.1 装配线调度 192
15.2 矩阵链乘法 197
15.3 动态规划基础 202
15.4 最长公共子序列 208
15.5 最优二叉查找树 212
第16章 贪心算法 222
16.1 活动选择问题 222
16.2 贪心策略的基本内容 228
16.3 赫夫曼编码 231
16.4 贪心法的理论基础 236
16.5 一个任务调度问题 239
第17章 平摊分析 244
17.1 聚集分析 244
17.2 记账方法 247
17.3 势能方法 249
17.4 动态表 251
17.4.1 表扩张 251
17.4.2 表扩张和收缩 253
第五部分 高级数据结构 261
概述 261
第18章 B树 263
18.1 B树的定义 265
18.2 对B树的基本操作 267
18.3 从B树中删除关键字 272
第19章 二项堆 277
19.1 二项树与二项堆 278
19.1.1 二项树 278
19.1.2 二项堆 279
19.2 对二项堆的操作 281
第20章 斐波那契堆 291
20.1 斐波那契堆的结构 291
20.2 可合并堆的操作 293
20.3 减小一个关键字与删除一个结点 299
20.4 最大度数的界 302
第21章 用于不相交集合的数据结构 305
21.1 不相交集合上的操作 305
21.2 不相交集合的链表表示 307
21.3 不相交集合森林 310
21.4 带路径压缩的按秩合并的分析 312
第六部分 图算法 321
引言 321
第22章 图的基本算法 322
22.1 图的表示 322
22.2 广度优先搜索 324
22.3 深度优先搜索 330
22.4 拓扑排序 336
22.5 强连通分支 338
第23章 最小生成树 344
23.1 最小生成树的形成 345
23.2 Kruskal算法和Prim算法 348
第24章 单源最短路径 357
24.1 Bellman-Ford算法 362
24.2 有向无回路图中的单源最短路径 364
24.3 Dijkstra算法 366
24.4 差分约束与最短路径 370
24.5 最短路径性质的证明 373
第25章 每对顶点间的最短路径 381
25.1 最短路径与矩阵乘法 382
25.2 Floyd-Warshall算法 386
25.3 稀疏图上的Johnson算法 391
第26章 最大流 396
26.1 流网络 396
26.2 Ford-Fulkerson方法 400
26.3 最大二分匹配 408
26.4 压入与重标记算法 411
26.5 重标记与前移算法 419
第七部分 算法研究问题选编 431
引言 431
第27章 排序网络 433
27.1 比较网络 433
27.2 0-1原理 436
27.3 双调排序网络 438
27.4 合并网络 440
27.5 排序网络 442
第28章 矩阵运算 446
28.1 矩阵的性质 446
28.2 矩阵乘法的Strassen算法 451
28.3 求解线性方程组 455
28.4 矩阵求逆 464
28.5 对称正定矩阵与最小二乘逼近 467
第29章 线性规划 473
29.1 标准型和松弛型 477
29.2 将问题表达为线性规划 482
29.3 单纯形算法 485
29.4 对偶性 495
29.5 初始基本可行解 498
第30章 多项式与快速傅里叶变换 506
30.1 多项式的表示 507
30.2 DFT与FFT 511
30.3 有效的FFT实现 516
第31章 有关数论的算法 522
31.1 初等数论概念 522
31.2 最大公约数 526
31.3 模运算 529
31.4 求解模线性方程 533
31.5 中国余数定理 535
31.6 元素的幂 538
31.7 RSA公钥加密系统 540
31.8 素数的测试 544
31.9 整数的因子分解 550
第32章 字符串匹配 557
32.1 朴素的字符串匹配算法 558
32.2 Rabin-Karp算法 560
32.3 利用有限自动机进行字符串匹配 563
32.4 Knuth-Morris-Pratt算法 568
第33章 计算几何学 575
33.1 线段的性质 575
33.2 确定任意一对线段是否相交 580
33.3 寻找凸包 584
33.4 寻找最近点对 591
第34章 NP完全性 597
34.1 多项式时间 600
34.2 多项式时间的验证 605
34.3 NP完全性与可归约性 608
34.4 NP完全性的证明 615
34.5 NP完全问题 620
34.5.1 团问题 620
34.5.2 顶点覆盖问题 622
34.5.3 哈密顿回路问题 623
34.5.4 旅行商问题 626
34.5.5 子集和问题 627
第35章 近似算法 633
35.1 顶点覆盖问题 634
35.2 旅行商问题 636
35.2.1 满足三角不等式的旅行商问题 636
35.2.2 一般旅行商问题 638
35.3 集合覆盖问题 640
35.4 随机化和线性规划 643
35.5 子集和问题 646
第八部分 附录:数学基础知识 653
引言 653
A 求和 654
A.1 求和公式及其性质 654
A.2 确定求和时间的界 656
B 集合等离散数学结构 661
B.1 集合 661
B.2 关系 664
B.3 函数 665
B.4 图 667
B.5 树 670
B.5.1 自由树 670
B.5.2 有根树和有序树 671
B.5.3 二叉树与位置树 672
C 计数和概率 676
C.1 计数 676
C.2 概率 679
C.3 离散随机变量 683
C.4 几何分布与二项分布 686
C.5 二项分布的尾 689
参考文献 694
索引 711
- 《物联网导论》张翼英主编 2020
- 《材料导论》张会主编 2019
- 《化工传递过程导论 第2版》阎建民,刘辉 2020
- 《计算机视觉系统设计及显著性算法研究》徐海波著 2019
- 《大数据导论》林子雨编著 2020
- 《全局光照算法技术》(美)菲利普·特瑞(Philip Dutre)等著 2019
- 《RNA折叠结构预测算法与计算复杂性》刘振栋著 2019
- 《跨文化交际学基础导论》林大津,尤泽顺导读 2007
- 《现代环境主义导论》(英)戴维·佩珀(David Pepper)著 2020
- 《ROS机器人编程与SLAM算法解析指南》陶满礼 2020
- 《断陷湖盆比较沉积学与油气储层》赵永胜等著 1996
- 《SQL与关系数据库理论》(美)戴特(C.J.Date) 2019
- 《魔法销售台词》(美)埃尔默·惠勒著 2019
- 《看漫画学钢琴 技巧 3》高宁译;(日)川崎美雪 2019
- 《优势谈判 15周年经典版》(美)罗杰·道森 2018
- 《社会学与人类生活 社会问题解析 第11版》(美)James M. Henslin(詹姆斯·M. 汉斯林) 2019
- 《海明威书信集:1917-1961 下》(美)海明威(Ernest Hemingway)著;潘小松译 2019
- 《迁徙 默温自选诗集 上》(美)W.S.默温著;伽禾译 2020
- 《上帝的孤独者 下 托马斯·沃尔夫短篇小说集》(美)托马斯·沃尔夫著;刘积源译 2017
- 《巴黎永远没个完》(美)海明威著 2017
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《北京生态环境保护》《北京环境保护丛书》编委会编著 2018
- 《高等教育双机械基础课程系列教材 高等学校教材 机械设计课程设计手册 第5版》吴宗泽,罗圣国,高志,李威 2018
- 《指向核心素养 北京十一学校名师教学设计 英语 九年级 上 配人教版》周志英总主编 2019
- 《高等院校旅游专业系列教材 旅游企业岗位培训系列教材 新编北京导游英语》杨昆,鄢莉,谭明华 2019
- 《中国十大出版家》王震,贺越明著 1991
- 《近代民营出版机构的英语函授教育 以“商务、中华、开明”函授学校为个案 1915年-1946年版》丁伟 2017
- 《新工业时代 世界级工业家张毓强和他的“新石头记”》秦朔 2019
- 《智能制造高技能人才培养规划丛书 ABB工业机器人虚拟仿真教程》(中国)工控帮教研组 2019
- 《AutoCAD机械设计实例精解 2019中文版》北京兆迪科技有限公司编著 2019