算法之道PDF电子书下载
- 电子书积分:11 积分如何计算积分?
- 作 者:邹恒明编著
- 出 版 社:北京:机械工业出版社
- 出版年份:2010
- ISBN:9787111294948
- 页数:292 页
第一篇 算法基础篇第1章 从无有到无穷 2
1.1 意念与现实 3
1.2 什么是算法 4
1.3 算法的表示 6
1.4 算法之魂 7
1.5 如何比较速度 8
1.6 算法与计算机的关系 9
1.7 算法的范畴 10
1.8 为什么学习算法 10
思考题 11
第2章 计数与渐近 12
2.1 算法的分析 12
2.1.1 正确性分析 13
2.1.2 时空效率分析 14
2.1.3 时空特性分析 14
2.2 计数:算法分析的核心 14
2.3 算法设计 15
2.4 算法效率表示 16
2.5 渐近分析 17
2.6 O、Ω、Θ表示 18
2.7 最好、最坏、平均 19
2.8 O、Ω、Θ的另一类定义 21
2.9 O、Ω、Θ的性质 22
2.10 要更快的计算机还是要更快的算法 22
思考题 23
第3章 分治与递归 25
3.1 分而治之为上策 26
3.2 分治策略 28
3.3 递归表达式求解 29
3.3.1 递归树法 29
3.3.2 替换解法 30
3.3.3 大师解法 32
3.4 分治策略举例1:乘方运算 35
3.5 生命不能承受之重:矩阵乘法 36
3.6 魔鬼序列:斐波那契序列 38
3.7 VLSI布线 41
3.8 多项式乘法 43
3.9 分治就在潜意识深处 43
思考题 43
第二篇 算法设计篇第4章 动态规划思想 46
4.1 什么是动态规划 47
4.2 流水装配线问题 48
4.3 最长公共子序列 52
4.3.1 第一种解法:蛮力策略 52
4.3.2 第二种解法:动态规划 53
4.4 最长公共子序列变种 55
4.5 记忆递归法 55
4.6 空间效率改善 56
4.7 最优二叉搜索树 56
4.7.1 递归解法 59
4.7.2 计算最优答案 59
4.8 最优子结构与重叠子问题 62
4.8.1 最优子结构 62
4.8.2 重叠子问题 63
4.9 动态规划与静态规划的关系 63
4.10 动态规划与静态规划的相互转换 64
思考题 65
第5章 贪婪选择思想 67
5.1 仅有动态规划是不够的 67
5.2 什么是贪婪 68
5.3 背包问题 68
5.4 贪婪选择属性 71
5.5 教室规划问题 72
5.6 最小生成树 76
5.6.1 Kruskal算法的正确性 79
5.6.2 Kruskal算法的时间分析 80
5.7 Prim算法 80
5.8 霍夫曼树和霍夫曼编码 83
5.8.1 霍夫曼树 85
5.8.2 霍夫曼编码 86
5.8.3 霍夫曼编码的无前缀编码性质 87
5.9 贪婪选择属性 88
5.10 标准分治、动态规划和贪婪选择的比较 89
思考题 90
第6章 随机化思想 92
6.1 为什么要随机化 93
6.2 随机的平方 94
6.3 什么是随机化算法 95
6.4 拉斯维加斯算法 96
6.5 蒙特卡罗算法 97
6.6 素性测试 97
6.7 矩阵乘积验证器 100
6.8 随机化最小生成树算法 102
6.8.1 Karger-Klein-Tarjan算法 103
6.8.2 节点降低算法 103
6.8.3 线性时间最小生成树算法 104
6.8.4 线性时间最小生成树算法的时间成本分析 104
6.9 随机数的生成 105
6.10 随机化算法的应用 105
思考题 106
第三篇 算法分析篇第7章 概率分析 108
7.1 一切都在概率中 109
7.2 什么是概率分析 109
7.3 梦幻情人的代价 110
7.3.1 直接分析 112
7.3.2 最坏情况分析 113
7.3.3 最好情况分析 113
7.3.4 平均情况分析 113
7.3.5 平均情况下成本的概率分析 113
7.4 概率分析结果的有效性 114
7.5 正确概率分析的保障 115
7.6 梦幻情人的概率 115
7.7 随机排列问题 117
7.8 南柯一梦:从无穷到无有 119
7.9 概率分析的其他应用 120
思考题 121
第8章 摊销分析 122
8.1 什么是摊销分析 123
8.2 摊销分析与数据结构 124
8.3 摊销分析的几种方法 124
8.4 聚类分析 125
8.4.1 栈操作的聚类分析 125
8.4.2 二进制计数器的聚类分析 126
8.5 会计分析 128
8.6 势能分析 130
8.6.1 栈操作的势能分析 130
8.6.2 二进制计数器的势能分析 131
8.7 摊销分析应用:表格扩展的代价 131
8.7.1 动态表插入操作的聚类分析 134
8.7.2 动态表插入操作的会计分析 134
8.7.3 动态表插入操作的势能分析 136
8.8 运气不好就摊销 137
思考题 138
第9章 竞争分析 139
9.1 什么是竞争分析 139
9.2 在线算法和离线算法 141
9.3 竞争力 142
9.4 健忘对手和优良对手 142
9.5 线性表更新问题 143
9.6 前置移动算法的竞争分析 145
9.7 聚类问题 147
9.7.1 聚类问题的次优解算法 148
9.7.2 CLUSTERING-ALGORITHM算法的竞争分析 148
9.8 竞争分析与普通算法分析 149
思考题 149
第四篇 经典算法篇第10章 排序和次序 152
10.1 排序无处不在 152
10.2 插入排序 153
10.2.1 插入排序的效率分析 154
10.2.2 折半插入排序 155
10.3 归并排序 156
10.4 快速排序 158
10.4.1 快速排序的过程 158
10.4.2 快速排序的时间复杂性分析 159
10.4.3 最坏情况分析 160
10.4.4 最好情况分析 160
10.4.5 平均情况分析 161
10.5 随机化快速排序 162
10.6 排序的下限 164
10.7 线性排序 165
10.8 计数排序 166
10.9 基数排序 168
10.9.1 基数排序的正确性 169
10.9.2 基数排序的时间效率分析 170
10.10 桶排序 171
10.10.1 桶排序的定义 172
10.10.2 桶排序的正确性 173
10.10.3 桶排序的时间复杂性分析 173
10.11 次序选择 175
10.12 快速次序选择算法 176
10.13 随机快速次序选择算法 178
10.14 最坏情况下的线性选择算法 179
10.14.1 杠杆点好坏分析 180
10.14.2 算法的时间复杂性分析 181
思考题 181
第11章 搜索与哈希 183
11.1 搜索问题 184
11.2 顺序搜索 184
11.3 折半搜索 185
11.4 常数搜索 186
11.5 哈希搜索 187
11.6 哈希函数选择 189
11.6.1 直接哈希 189
11.6.2 除法(模除法)哈希 190
11.6.3 乘法哈希 191
11.6.4 乘法哈希的赌徒原理 192
11.6.5 乘方取中法 193
11.7 哈希算法的碰撞问题 193
11.7.1 开放寻址哈希 193
11.7.2 开放寻址哈希的时间成本 194
11.7.3 开放寻址下成功搜索的时间成本 195
11.7.4 封闭寻址哈希 196
11.7.5 探寻序列的设计 197
11.7.6 封闭寻址哈希的效率分析 199
11.7.7 搜索不成功的时间成本 199
11.7.8 成功搜索的效率分析 201
11.8 哈希表元素删除 201
11.9 随机化哈希 202
11.10 全域哈希 203
11.11 全域哈希构造 204
11.12 完美哈希 206
思考题 208
第12章 最短路径 211
12.1 剑指罗马 211
12.2 最短路径问题 213
12.3 单源单点最短路径问题 215
12.3.1 深度优先搜索与广度优先搜索 215
12.3.2 深度优先解法 217
12.4 单源多点最短路径问题 218
12.4.1 最短路径的性质 219
12.4.2 Dijkstra最短路径算法 220
12.4.3 Dijkstra算法举例 221
12.4.4 Dijkstra算法与洪水泛滥 222
12.4.5 Dijkstra算法的正确性 223
12.4.6 Dijkstra算法的时间复杂性 224
12.5 Bellman-Ford算法 226
12.5.1 负权重的应对方式 227
12.5.2 Bellman-Ford算法的正确性 230
12.5.3 负循环检查问题 231
12.5.4 Bellman-Ford算法的时间复杂性 231
12.6 多源多点最短路径问题 232
12.6.1 多源多点最短路径问题解决思路 232
12.6.2 直接动态规划解法 233
12.6.3 矩阵乘法解法 234
12.6.4 Floyd-Warshall算法 235
12.6.5 Johnson算法 236
12.6.6 Johnson等效变换 237
12.6.7 差限问题解决 238
12.7 天意难违 240
思考题 240
第五篇 难解与无解篇第13章 可解与不可解 244
13.1 我们战无不胜吗 245
13.2 易解与难解 245
13.3 决策问题和优化问题 246
13.4 决策问题 247
13.5 P类问题 247
13.6 NP类问题 248
13.7 (确定性)图灵机 249
13.8 非确定性图灵机 249
13.9 非确定性算法 250
13.10 回到NP类问题 251
13.11 P和NP 252
13.12 搜索问题、决策问题和优化问题 253
13.13 有没有解和是否可决定 253
思考题 254
第14章 NP完全问题 256
14.1 玉龙雪山下的审判 256
14.2 NP完全问题的定义 257
14.3 NP完全的重要性 258
14.4 多项式时间规约 259
14.5 如何证明一个问题S是NP完全 259
14.6 第1个NP完全问题的证明 260
14.7 库克定理 260
14.8 3-SAT问题 263
14.9 证明NP难的技巧 264
14.10 整数规划 265
14.11 独立集问题 266
14.12 汉密尔顿回路问题 268
14.13 讨论:弱NP完全、强NP完全和中NP完全 271
思考题 272
第15章 无解与近似 273
15.1 难解问题 274
15.2 不可决定问题 274
15.3 程序终结的判断 275
15.4 难解之题的求解 276
15.5 智能穷举、近似算法和本地搜索 277
15.6 智能穷举之回溯策略 279
15.7 智能穷举之分支限界 280
15.8 贪婪近似策略 280
15.9 启发式搜索策略 281
15.10 模拟淬火算法 282
15.10.1 模拟淬火算法的思想 284
15.10.2 模拟淬火算法的基本循环 284
15.10.3 淬火算法描述 284
思考题 286
结语 算法之道 288
附录 算法随想 290
- 《计算机视觉系统设计及显著性算法研究》徐海波著 2019
- 《全局光照算法技术》(美)菲利普·特瑞(Philip Dutre)等著 2019
- 《RNA折叠结构预测算法与计算复杂性》刘振栋著 2019
- 《ROS机器人编程与SLAM算法解析指南》陶满礼 2020
- 《图解数据结构与算法》汪建 2020
- 《信息融合中估计算法的性能评估》毛艳慧著 2019
- 《基于群体智能优化算法的文本过滤关键技术研究》朱振方,刘培玉,尉永清著 2019
- 《被算法操控的生活:重新定义精准广告、大数据和AI=OUTNUMBERED FROM FACEBOOK AND GOOGLE TO FAKE NEWS AND FILTER-BUBBL》(瑞典)大卫·萨普特(DavidSumpter) 2020
- 《海洋动力环境模拟数值算法及应用》王永学 2019
- 《机器视觉算法原理与编程实战》杨青著 2019
- 《市政工程基础》杨岚编著 2009
- 《家畜百宝 猪、牛、羊、鸡的综合利用》山西省商业厅组织技术处编著 1959
- 《《道德经》200句》崇贤书院编著 2018
- 《高级英语阅读与听说教程》刘秀梅编著 2019
- 《计算机网络与通信基础》谢雨飞,田启川编著 2019
- 《看图自学吉他弹唱教程》陈飞编著 2019
- 《法语词汇认知联想记忆法》刘莲编著 2020
- 《培智学校义务教育实验教科书教师教学用书 生活适应 二年级 上》人民教育出版社,课程教材研究所,特殊教育课程教材研究中心编著 2019
- 《国家社科基金项目申报规范 技巧与案例 第3版 2020》文传浩,夏宇编著 2019
- 《流体力学》张扬军,彭杰,诸葛伟林编著 2019
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《北京生态环境保护》《北京环境保护丛书》编委会编著 2018
- 《高等教育双机械基础课程系列教材 高等学校教材 机械设计课程设计手册 第5版》吴宗泽,罗圣国,高志,李威 2018
- 《指向核心素养 北京十一学校名师教学设计 英语 九年级 上 配人教版》周志英总主编 2019
- 《高等院校旅游专业系列教材 旅游企业岗位培训系列教材 新编北京导游英语》杨昆,鄢莉,谭明华 2019
- 《中国十大出版家》王震,贺越明著 1991
- 《近代民营出版机构的英语函授教育 以“商务、中华、开明”函授学校为个案 1915年-1946年版》丁伟 2017
- 《新工业时代 世界级工业家张毓强和他的“新石头记”》秦朔 2019
- 《智能制造高技能人才培养规划丛书 ABB工业机器人虚拟仿真教程》(中国)工控帮教研组 2019
- 《AutoCAD机械设计实例精解 2019中文版》北京兆迪科技有限公司编著 2019