算法设计与分析

第1章 概论

1.1 算法的概念

1.1.1 什么是算法

1.1.2 算法描述

1.1.3 算法和数据结构

1.1.4 算法设计的基本步骤

1.2 算法分析

1.2.1 算法时间复杂度分析

1.2.2 算法空间复杂度分析

1.3 计算复杂性理论简介

1.3.1 图灵机模型

1.3.2 P类和NP类问题

1.3.3 NPC问题

上机实验题1——统计求最大、最小元素的平均比较次数

练习题1

第2章 递归算法设计技术

2.1 什么是递归

2.1.1 递归的定义

2.1.2 何时使用递归

2.1.3 递归模型

2.1.4 递归算法的执行过程

2.2 递推式的计算

2.2.1 用特征方程求解递归方程

2.2.2 用递归树方法求解递归方程

2.3 递归算法设计

2.3.1 递归与数学归纳法

2.3.2 递归算法设计的一般步骤

2.3.3 基于递归数据结构的递归算法设计

2.3.4 基于归纳思想的递归算法设计

2.4 递归算法设计示例

2.4.1 简单选择排序和冒泡排序

2.4.2 求解n皇后问题

2.4.3 求解简单装载问题

2.5 递归算法转化为非递归算法

2.5.1 用循环结构替代递归过程

2.5.2 用栈消除递归过程

上机实验题2——删除二叉树的子树

练习题2

第3章 穷举法

3.1 穷举法概述

3.2 穷举法的基本应用

3.2.1 直接采用穷举法的一般格式

3.2.2 简单选择排序和冒泡排序

3.2.3 求解幂集问题

3.2.4 求解0/1背包问题

3.2.5 求解全排列问题

3.2.6 求解最大连续子序列和问题

3.3 递归在穷举法中的应用

3.3.1 用递归方法求解幂集问题

3.3.2 用递归方法求解全排列问题

3.3.3 用递归方法求解组合问题

上机实验题3——钱币兑换问题

练习题3

第4章 分治法

4.1 分治法概述

4.1.1 分治法的设计思想

4.1.2 分治法的求解过程

4.2 求解排序问题

4.2.1 快速排序

4.2.2 归并排序

4.3 求解查找问题

4.3.1 折半查找

4.3.2 寻找一个序列中第k小元素

4.3.3 寻找两个等长有序序列的中位数

4.4 求解最大连续子序列和问题

4.5 求解大整数乘法问题

4.6 求解矩阵乘法问题

4.7 并行计算简介

4.7.1 并行计算概述

4.7.2 并行计算模型

4.7.3 快速排序的并行算法

上机实验题4——求序列的最大元素和次大元素

练习题4

第5章 贪心法

5.1 贪心法概述

5.1.1 什么是贪心法

5.1.2 贪心法求解的问题应具有的性质

5.1.3 贪心法的一般求解过程

5.2 求解区间问题

5.2.1 求解区间覆盖问题

5.2.2 求解最大不相交区间问题

5.2.3 求解活动安排问题

5.3 求解背包问题

5.4 求解多机调度问题

5.5 哈夫曼编码

5.6 求解磁盘排序问题

上机实验题5——求解删数问题

练习题5

第6章 动态规划

6.1 动态规划概述

6.1.1 动态规划的原理

6.1.2 动态规划求解的基本步骤

6.1.3 动态规划与其他方法的比较

6.2 求解整数拆分问题

6.3 求解最长公共子序列问题

6.4 求解0/1背包问题

6.5 求解完全背包问题

6.6 求解最大连续子序列和问题

6.7 求解资源分配问题

上机实验题6——求最长单调递增子序列

练习题6

第7章 回溯法

7.1 回溯法概述

7.1.1 问题的解空间

7.1.2 什么是回溯法

7.1.3 回溯法的算法框架

7.1.4 回溯法算法的时间分析

7.2 求解0/1背包问题

7.3 求解子集和问题

