计算机算法与程序设计

第1章 绪论

1.1 算法研究的意义

1.2 算法与程序

1.3 算法的描述工具

1.4 算法的复杂性分析

1.4.1 时间复杂度

1.4.2 空间复杂度

1.5 常用数学分析公式

第2章 数据抽象与数据结构

2.1 数据抽象概念

2.1.1 数据结构的基本概念和术语

2.1.2 数据抽象

2.2 基本数据结构

2.2.1 线性表与向量

2.2.2 链表

2.2.3 栈和队列

2.2.4 二叉树

2.2.5 图

2.3 关键数据结构拓广

2.3.1 哈希表

2.3.2 并查集（等价类）

2.3.3 线段树

2.3.4 二叉堆

第3章 初等数论

3.1 数论基础

3.1.1 素数与算术基本定理

3.1.2 最大公约数与最小公倍数

3.2 同余方程

3.2.1 同余方程概念

3.2.2 中国剩余定理

3.3 数论函数

3.3.1 欧拉函数

3.3.2 积性函数

3.4 素数和整除

3.4.1 筛法求素数

3.4.2 整数Ⅳ的因子函数

3.5 高精度计算

第4章 组合数学初步

4.1 加法原理与乘法原理

4.2 鸽笼原理和Ramsey数

4.3 递推关系和生成函数

4.3.1 Fibonacci数

4.3.2 Catalan数

4.3.3 第二类Stirlin9数

4.4 排列组合

4.4.1 字典序排列

4.4.2 组合算法

4.4.3 二项式系数

4.5 容斥原理

4.5.1 容斥原理的概念

4.5.2 错排问题

4.6 Polya定理及其应用

第5章 递归与分治策略

5.1 递归概念

5.1.1 递归与递归调用

5.1.2 递归应用

5.2 分治法概述

5.2.1 分治法基本思想

5.2.2 分治算法设计和特点

5.3 分治法的基本应用

5.3.1 最大最小值

5.3.2 Strassen矩阵乘法

5.4 分治法解骑士周游

5.5 大整数乘法

5.5.1 常规大整数乘法

5.5.2 分治法解大整数乘法

5.6 棋盘覆盖问题

第6章 贪心算法

6.1 贪心算法概述

6.1.1 贪心举例

6.1.2 贪心算法的理论基础

6.1.3 贪心算法与动态规划算法的区别

6.2 背包问题

6.3 机器任务调度算法

6.3.1 多机调度问题

6.3.2 活动安排问题

6.4 最小生成树

6.4.1 普里姆（Prim）算法

6.4.2 克鲁斯卡尔（Kruskal）算法

6.5 哈夫曼（Huffman）树及其应用

6.5.1 Huffman树

6.5.2 哈夫曼编码

6.5.3 Huffman算法的正确性

第7章 动态规划

7.1 动态规划算法思想

7.1.1 动态规划最优决策原理

7.1.2 动态规划求解步骤

7.1.3 动态规划的数学抽象

7.2 矩阵连乘问题

7.3 最长子序列探索

7.3.1 最长递增子序列

7.3.2 最长公共子序列

7.4 多段图的最短路径

7.5 资源分配问题

7.6 树状动态规划

第8章 搜索技术

8.1 盲目搜索算法

8.1.1 对分搜索

8.1.2 DFS与BFS搜索算法

8.1.3 盲目搜索算法应用

8.2 回溯算法

8.3 启发式搜索

8.3.1 启发式搜索策略

8.3.2 A*算法

8.4 博弈问题

8.4.1 博弈树

8.4.2 极小极大搜索法

8.5 α-β剪枝技术

第9章 图论算法

9.1 基本概念和定理

9.1.1 可行遍性问题

9.1.2 平面图

9.1.3 独立集、覆盖与支配集

9.2 最短路径

9.2.1 Diikstra算法

9.2.2 Floyd算法求一对点最短路径

9.3 道路和回路

9.3.1 欧拉道路和欧拉回路

9.3.2 哈密尔顿图和货郎担问题

9.4 网络流算法

9.4.1 基本概念

9.4.2 最大流问题

9.4.3 最小费用流

9.5 二分图相关问题

9.5.1 二分图的最大匹配

9.5.2 二分图的最佳匹配

第10章 计算几何

10.1 计算几何基本问题

10.1.1 矢量与线段

10.1.2 几何计算公式

10.2 点与线段的关系

10.2.1 点与线段的距离

10.2.2 线段与直线的交点

10.3 多边形

10.3.1 多边形基本概念

10.3.2 点与多边形的关系

10.4 凸包问题

10.4.1 判断凸包

10.4.2 寻找凸包

10.5 欧拉定理及其应用.

第11章 排序

11.1 排序基础

11.2 比较排序法

11.2.1 插入排序

11.2.2 冒泡排序

11.2.3 简单选择排序

11.3 基于分治策略的排序算法

11.3.1 快速排序

11.3.2 归并排序

11.4 堆排序

11.4.1 树状选择排序

11.4.2 堆排序

11.5 基数排序

11.6 排序小结

第12章 算法与程序经典实例

12.1 计算机算法设计实例

12.2 国际竞赛程序实例分析

将本科“计算机算法与程序设计”课程与大学生程序设计竞赛有机地结合是新时期教学改革、培养实用型计算机优秀人才的创新。本书既系统深入地介绍算法设计的理论知识，又详尽地将其应用于实际编程，做到理论与实践的统一。书中首先从理论的角度介绍了算法基础，数据抽象与数据结构，初等数论，组合数学初步；讲述了递归与分治策略，动态规划，贪心算法，搜索技术，图论算法；进一步研究了计算几何，排序算法；最后从实践的角度给出了程序设计典型实例及详细解析。