算法设计/21世纪高等学校计算机规划教材

图书标准信息

• 作者 郑宇军 著
• 出版社 人民邮电出版社
• 出版时间 2012-05
• 版次 1
• ISBN 9787115274359
• 定价 32.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 232页
• 字数 393千字
• 丛书 21世纪高等学校计算机规划教材

【内容简介】

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

【目录】

第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.20-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.2Strassen矩阵乘法
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.1Floyd算法
5.7.2Warshall算法
5.7.3Kleen抽象算法
5.8多阶段决策问题
5.9动态规划的备忘录方法
5.10小结
习题5

第6章贪心法
6.1找零钱问题
6.2最大数量装载问题
6.3最小生成树
6.3.1Prim算法
6.3.2Kruskal算法
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.20-1背包问题
7.2.1定义剪枝函数
7.2.2回溯算法
7.2.3分支限界算法
7.3旅行商问题
7.3.1回溯算法
7.3.2分支限界算法
7.4图着色问题
7.5N皇后问题
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.1P类问题
9.3.2NP类问题
9.4NP完全问题
9.4.1第一个NP完全问题
9.4.2NP完全性的证明
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.10-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.2N皇后问题
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伪代码语法规则