算法设计与分析/21世纪高等学校规划教材·计算机科学与技术

图书标准信息

• 作者 王秋芬 著
• 出版社 清华大学出版社
• 出版时间 2011-08
• 版次 1
• ISBN 9787302251217
• 定价 33.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 313页
• 正文语种 简体中文
• 丛书 21世纪高等学校规划教材.计算机科学与技术

【内容简介】

《21世纪高等学校规划教材·计算机科学与技术：算法设计与分析》是普通本科高校计算机专业核心课程“算法设计与分析”的教材。本着“易理解，重实用”的指导思想，结合多年的教学经验，以算法设计策略为主线，沿着“算法思想—算法设计—构造实例—算法描述—算法分析”的思路来组织教材内，系统介绍了算法的设计方法和分析技巧。主要内容包括：算法及基础知识、贪心法、分治法、动态规划、搜索法、随机化算法、线性规划问题与网络流、数论算法及计算几何算法和NP完全理论。为突出教材的可读性、可用性及前沿性，每章增设了教学目标、阅读材料及习题解析。
《21世纪高等学校规划教材·计算机科学与技术：算法设计与分析》内容丰富、思路清晰、实例讲解详细、图例直观形象，适合作为计算机及其相关专业的本科生教材，也可供工程技术人员和自学读者学习参考。此外，也适合作为参加ACM程序设计大赛的爱好者的参考书或培训教材。

【目录】

第1章算法及基础知识
1.1算法的基本概念
1.1.1学习算法的重要性
1.1.2算法的定义及特性
1.1.3算法的描述方式
1.1.4算法与程序的区别
1.2算法设计的一般过程
1.3算法分析
1.3.1算法分析的概念
1.3.2时间复杂性
1.3.3空间复杂性
1.3.4渐进复杂性态
1.3.5算法复杂性的权衡考虑
1.4递归
1.4.1认知递归
1.4.2n的阶乘
1.4.3排列问题
1.4.4递归算法的复杂性分析
1.5基本的数据结构
1.5.1顺序表与链表
1.5.2栈与队列
1.5.3树与图
1.5.4集合
1.6常用数学公式
1.6.1对数公式
1.6.2组合公式
1.6.3求和公式
1.6.4向下取整和向上取整公式
阅读材料1--算法界十大名师简介
习题1

第2章贪心法
2.1概述
2.1.1贪心法的基本思想
2.1.2贪心法的基本要素
2.1.3贪心法的解题步骤及算法设计模式
2.2会场安排问题
2.3单源最短路径问题
2.4哈夫曼编码
2.5最小生成树
2.5.1Prim算法
2.5.2Kruskal算法
2.5.3两种算法的比较
阅读材料2--遗传算法
习题2

第3章分治法
3.1概述
3.1.1分治法的基本思想
3.1.2分治法的求解步骤
3.2二分查找
3.3循环赛日程表
3.4合并排序
3.5快速排序
阅读材料3--禁忌搜索算法
习题3

第4章动态规划
4.1概述
4.1.1动态规划的基本思想
4.1.2动态规划的求解步骤
4.1.3动态规划的基本要素
4.2矩阵连乘问题
4.3凸多边形最优三角剖分
4.4最长公共子序列问题
4.5加工顺序问题
4.60-1背包问题
4.7最优二叉查找树
阅读材料4--模拟退火算法
习题4

第5章搜索法
5.1穷举搜索
5.2深度优先搜索
5.3回溯法
5.3.1回溯法的算法框架及思想
5.3.2子集树
5.3.3排列树
5.3.4满m叉树
5.4宽度优先搜索
5.5分支限界法
5.5.1分支限界法的基本思想
5.5.20-1背包问题
5.5.3旅行商问题
5.5.4布线问题
5.5.5分支限界法与回溯法的比较
阅读材料5--蚁群算法
习题5

第6章随机化算法
6.1概述
6.1.1随机化算法的类型及特点
6.1.2随机数发生器
6.2数值随机化算法
6.2.1计算π的值
6.2.2计算定积分
6.3蒙特卡罗算法
6.3.1主元素问题
6.3.2素数测试
6.4拉斯维加斯算法
6.4.1整数因子分解
6.4.2n皇后问题
6.5舍伍德算法
6.5.1随机快速排序
6.5.2线性时间选择
阅读材料6--粒子群优化算法
习题6

第7章线性规划问题与网络流
7.1概述
7.1.1一般线性规划问题的描述
7.1.2标准型线性规划问题的描述
7.1.3标准型线性规划问题的单纯形算法
7.2最大网络流
7.2.1基本概念
7.2.2增广路算法
7.2.3最大网络流的变换与应用
7.3最小费用最大流
7.3.1基本概念
7.3.2消圈算法
7.3.3最小费用最大流的变换与应用
阅读材料7--捕食搜索算法
习题7

第8章数论算法及计算几何算法
8.1最大公约数
8.1.1欧几里得算法
8.1.2Stein算法
8.2同余方程
8.3同余方程组
8.4线段相交
8.5凸包问题
8.5.1凸包问题的穷举搜索法
8.5.2凸包问题的分治法
8.6最接近点对问题
8.6.1最接近点对问题的穷举搜索法
8.6.2最接近点对问题的分治法
阅读材料8--动态进化算法
习题8

第9章NP完全理论
9.1易解问题和难解问题
9.2P类和NP类问题
9.2.1P类问题
9.2.2NP类问题
9.2.3P类问题和NP类问题的关系
9.3NP完全问题
9.3.1多项式变换技术
9.3.2典型的NP完全问题
9.4NP完全问题的近似算法
9.4.1顶点覆盖问题
9.4.2装箱问题
9.4.3旅行商问题TSP
9.4.4集合覆盖问题
阅读材料9--DNA计算
习题9
附录A习题解析
第1章
第2章
第3章
第4章
第5章
第6章
第7章
第8章
第9章
参考文献