编辑推荐
《面向CS2013计算机专业规划教材:算法设计与分析》主要面向计算机专业本科生，以及其他需要学习计算机科学基础知识与了解计算机程序设计背后原理的读者。
作者简介
南京大学计算机系副教授。
目录
前言
教学建议
第一部分计算模型
第1章抽象的算法设计与分析2
1.1RAM模型的引入2
1.1.1计算的基本概念2
1.1.2计算模型的基本概念3
1.1.3RAM模型4
1.1.4计算模型的选择：易用性和精确性6
1.2抽象算法设计7
1.2.1算法问题规约7
1.2.2算法正确性证明：数学归纳法8
1.3抽象算法分析10
1.3.1抽象算法的性能指标10
1.3.2最坏情况时间复杂度分析11
1.3.3平均情况时间复杂度分析12
1.4习题13
第2章从算法的视角重新审视数学的概念16
2.1数学运算背后的算法操作16
2.1.1取整x和x16
2.1.2对数logn17
2.1.3阶乘n！18
2.1.4常见级数求和∑ni=1f（i）19
2.1.5期望E（X）20
2.2函数的渐近增长率22
2.3“分治递归”求解24
2.3.1替换法24
2.3.2分治递归与递归树25
2.3.3Master定理26
2.4习题27
第二部分朴素遍历
第3章线性表的遍历32
3.1基于遍历的选择与查找32
3.2基于遍历的排序33
3.2.1选择排序34
3.2.2插入排序35
3.3习题37
第4章图的深度优先遍历39
4.1图和图遍历39
4.2有向图的深度优先遍历40
4.2.1有向图的深度优先遍历框架40
4.2.2有向图的深度优先遍历树42
4.2.3活动区间43
4.3有向图的深度优先遍历应用45
4.3.1拓扑排序45
4.3.2关键路径48
4.3.3有向图中的强连通片50
4.4无向图的深度优先遍历54
4.4.1无向图的深度优先遍历树55
4.4.2无向图的深度优先遍历框架56
4.5无向图的深度优先遍历应用57
4.5.1容错连通57
4.5.2寻找割点58
4.5.3寻找桥60
4.6习题61
第5章图的广度优先遍历66
5.1广度优先遍历66
5.1.1广度优先遍历框架67
5.1.2有向图的广度优先遍历树70
5.1.3无向图的广度优先遍历树70
5.2广度优先遍历的应用72
5.2.1判断二分图72
5.2.2寻找k度子图73
5.3习题74
第三部分分治策略
第6章排序：从遍历到分治78
6.1快速排序78
6.1.1插入排序的不足78
6.1.2快速排序的改进79
6.1.3快速排序的分析81
6.2合并排序84
6.3基于比较的排序的下界86
6.3.1决策树的引入87
6.3.2比较排序最坏情况时间复杂度的下界88
6.3.3比较排序平均情况时间复杂度的下界88
6.4习题90
第7章堆的设计与应用95
7.1堆的定义95
7.2堆的抽象维护96
7.2.1堆的修复96
7.2.2堆的构建97
7.3堆的具体实现98
7.4堆的应用100
7.4.1堆排序100
7.4.2基于堆实现优先队列100
7.5习题101
第8章线性时间选择103
8.1期望线性时间的选择103
8.1.1期望线性时间的选择算法设计103
8.1.2期望线性时间的选择算法分析104
8.2最坏情况线性时间的选择106
8.2.1最坏情况线性时间的选择算法设计106
8.2.2最坏情况线性时间的选择算法分析107
8.3习题108
第9章对数时间查找110
9.1折半查找110
9.1.1经典折半查找110
9.1.2折半查找的推广111
9.2平衡二叉搜索树112
9.2.1二叉搜索树及其平衡性113
9.2.2红黑树的定义114
9.2.3红黑树的平衡性115
9.3习题116
第四部分贪心策略
第10章最小生成树120
10.1Prim算法120
10.1.1Prim算法的正确性122
10.1.2Prim算法的实现125
10.1.3Prim算法的分析126
10.2Kruskal算法127
10.2.1Kruskal算法的正确性128
10.2.2判断是否成环——基于并查集的实现129
10.2.3Kruskal算法的实现与分析133
10.3最小生成树贪心构建框架MCE134
10.3.1从MCE框架的角度分析Prim算法135
10.3.2从MCE框架的角度分析Kruskal算法136
10.4习题137
第11章给定源点的最短路径142
11.1Dijkstra算法142
11.1.1Dijkstra算法的设计142
11.1.2Dijkstra算法的正确性与性能分析144
11.2从Dijkstra算法到贪心遍历框架BestFS146
11.3习题147
第12章贪心策略的其他应用151
12.1相容任务调度问题151
12.1.1直觉的尝试151
12.1.2基于任务结束时间的贪心算法152
12.2Huffman编码153
12.2.1可变长度编码153
12.2.2最优编码方案的性质154
12.2.3贪心的Huffman编码156
12.3习题156
第五部分动态规划
第13章最短路径160
13.1有向无环图上的给定源点最短路径问题160
13.2传递闭包问题和Shortcut算法161
13.3所有点对最短路径：基于路径长度的递归163
13.4Floyd—Warshall算法：基于中继节点范围的递归164
13.5习题166
第14章动态规划算法168
14.1动态规划的动机168
14.2动态规划的基本过程169
14.2.1基于朴素遍历的递归170
14.2.2未作规划的递归171
14.2.3采用动态规划的递归171
14.3动态规划的应用174
14.3.1动态规划的要素174
14.3.2编辑距离问题175
14.3.3硬币兑换问题176
14.3.4最大和连续子序列问题178
14.3.5相容任务调度问题179
14.4习题179
第六部分计算复杂性理论初步
第15章多项式时间归约188
15.1问题间的归约188
15.1.1优化问题和判定问题188
15.1.2问题间归约的定义189
15.2多项式时间：解决问题与完成归约190
15.2.1多项式时间可解的问题190
15.2.2多项式时间归约191
15.3习题192
第16章NP完全问题的基本概念193
16.1NP完全问题的定义193
16.1.1NP问题的定义193
16.1.2NP难与NP完全问题的定义194
16.2NP完全性证明的初步知识195
16.2.1一般问题和特例问题195
16.2.2等价的问题196
16.3习题197
附录A数学归纳法199
附录B二叉树200
参考文献201
文摘
版权页：
插图：
前面我们讨过，Prim算法基于图遍历的过程构建一棵生成树。更具体地说，Prim算法是基于广度优先遍历的过程来构建图中的一棵生成树。算法从一个调度器中取出一个节点v进行处理。在处理节点v的过程中，v的所有不在调度器中的邻居节点被加入调度器中，有待合适的时机被选择出来进行处理。这一过程保证了算法遍历整个图并得到一棵生成树。
Prim算法的关键在于它的贪心选择的过程。存图中所有未被选人当前局部最小生成树的节点中，有一些与当前最小生成树有边相连，我们称这些点为Fringe节点。我们要在所有Fringe节点之间进行贪心选择，这可以通过将Fringe节点维护成一个优先队列来实现。每个节点的优先级值就是它与当前的局部最小生成树中相连的边的权值，权值越小，优先级越高。如果一个点有多条边连到当前最小生成树，则最小的边权值为该节点的优先级，因而对于已经在优先队列中的点我们也需要随时检查是否需要更新它的优先级。
例如刚10.1和图10.2的例子中，点F以边FA与当前局部最小生成树相连。F的邻居1也进入优先队列，并且先于F进入当前局部最小生成树。此时，点F有边FA和FI与当前局部最小生成树相连，由于后来的边F1的权值更小，所以当1进入局部最小生成树后，需要更新优先队列中F的权值，从7（F—A的权值）更新为5（F1的权值）。
维护所有Fringe节点的优先队列就是整个Prim算法执行的调度器。当前需要处理的节点就是从Fringe中贪心选出的优先级最高（与当前局部最小生成树相连边的权值最小）的节点。
《面向CS2013计算机专业规划教材:算法设计与分析》主要面向计算机专业本科生，以及其他需要学习计算机科学基础知识与了解计算机程序设计背后原理的读者。
作者简介
南京大学计算机系副教授。
目录
前言
教学建议
第一部分计算模型
第1章抽象的算法设计与分析2
1.1RAM模型的引入2
1.1.1计算的基本概念2
1.1.2计算模型的基本概念3
1.1.3RAM模型4
1.1.4计算模型的选择：易用性和精确性6
1.2抽象算法设计7
1.2.1算法问题规约7
1.2.2算法正确性证明：数学归纳法8
1.3抽象算法分析10
1.3.1抽象算法的性能指标10
1.3.2最坏情况时间复杂度分析11
1.3.3平均情况时间复杂度分析12
1.4习题13
第2章从算法的视角重新审视数学的概念16
2.1数学运算背后的算法操作16
2.1.1取整x和x16
2.1.2对数logn17
2.1.3阶乘n！18
2.1.4常见级数求和∑ni=1f（i）19
2.1.5期望E（X）20
2.2函数的渐近增长率22
2.3“分治递归”求解24
2.3.1替换法24
2.3.2分治递归与递归树25
2.3.3Master定理26
2.4习题27
第二部分朴素遍历
第3章线性表的遍历32
3.1基于遍历的选择与查找32
3.2基于遍历的排序33
3.2.1选择排序34
3.2.2插入排序35
3.3习题37
第4章图的深度优先遍历39
4.1图和图遍历39
4.2有向图的深度优先遍历40
4.2.1有向图的深度优先遍历框架40
4.2.2有向图的深度优先遍历树42
4.2.3活动区间43
4.3有向图的深度优先遍历应用45
4.3.1拓扑排序45
4.3.2关键路径48
4.3.3有向图中的强连通片50
4.4无向图的深度优先遍历54
4.4.1无向图的深度优先遍历树55
4.4.2无向图的深度优先遍历框架56
4.5无向图的深度优先遍历应用57
4.5.1容错连通57
4.5.2寻找割点58
4.5.3寻找桥60
4.6习题61
第5章图的广度优先遍历66
5.1广度优先遍历66
5.1.1广度优先遍历框架67
5.1.2有向图的广度优先遍历树70
5.1.3无向图的广度优先遍历树70
5.2广度优先遍历的应用72
5.2.1判断二分图72
5.2.2寻找k度子图73
5.3习题74
第三部分分治策略
第6章排序：从遍历到分治78
6.1快速排序78
6.1.1插入排序的不足78
6.1.2快速排序的改进79
6.1.3快速排序的分析81
6.2合并排序84
6.3基于比较的排序的下界86
6.3.1决策树的引入87
6.3.2比较排序最坏情况时间复杂度的下界88
6.3.3比较排序平均情况时间复杂度的下界88
6.4习题90
第7章堆的设计与应用95
7.1堆的定义95
7.2堆的抽象维护96
7.2.1堆的修复96
7.2.2堆的构建97
7.3堆的具体实现98
7.4堆的应用100
7.4.1堆排序100
7.4.2基于堆实现优先队列100
7.5习题101
第8章线性时间选择103
8.1期望线性时间的选择103
8.1.1期望线性时间的选择算法设计103
8.1.2期望线性时间的选择算法分析104
8.2最坏情况线性时间的选择106
8.2.1最坏情况线性时间的选择算法设计106
8.2.2最坏情况线性时间的选择算法分析107
8.3习题108
第9章对数时间查找110
9.1折半查找110
9.1.1经典折半查找110
9.1.2折半查找的推广111
9.2平衡二叉搜索树112
9.2.1二叉搜索树及其平衡性113
9.2.2红黑树的定义114
9.2.3红黑树的平衡性115
9.3习题116
第四部分贪心策略
第10章最小生成树120
10.1Prim算法120
10.1.1Prim算法的正确性122
10.1.2Prim算法的实现125
10.1.3Prim算法的分析126
10.2Kruskal算法127
10.2.1Kruskal算法的正确性128
10.2.2判断是否成环——基于并查集的实现129
10.2.3Kruskal算法的实现与分析133
10.3最小生成树贪心构建框架MCE134
10.3.1从MCE框架的角度分析Prim算法135
10.3.2从MCE框架的角度分析Kruskal算法136
10.4习题137
第11章给定源点的最短路径142
11.1Dijkstra算法142
11.1.1Dijkstra算法的设计142
11.1.2Dijkstra算法的正确性与性能分析144
11.2从Dijkstra算法到贪心遍历框架BestFS146
11.3习题147
第12章贪心策略的其他应用151
12.1相容任务调度问题151
12.1.1直觉的尝试151
12.1.2基于任务结束时间的贪心算法152
12.2Huffman编码153
12.2.1可变长度编码153
12.2.2最优编码方案的性质154
12.2.3贪心的Huffman编码156
12.3习题156
第五部分动态规划
第13章最短路径160
13.1有向无环图上的给定源点最短路径问题160
13.2传递闭包问题和Shortcut算法161
13.3所有点对最短路径：基于路径长度的递归163
13.4Floyd—Warshall算法：基于中继节点范围的递归164
13.5习题166
第14章动态规划算法168
14.1动态规划的动机168
14.2动态规划的基本过程169
14.2.1基于朴素遍历的递归170
14.2.2未作规划的递归171
14.2.3采用动态规划的递归171
14.3动态规划的应用174
14.3.1动态规划的要素174
14.3.2编辑距离问题175
14.3.3硬币兑换问题176
14.3.4最大和连续子序列问题178
14.3.5相容任务调度问题179
14.4习题179
第六部分计算复杂性理论初步
第15章多项式时间归约188
15.1问题间的归约188
15.1.1优化问题和判定问题188
15.1.2问题间归约的定义189
15.2多项式时间：解决问题与完成归约190
15.2.1多项式时间可解的问题190
15.2.2多项式时间归约191
15.3习题192
第16章NP完全问题的基本概念193
16.1NP完全问题的定义193
16.1.1NP问题的定义193
16.1.2NP难与NP完全问题的定义194
16.2NP完全性证明的初步知识195
16.2.1一般问题和特例问题195
16.2.2等价的问题196
16.3习题197
附录A数学归纳法199
附录B二叉树200
参考文献201
文摘
版权页：
插图：
前面我们讨过，Prim算法基于图遍历的过程构建一棵生成树。更具体地说，Prim算法是基于广度优先遍历的过程来构建图中的一棵生成树。算法从一个调度器中取出一个节点v进行处理。在处理节点v的过程中，v的所有不在调度器中的邻居节点被加入调度器中，有待合适的时机被选择出来进行处理。这一过程保证了算法遍历整个图并得到一棵生成树。
Prim算法的关键在于它的贪心选择的过程。存图中所有未被选人当前局部最小生成树的节点中，有一些与当前最小生成树有边相连，我们称这些点为Fringe节点。我们要在所有Fringe节点之间进行贪心选择，这可以通过将Fringe节点维护成一个优先队列来实现。每个节点的优先级值就是它与当前的局部最小生成树中相连的边的权值，权值越小，优先级越高。如果一个点有多条边连到当前最小生成树，则最小的边权值为该节点的优先级，因而对于已经在优先队列中的点我们也需要随时检查是否需要更新它的优先级。
例如刚10.1和图10.2的例子中，点F以边FA与当前局部最小生成树相连。F的邻居1也进入优先队列，并且先于F进入当前局部最小生成树。此时，点F有边FA和FI与当前局部最小生成树相连，由于后来的边F1的权值更小，所以当1进入局部最小生成树后，需要更新优先队列中F的权值，从7（F—A的权值）更新为5（F1的权值）。
维护所有Fringe节点的优先队列就是整个Prim算法执行的调度器。当前需要处理的节点就是从Fringe中贪心选出的优先级最高（与当前局部最小生成树相连边的权值最小）的节点。
| ISBN | 7111572971,9787111572978 |
|---|---|
| 出版社 | 机械工业出版社 |
| 作者 | 黄宇 |
| 尺寸 | 16 |