算法设计与分析

第1章 算法引论

1.1 算法

1.2 算法描述

1.2.1 算法描述约定

1.2.2 一个简单问题的求解过程

1.3 算法分析基础

1.3.1 算法分析的评估体系

1.3.2 算法的时间复杂度

1.3.3 算法的空间复杂度

1.3.4 NP-完全问题

1.4 基本数据结构

1.4.1 栈和队列

1.4.2 树

1.4.3 图

1.5 迭代法

1.5.1 递推法

1.5.2 倒推法

1.5.3 迭代法解方程

1.6 递归和消除递归

1.6.1 递归

1.6.2 消除递归

本章小结

习题1

第2章 排序算法

2.1 排序

2.1.1 排序问题

2.1.2 冒泡问题

2.1.3 交换排序

2.1.4 选择排序

2.1.5 插入排序

2.2 堆排序

2.2.1 堆

2.2.2 建堆

2.2.3 堆排序算法

2.2.4 堆排序的应用

2.3 快速排序

2.3.1 快速排序的描述

2.3.2 快速排序的性能

2.3.3 随机化的快速排序算法

2.3.4 快速排序分析

2.4 线性时间排序

2.4.1 排序算法的下界

2.4.2 计数排序

2.4.3 基数排序

2.4.4 桶排序

2.5 中数排序

2.5.1 最大和最小元素

2.5.2 一般选择问题

本章小结

习题2

第3章 分治法

3.1 一般算法

3.2 二分检索

3.3 找最大值和最小值

3.4 归并分类

3.4.1 基本方法

3.4.2 改进的归并算法

3.5 快速分类

3.5.1 快速分类算法

3.5.2 快速分类分析

3.6 选择问题

3.6.1 选择问题算法

3.6.2 SELECT2实现

本章小结

习题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 回溯算法的抽象描述

4.3.3 n-皇后问题

4.3.4 子集和数问题

4.3.5 0/1背包问题

4.3.6 图的m-着色问题

4.3.7 哈密顿环

4.3.8 连续邮资问题

4.3.9 回溯法的效率估计

本章小结

习题4

第5章 贪心算法

5.1 算法概述

5.1.1贪心选择性质

5.1.2 最优子结构性质

5.1.3活动安排问题

5.2 背包问题

5.3 带有限期的作业排序

5.3.1 带有限期的作业排序算法

5.3.2 改进的带有限期的作业排序算法

5.4 最优归并模式

5.5 哈夫曼编码

5.5.1 前缀码

5.5.2 哈夫曼编码

5.6 最小生成树

5.6.1 Prim算法

5.6.2 Kruskal算法

5.7 单源点最短路径

本章小结

习题5

第6章 动态规划算法

6.1 一般方法

6.2 多段图

6.3 每对结点之间的最短路径

6.4 最优二分检索树

6.5 0/1背包问题

6.5.1 0/1背包问题实现的实例分析

6.5.2 DKP的实现

6.5.3 过程DKNAP的分析

6.6 可靠性设计

6.7 货郎担问题

6.8 流水线调度问题

本章小结

习题6

第7章 分支限界法

7.1 一般方法

7.1.1 FIFO和LIFO-检索

7.1.2 LC-检索

7.1.3 LC-检索的抽象化描述

7.1.4 分支限界法解最优化问题

7.2 0/1背包问题

7.2.1 LC-分支限界求解

7.2.2 FIFO –分支限界求解

7.3 货郎担问题

7.4 效率分析

本章小结

习题7

第8章 并行算法

8.1 并行计算机及并行模型

8.1.1 并行计算机

8.1.2 并行计算模型

8.1.3 并行计算机网络

8.1.4 并行算法的一般术语

8.2 SIMD共享存储模型的并行算法

8.2.1 播送算法

8.2.2 求和算法

8.2.3 并行k-选择算法

8.2.4 并行桶排序算法

8.2.5 有序表搜索并行算法

8.3 SIMD互联网络模型的并行算法

8.3.1 网孔上的随机序列搜索算法

8.3.2 树机上的矩阵和向量乘法

