算法设计

第1章 算法概述

1.1 问题、算法和程序

1.2 两个典型问题的求解

1.2.1 排序问题

1.2.2 稳定匹配问题

1.3 算法的复杂度分析

1.4 小结

习题1

第2章 基本数据结构

2.1 链表

2.1.1 普通链表

2.1.2 泛型链表

2.1.3 双向链表

2.2 堆栈和队列

2.2.1 堆栈

2.2.2 队列

2.2.3 优先级队列

2.3 树

2.3.1 树

2.3.2 二叉树

2.3.3 堆

2.4 图

2.4.1 图的基本概念

2.4.2 图的存储方式

2.5 小结

习题2

第3章 蛮力法

3.1 字符串匹配

3.2 矩阵相乘

3.3 子集和问题

3.4 冒泡排序

3.5 若干最优化问题

3.5.1 最近点对问题

3.5.2 0-1背包问题

3.5.3 子集和问题的最优化版本

3.5.4 最大独立集和最小顶点覆盖

3.5.5 旅行商问题

3.6 小结

习题3

第4章 递归和分治法

4.1 递归

4.1.1 递归的基本概念

4.1.2 递归算法的效率分析

4.1.3 汉诺塔问题

4.1.4 幂集和全排列

4.2 树和图中的一些递归问题

4.2.1 二叉树的遍历

4.2.2 图的遍历

4.3 分治法的基本思想

4.4 最近点对问题的分治算法

4.5 归并排序和快速排序

4.5.1 归并排序

4.5.2 快速排序

4.6 大数乘法和Strassen矩阵乘法

4.6.1 大数乘法

4.6.2 Strassen矩阵乘法

4.7 小结

习题4

第5章 动态规划法

5.1 动态规划法的基本思想

5.1.1 重叠子问题

5.1.2 最优性原则

5.2 计算二项式系数

5.3 最长连续上升子序列问题

5.4 最大子段和

5.4.1 一维数组的最大子段和

5.4.2 二维数组的最大子段和

5.5 序列比较

5.5.1 最长公共子序列问题

5.5.2 序列比对问题

5.6 矩阵连乘问题

5.7 图中的路径

5.7.1 Floyd算法

5.7.2 Warshall算法

5.7.3 Kleen抽象算法

5.8 多阶段决策问题

5.9 动态规划的备忘录方法

5.10 小结

习题5

第6章 贪心法

6.1 找零钱问题

6.2 最大数量装载问题

6.3 最小生成树

6.3.1 Prim算法

6.3.2 Kruskal算法

6.3.3 破圈算法

6.4 单源最短路径

6.5 往返运输问题

6.6 区间活动安排问题

6.7 单位时间任务调度问题

6.8 哈夫曼树

6.9 小结

习题6

第7章 回溯和分支限界

7.1 回溯和分支限界法的基本思想

7.1.1 状态空间

7.1.2 状态空间树与搜索策略

7.1.3 剪枝函数

7.2 0-1背包问题

7.2.1 定义剪枝函数

7.2.2 回溯算法

7.2.3 分支限界算法

7.3 旅行商问题

7.3.1 回溯算法

7.3.2 分支限界算法

7.4 图着色问题

7.5 N皇后问题

7.6 任务分配问题

7.7 小结

习题7

第8章 迭代改进法

8.1 线性规划与单纯形法

8.1.1 线性规划问题

8.1.2 线性规划的几何意义

8.1.3 单纯形法

8.2 二部图匹配问题

8.3 最大流

8.3.1 流网络

8.3.2 最大流问题

8.3.3 最小割问题

8.4 小结

习题8

第9章 计算复杂性与NP理论

9.1 多项式时间归约

9.2 计算模型

9.2.1 形式语言与问题编码

9.2.2 图灵机模型

9.2.3 不确定性图灵机

9.2.4 图灵机与可计算性

9.3 计算复杂性分类--P和NP

9.3.1 P类问题

9.3.2 NP类问题

9.4 NP完全问题

9.4.1 第一个NP完全问题

9.4.2 NP完全性的证明

9.4.3 更多的NP完全问题

9.5 小结

习题9

第10章 近似算法

10.1 绝对近似算法--平面图着色

10.2 相对近似算法--常数近似比

10.2.1 顶点覆盖问题

10.2.2 最短工期问题

10.2.3 旅行商问题

10.2.4 反馈集问题

10.3 相对近似算法--函数近似比

10.3.1 无重合路径问题

10.3.2 集合覆盖问题

10.4 相对近似算法--任意近似比

10.4.1 0-1背包问题的PTAS

10.4.2 子集和问题的FPTAS

10.5 小结

习题10

第11章 参数化算法

11.1 顶点覆盖问题的参数化算法

11.1.1 参数化问题与搜索树方法

11.1.2 问题简约：消除高度数顶点

11.1.3 增强的问题简约与搜索树方法

11.2 反馈集问题的参数化算法

11.2.1 问题简约

11.2.2 搜索树方法

11.2.3 改进的搜索树方法

11.3 支配集问题的参数化算法

11.4 参数化的计算复杂性框架

11.5 小结

习题11

第12章 随机算法

12.1 随机算法的基本概念

12.1.1 近似计算圆周率的随机算法

12.1.2 随机数的生成

12.1.3 抛硬币问题

12.2 舍伍德算法

12.2.1 随机化快速排序

12.2.2 有序链表搜索

12.3 蒙特卡洛算法

12.3.1 众数问题

12.3.2 素数判定问题

12.4 拉斯维加斯算法

12.4.1 随机取样问题

12.4.2 N皇后问题

12.4.3 大整数分解问题

12.5 小结

习题12

第13章 现代优化算法

13.1 禁忌搜索

13.1.1 禁忌搜索的基本思想

13.1.2 禁忌搜索算法框架与应用

13.2 模拟退火

13.2.1 模拟退火算法的基本思想

13.2.2 模拟退火算法框架与应用

13.3 遗传算法

13.3.1 遗传算法的基本思想

13.3.2 遗传算法框架与应用

13.3.3 遗传算法的其他变种

13.4 蚁群算法

13.4.1 蚁群算法的基本思想

13.4.2 蚁群算法框架与应用

13.5 粒子群算法

13.5.1 粒子群算法的基本思想

13.5.2 粒子群算法框架与应用

13.5.3 粒子群算法的其他变种

13.6 差分进化算法

13.6.1 差分进化算法的基本思想

13.6.2 差分进化算法框架与应用

13.6.3 差分进化算法的其他变种

13.7 小结

习题13

附录A 伪代码语法规则

《21世纪高等学校计算机规划教材：算法设计》以设计策略为主线，循序渐进地介绍了经典算法设计(包括分治、动态规划、贪心、回溯、迭代改进等算法)、NP完全理论、非精确型算法设计(包括近似算法、参数化算法，随机算法)，以及现代智能优化方法。在知识讲解中强调算法思维与编程实践并重，注重培养学生运用算法技术解决实际工程问题的能力。
《21世纪高等学校计算机规划教材：算法设计》可作为计算机科学及相关专业的本科和研究生教材，也可供软件开发人员学习参考。书中的算法提供多种语言的源代码下载。为提高教学效果，本书提供配套的教学课件，并配有专门的“算法设计教学演示软件”，欢迎授课教师使用。