7.4 求解排列和组合问题

7.4.1 求解全排列问题

7.4.2 求解组合问题

7.5 求解迷宫问题

7.5.1 采用回溯法递归框架求解迷宫问题

7.5.2 采用回溯法非递归框架求解迷宫问题

7.6 求解n皇后问题

7.6.1 不采用栈求解n皇后问题

7.6.2 采用栈求解n皇后问题

上机实验题7——求解装载问题

练习题7

第8章 分枝限界法

8.1 分枝限界法概述

8.1.1 什么是分枝限界法

8.1.2 分枝限界法的设计思想

8.1.3 分枝限界法的时间性能

8.2 求解0/1背包问题

8.2.1 采用队列式分枝限界法求解

8.2.2 采用优先队列式分枝限界法求解

上机实验题8——求解最优装载问题

练习题8

第9章 图搜索算法设计

9.1 图的表示

9.1.1 图的定义

9.1.2 图的存储结构

9.2 图的搜索方法

9.2.1 图搜索的概念

9.2.2 深度优先搜索

9.2.3 广度优先搜索

9.3 最小生成树

9.3.1 最小生成树的概念

9.3.2 普里姆算法构造最小生成树

9.3.3 克鲁斯卡尔算法

9.4 最短路径

9.4.1 狄克斯特拉算法

9.4.2 贝尔曼·福特算法

9.4.3 弗洛伊德算法

9.5 利用STL设计算法

9.5.1 什么是容器

9.5.2 什么是算法

9.5.3 什么是迭代器

9.5.4 常用STL容器的使用

9.6 求解TSP问题

9.6.1 TSP问题描述

9.6.2 采用穷举法求解TSP问题

9.6.3 采用动态规划求解TSP问题

9.6.4 采用回溯法求解TSP问题

9.6.5 采用分枝限界法求解TSP问题

9.6.6 采用贪心法求解TSP问题

9.7 求多段图的关键路径

9.8 网络流

9.8.1 相关概念

9.8.2 求最大流

9.8.3 割集与割量

9.8.4 求最小费用最大流

上机实验题9——求图着色问题

练习题9

第10章 计算几何

10.1 矢量运算

10.1.1 矢量的基本运算

10.1.2 判断一个点是否在一个矩形内

10.1.3 判断一个点是否在一条线段上

10.1.4 判断两条线段是否平行

10.1.5 判断两线段是否相交

10.1.6 判断一个点是否在多边形内

10.2 求解凸包问题

10.2.1 礼品包裹算法

10.2.2 Graham扫描算法

10.3 求解最近点对问题

10.3.1 用穷举法求最近点对

10.3.2 用分治法求最近点对

10.4 求解最远点对问题

10.4.1 用穷举法求最远点对

10.4.2 用旋转卡壳法求最远点对

上机实验题10——求凸多边形的直径

练习题10

附录A 部分练习题参考答案

附录B 上机实验题参考程序

附录C 书中部分算法清单

参考文献

本书系统地介绍了各种常用的算法设计策略，包括穷举法、分治法、贪心法、动态规划法、回溯法、分枝限界法等，并详细讨论了各种图搜索算法和计算几何设计算法。全书既注重原理又注重实践，配有大量图表、上机实验题和练习题，内容丰富，概念讲解清楚，表达严谨，逻辑性强，语言精练，可读性好。本书既便于教师课堂讲授，又便于自学者阅读。本书可作为高等院校算法设计与分析课程的教材，也可供ACM和各类程序设计竞赛者参考。

内容全面、知识点详实：在内容讲授上力求详实和全面，细致解析每个知识点和各知识点的联系。
梯度合理：按照算法思路、算法设计方法、应用的模式编写，适合不同层次的读者学习。
多维性：强调同一个问题的多种算法策略以及不同算法的比较。
教学资源包完整：提供PPT、源程序代码和部分练习题的参考答案，方便教师教学和学生学习。