第1章　算法概述

1.1 算法概念

1.1.1　什么是算法

1.1.2　抽象表达算法机制

1.2 算法的复杂度

1.2.1 算法三性态

1.2.2 算法复杂度

1.3 算法设计与分析的步骤

1.3.1 利用算法进行问题求解的过程

1.3.2 如何设计算法

1.3.3 如何表示算法

1.3.4 如何确认算法

1.3.5 如何分析算法

1.4 算法描述语言简介

1.4.1 C语言中的标准数据类型

1.4.2 C语言中的运算符

1.4.3 C语言中的语句简介

小结

习题一

一、选择题

二、填空题

三、简答题

四、计算题

五、上机题

第2章 递归技术

2.1 递归技术概述

2.1.1 什么是递归技术

2.1.2 递归技术的基本思想

2.2 Hanoi塔问题

2.3 递归方程的建立与求解

2.3.1 递推法

2.3.2 生成函数法

2.3.3 特征方程法

2.3.4 数学归纳法

2.3.5 不规则解法

2.4 递归消除

2.4.1 简单递归消除

2.4.2 基于栈的递归消除

小结

习题二

一、选择题

二、填空题

三、简答题

四、计算题

五、上机题

第3章 分治法

3.1 分治法概述

3.1.1 什么是分治法

3.1.2 分治法的基本思想

3.1.3 分治法的基本要素

3.2 二分检索技术

3.2.1 二分检索算法描述

3.2.2 最坏情况分析

3.2.3 平均复杂度分析

3.2.4 以比较为基础的检索时间下界

3.3 找第K小元素

3.3.1 分划点m的选取

3.3.2 随机选择算法

3.4 分治乘法

3.4.1 大整数相乘

3.4.2 多项式乘法

3.4.3 矩阵乘法

3.5 棋盘覆盖

3.6 分治合并排序

3.6.1 什么是合并

3.6.2 合并排序的基本思想

3.6.3 二路合并排序算法

3.7 分治快速排序

3.7.1　快速排序的基本思想

3.7.2　示例

3.8　常见分治

3.8.1　快速傅立叶变换

3.8.2　傅立叶变换的逆变换

3.8.3　利用傅立叶理论求解多项式相乘

小结

习题三

一、选择题

二、填空题

三、简答题

四、计算题

五、上机题

第4章　贪心法

4.1　贪心算法概述

4.1.1　什么是贪心法

4.1.2　贪心法的基本思想

4.1.3　贪心法基本要素

4.2　背包问题

4.3　磁带存储

4.3.1　单磁带最优存储

4.3.2　多磁带最优存储

4.4　作业调度

4.4.1　顺序选择法

4.4.2　最大期限选择法

4.5　启发式算法

4.6　贪心法的理论基础

4.6.1　拟阵

4.6.2　带权拟阵的贪心算法

4.6.3　任务时间表问题

4.7　常见贪心算法问题

4.7.1 最优装载

4.7.2 哈夫曼编码

4.7.3 单源最短路径

4.7.4 最小生成树

小结

习题四

一、选择题

二、填空题

三、简答题

四、计算题

五、上机题

第5章 动态规划

5.1 动态规划概述

5.1.1 什么是动态规划

5.1.2 动态规划的基本思想

5.1.3 动态规划的基本要素

5.2 最短路径

5.3 0/1背包问题

5.4 多矩阵乘积

5.5 货郎担问题

5.6 资源分配

小结

习题五

一、选择题

二、填空题

三、简答题

四、计算题

五、上机题

第6章 回溯法

6.1 概述

6.1.1 什么是回溯法

6.1.2 回溯法的基本思想

6.1.3 回溯法的算法框架与符号

6.2 n-皇后问题

6.3 图的m着色问题

6.3.1 图m着色问题的回溯法求解

6.3.2 图m着色问题的递归回溯算法

6.4 批处理作业调度问题

6.5 其他常见回溯法问题

6.5.1 最大团问题

6.5.2 旅行售货员问题

6.5.3 连续邮资问题

6.5.4 电路板排列问题

小结

习题六

一、选择题

二、填空题

三、简答题

四、计算题

五、上机题

第7章 分支限界法

7.1 概述

7.1.1 什么是分支限界法

7.1.2 分支限界的基本思想

7.2 复杂的有限期作业调度问题

7.3 贷郎担问题的分支限界法

7.4 其他分支限界问题

7.4.1 布线问题

7.4.2 0/1背包问题

7.4.3 单源最短路径的分支限界法

7.5 分支限界法与回溯法的比较

小结

习题七

一、选择题

二、填空题

三、简答题

四、计算题

五、上机题

第8章 概率算法概述

8.1 概率算法概述

8.1.1 什么是概率算法

8.1.2 概率算法的基本思想

8.2 数值概率算法

8.3 蒙特卡罗算法

8.4 其他概率算法

8.4.1 舍伍德算法

8.4.2 拉斯维加斯算法

小结

习题八

一、选择题

二、填空题

三、简答题

四、计算题

五、上机题

第9章 NP问题

9.1 NP问题概述

9.2 P类与NP类问题

9.2.1 非确定性图灵机

9.2.2 P类与NP类语言

9.2.3 多项式时间验证

9.3 NP完全问题

9.3.1 多项式时间变换

9.3.2 Cook定理

9.4 一些典型的NP完全问题

9.4.1 合取范式的可满足性问题CNF-SAT

9.4.2 三元合取范式的可满足性问题3-SAT

9.4.3 团问题CLIQUE

9.4.4 顶点覆盖问题VERTEX-COVER

9.4.5 子集和问题SUBSET-SUM

9.4.6 哈密顿回路问题HAM-CYCLE

9.4.7　旅行售货员问题TSP

小结

习题九

一、选择题

二、填空题

三、简答题

四、计算题

五、上机题

第10章　近似算法

10.1　近似算法概述

10.1.1　什么是近似算法

10.1.2　近似算法的基本思想及性能

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

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

10.4 子集合问题的近似算法

10.4.1 子集和问题的指数时间算法

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

小结

习题十

一、选择题

二、填空题

三、简答题

四、计算题

五、上机题

第11章 新型算法

11.1 加密算法概述

11.2 初等数论

11.3 DES以及3重DES算法

11.3.1 DES算法

11.3.2 三重DES算法

11.4 AES算法

11.4.1 Rijndael加密算法描述

11.4.2 Rijndael解密算法描述

11.5 RSA算法

小结

习题十一

一、选择题

二、填空题

三、简答题

四、计算题

五、上机题

第12章 并行算法

12.1 并行算法概述

12.2 并行计算机

12.2.1 并行计算机分类

12.2.2 并行计算机的处理机互连方式

12.2.3 并行计算模型

12.3 并行算法

12.3.1 数据并行模型

12.3.2 消息传递模型

12.3.3 共享变量模型

12.4 并行算法编程实现

12.4.1 枚举排序

12.4.2 快速排序

12.4.3 并行正则采样排序

小结

习题十二

一、选择题

二、填空题

三、简答题

四、计算题

五、上机题

第13章 上机实训

13.1 递归技术应用

13.2 运用贪心算法求解实际问题

13.2.1 套汇问题

13.2.2 汽车加油问题

13.3 动态规划法应用

13.3.1 最好费用购物

13.3.2 租用游艇问题

13.4 回溯法应用

13.4.1 重排九宫问题

13.4.2 智力拼图问题

13.5 分支限界法应用

13.5.1 0/1问题的栈式分支限界法

13.5.2 用最大堆存储活结点的优先队列式分支限界法

小结

参考文献