目录

教学大纲

教学课件

程序源码

第1章概念入门

1．1问题模型

1．2算法的概念

1．3算法的正确性

1．4算法的效率

1．5问题的下界

1．6小结

习题

实验题

第2章渐近符号

2．1Θ符号

2．2O符号

2．3Ω符号

2．4渐近符号的性质

2．5常用函数的直观含义

2．6小结

习题

第3章算法分析方法

3．1概率分析

3．2分摊分析

3．2．1合计方法

3．2．2记账方法

3．2．3势能方法

3．3实验分析

3．4小结

习题

第4章递归算法

4．1算法思想

4．1．1递归算法的应用

4．1．2递归与迭代

4．2递归方程的求解

4．2．1替换法

4．2．2递归树法

4．2．3公式法

4．3多项式求值实验

4．4小结

习题

实验题

第5章分治算法

5．1算法思想

5．2合并排序

5．3快速排序

5．4大整数乘法

5．5矩阵乘法

5．6残缺棋盘游戏

5．7快速傅里叶变换

5．8小结

习题

实验题

第6章动态规划算法

6．1算法思想

6．2装配线调度问题

6．3矩阵链乘法问题

6．4最长公共子序列问题

6．50/1背包问题

6．6最优二叉搜索树问题

6．7动态规划的基本性质

6．8小结

习题

实验题

第7章贪心算法

7．1算法思想

7．2任务选择问题

7．3背包问题

7．4哈夫曼编码问题

7．5缓存维护问题

7．6任务选择问题实验

7．7小结

习题

实验题

第8章图算法

8．1图的搜索问题

8．1．1宽度优先搜索

8．1．2深度优先搜索

8．2最小生成树问题

8．2．1Kruskal算法

8．2．2Prim算法

8．3最短路径问题

8．3．1单个源点的最短路径问题

8．3．2所有点对的最短路径问题

8．4小结

习题

实验题

第9章网络流与匹配

9．1最大流问题

9．1．1FordFulkerson算法

9．1．2最短路径增广算法

9．1．3Dinic 算法

9．1．4MPM 算法

9．1．5最大流问题的变形

9．2最小费用流问题

9．2．1消除回路算法

9．2．2最小费用路算法 

9．2．3最小费用路算法的改进

9．3匹配问题

9．3．1二分图匹配

9．3．2一般图的匹配

9．4小结

习题

实验题

第10章线性规划

10．1线性规划问题

10．1．1线性规划问题的标准形式

10．1．2线性规划问题的松弛形式

10．2求解算法

10．2．1图解法

10．2．2单纯形算法

10．3对偶

10．4小结

习题

实验题

第11章NP完全理论

11．1判定问题

11．2P和NP

11．3NPC

11．3．1NPC的定义

11．3．2电路可满足性问题

11．4NPC的证明

11．4．1可满足性问题

11．4．23CNF可满足性问题

11．4．3团问题

11．4．4顶点覆盖问题

11．5其他NP完全问题

11．6小结

习题

第12章回溯算法

12．1算法思想

12．2装载问题

12．30/1背包问题

12．4着色问题

12．5n皇后问题

12．6旅行商问题

12．7流水作业调度问题

12．8零件切割问题

12．9小结

习题

实验题

第13章分支限界算法

13．1算法思想

13．2装载问题

13．30/1背包问题

13．4可满足性问题

13．5旅行商问题

13．6流水作业调度问题

13．70/1背包问题实验

13．8小结

习题

实验题

第14章启发式搜索

14．1算法思想

14．2A*搜索算法

14．2．1最短路径问题

14．2．2八数字问题

14．3博弈搜索算法

14．3．1α和β剪支

14．3．2分硬币游戏

14．3．3井字博弈

14．4小结

习题

实验题

参考文献