8.3.3 一维线性陈列上的奇偶转置排序算法

8.3.4 树机上求最小值算法

8.3.5 树机上的连通分量算法

8.4 MIMD共享存储模型的并行算法

8.4.1 异步枚举排序算法

8.4.2 单源点最短路径并行算法

8.4.3 最小生成树并行算法

8.4.4 Gauss-Seidel算法

8.4.5 牛顿求根并行算法

8.5 MIMD异步通信模型的并行算法

8.5.1 快速排序并行算法

8.5.2 二维网孔上的矩阵转置并行算法

8.5.3 矩阵并行分块乘法算法

8.5.4 分布式矩阵求逆的并行算法

8.5.5 分布式高斯消去并行算法

本章小结

习题8

第9章 NP-完全问题

9.1 计算模型

9.1.1 有限自动机

9.1.2 下推自动机

9.1.3 图灵机

9.2 P类与NP类问题

9.2.1 多项式时间界

9.2.2 P类问题

9.2.3 NP类问题

9.3 NP-完全问题

9.3.1 判定NP-完全问题的关键概念

9.3.2 NP-完全性

9.3.3 Cook定理

9.4 典型的NP-完全问题

9.4.1 NP-完全性的证明方法

9.4.2 典型的NP-完全问题

9.4.3 NP-完全问题的计算机实现

本章小结

习题9

第10章 近似算法

10.1 近似算法的性能

10.2 启发式算法

10.2.1 图着色问题

10.2.2 旅行商问题

10.3 任务安排的近似算法

10.4 覆盖问题的近似算法

10.4.1 顶点覆盖问题的近似算法

10.4.2 集合覆盖问题的近似算法

10.5 旅行售货员问题近似算法

10.5.1 具有三角不等式的旅行售货员问题

10.5.2 一般旅行售货员问题

10.6 背包问题

10.7 子集合问题的近似算法

10.7.1 解子集合问题的指数时间算法

10.7.2 子集合问题的完全多项式时间近似格式

本章小结

习题10

第11章 概率算法

11.1 概率算法概述

11.2 伪随机数

11.3 数值概率算法

11.3.1 用随机投点法计算圆周率值

11.3.2 计算定积分

11.3.3 解非线性方程组

11.4 Sherwood算法

11.4.1 线性时间选择算法

11.4.2 搜索有序表

11.4.3 跳跃表

11.5 Las Vegas算法

11.5.1 n后问题

11.5.2 整数因子分解

11.6 Monte Carlo算法

11.6.1 Monte Carlo算法的基本思想

11.6.2 主元素问题

11.6.3 素数性测试

本章小结

习题11

主要参考文献

本书作为普通高等学校计算机与信息安全专业本科生的教材，根据国内外计算机技术的最新发展，阐述计算机算法的各种设计策略、算法分析和一些经典及应用问题的算法。
全书共11章，第1章介绍算法引论；第2章阐述了排序算法；第3章介绍了分治算法；第4章介绍了图的搜索算法；第5章介绍了贪心算法；第6章介绍了动态规划算法；第7章介绍了分支限界法；第8章介绍了并行算法；第9 章介绍了NP-完全问题；第10章介绍了近似算法；第11章介绍了概率算法。
本书是一本注重系统性、科学性的教材，内容丰富、理论性强，可作为计算机与信息安全专业及其他相关专业的本科教材，也可作为计算机及信息安全领域软件开发人员的技术参考书。

计算机算法是计算机科学和计算机应用的核心，计算机科学技术的几乎每一项新的成就都与算法密切相关。算法设计与分析技术包含了培养高质量计算机人才所必需的基本理论和知识。通过对算法系统的学习，理解和掌握算法设计的主要方法，培养对算法的计算复杂性进行正确分析的能力，为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础。本书根据国内外计算机技术的最新发展，阐述了计算机算法的各种设计策略、算法分析和一些经典及应用问题的算法。本书是一本注重系统性、科学性的教材，内容丰富、理论性强的教材，它可作为普通高等学校计算机与信息安全专业本科生的教材。