《算法设计与分析》是2009年8月1日国防工业出版社出版的图书，作者是张德富。本书主要取材于算法设计与分析领域的经典内容，介绍了算法设计的发展趋势。

本书内容主要包括非常经典的算法设计技术，例如递归与分治、动态规划、贪心、回溯、分支限界、图算法，也包括了一些高级的算法设计主题，例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面，介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面，介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。

本书内容基本上涵盖了目前程序设计竞赛所要掌握的算法，并在书后精选了部分ACM国际大学生程序设计竞赛的题目，供大家练习。

本书可作为计算机科学系、数学系、软件学院等专业本科及研究生课程的教材，特别适合于有志于参加程序设计竞赛的学生学习和训练。

第1章 入门

1.1 问题

1.2 算法的概念

1.3 算法的正确性

1.4 算法的效率

1.5 问题的下界

1.6 小结

习题

实验题

第2章 渐近符号

2.1 θ符号

2.2 O符号

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 快速傅里叶变换(FFT)

5.8 小结

习题

实验题

第6章 动态规划

6.1 算法思想

6.2 装配线调度问题

6.3 矩阵链乘法问题

6.4 最长公共子序列问题

6.5 0/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.1 Kruskall算法

8.2.2 Prim算法

8.3 最短路径问题

8.3.1 单个源点的最短路径问题

8.3.2 所有点对的最短路径问题

8.4 小结

习题

实验题

第9章 网络流与匹配

9.1 最大流问题

9.1.1 FordFulkerson方法

9.1.2 最短路径增广算法

9.1.3 Dinic算法

9.1.4 MPM算法

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章 NIP完全理论

11.1 判定问题

11.2 P和NP

11.3 NPC

11.3.1 NPC的定义

11.3.2 电路可满足性问题

11.4 NPC的证明

11.4.1 可满足性问题

11.4.2 3.CNF可满足性问题

11。4.3 团问题

11.4.4 顶点覆盖问题

11.5 其他NP完全问题

11.6 小结

习题

第12章 回溯

12.1 算法思想

12.2 装载问题

12.3 0/1背包问题

12.4 着色问题

12.5 n皇后问题

12.6 旅行商问题

12.7 流水作业调度问题

12.8 零件切割问题

12.9 小结

习题

实验题

第13章 分支限界

第14章 启发式搜索

第15章 数论

第16章 计算几何

参考文献