目 录
译者序
前言
第1章 什么是算法以及为什么应该关注算法 / 1
1.1 正确性 / 2
1.2 资源利用 / 4
1.3 针对非计算机专业人士的计算机算法 / 6
1.4 针对计算机专业人士的计算机算法 / 7
1.5 拓展阅读 / 9
第2章 如何描述和评估计算机算法 / 11
2.1 如何描述计算机算法 / 11
2.2 如何描述运行时间 / 19
2.3 循环不变式 / 24
2.4 递归 / 26
2.5 拓展阅读 / 28
第3章 排序算法和查找算法 / 29
3.1 二分查找 / 32
3.2 选择排序 / 37
3.3 插入排序 / 41
3.4 归并排序 / 46
3.5 快速排序 / 56
3.6 小结 / 65
3.7 拓展阅读 / 68
第4章 排序算法的下界和如何超越下界 / 69
4.1 基于排序的规则 / 70
4.2 基于比较排序的下界 / 71
4.3 使用计数排序超越下界 / 72
4.4 基数排序 / 79
4.5 拓展阅读 / 81
第5章 有向无环图 / 82
5.1 有向无环图 / 85
5.2 拓扑排序 / 86
5.3 如何表示有向图 / 90
5.4 拓扑排序的运行时间 / 92
5.5 PERT图表中的关键路径 / 92
5.6 有向无环图中的最短路径 / 97
5.7 拓展阅读 / 102
第6章 最短路径 / 103
6.1 Dijkstra算法 / 105
6.2 BellmanFord算法 / 117
6.3 FloydWarshall算法 / 123
6.4 拓展阅读 / 133
第7章 字符串算法 / 134
7.1 最长公共子序列 / 135
7.2 字符串转换 / 141
7.3 字符串匹配 / 151
7.4 拓展阅读 / 159
第8章 密码学基础 / 160
8.1 简单替代密码 / 161
8.2 对称密钥加密 / 163
8.3 公钥加密 / 167
8.4 RSA加密系统 / 170
8.5 混合加密系统 / 180
8.6 计算随机数 / 181
8.7 拓展阅读 / 182
第9章 数据压缩 / 183
9.1 赫夫曼编码 / 185
9.2 传真机 / 193
9.3 LZW压缩 / 194
9.4 拓展阅读 / 206
第10章 难？问题 / 207
10.1 棕卡车问题 / 207
10.2 P、NP和NP完全类 / 212
10.3 可判定问题和归约 / 214
10.4 主问题 / 218
10.5 NP完全问题例析 / 220
10.6 总体策略 / 238
10.7 前景 / 241
10.8 不可判定问题 / 244
10.9 小结 / 246
10.10 拓展阅读 / 247
参考文献 / 248
索引 / 250
鄂公网安备 42010302001612号 