算法分析与设计

　　《算法分析与设计》将计算机经典问题和算法设计技术结合起来，系统深入地介绍了算法设计技术及其在经典问题中的应用。《算法分析与设计》共8章，第1章介绍了算法分析与设计的基本概念和基本方法，第2-8章分别介绍分治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术，每章均附有一篇阅读材料，介绍了算法领域的一些最新研究成果。书中所有算法均给出了C++描述，书中所有问题均给出了若干应用实例。《算法分析与设计》内容丰富，深入浅出，结合应用，图例丰富，可作为高等院校计算机专业本科生学习算法设计与分析的教材，也可供丁：程技术人员和自学读者学习参考。

暂缺《算法分析与设计》作者简介

第1章 绪论
1.1 算法的基本概念
1.1.1 为什么要学习算法
1.1.2 算法及其重要特性
1.1.3 算法的描述方法
1.1.4 算法设计的一般过程
1.2 算法分析
1.2.1 渐近符号
1.2.2 非递归算法的分析
1.2.3 递归算法的分析
1.2.4 算法的后验分析
实验1——求最大公约数
阅读材料1——海量数据处理方法：Bloom filter
习题1
第2章 分治法
2.1 概述
2.1.1 分治法简介
2.1.2 分治法的基本步骤
2.2 最大子段和问题
2.3 棋盘覆盖问题
2.4 输油管道问题
2.5 凸包问题
实验2——最近对问题
阅读材料2——分治法在中值滤波快速算法中的应用研究
习题2
第3章 动态规划
3.1 动态规划问题的数学描述
3.2 动态规划问题的最优化原理
3.3 动态规划应用举例
3.3.1 数字三角形问题
实验3数字三角形问题
阅读材料3——深入探讨动态规划中的几个问题
习题3
第4章 贪心法
4.1 概 述
4.1.1 贪心法的设计思想
4.1.2 贪心法的求解过程
4.2 删数问题
4.2.1 问题的提出
4.2.2 贪心选择策略
4.2.3 最优子结构性质
4.2.4 贪心选择性质
4.2.5 算法实现
4.3 图问题中的贪心法
4.3.1 TSP问题
4.3.2 图着色问题
4.4 FatMouse Trade
实验4——图着色问题
阅读材料4——用贪心算法求解删数问题
习题4
第5章 回溯法
5.1 概 述
5.1.1 问题的解空间
5.1.2 解空间树的动态搜索
5.1.3 回溯法的求解过程
5.1.4 回溯法的时间性能
5.2 装载问题
5.3 图着色问题
5.4 Fire Net
实验5——O／I背包问题
阅读材料5——基于回溯法油管传输射孔排炮算法研究
习题5
第6章 分支限界法
6.1 概 述
6.1.1 解空间树的动态搜索
6.1.2 分支限界法的设计思想
6.1.3 分支限界法的时间性能
6.2 TSP问题
6.3 电路布线问题
实验6-电路布线问题
阅读材料6——分支限界法在游戏地图寻径中的应用
习题6
第7章 概率算法
7.1 概 述
7.1.1 概率算法的设计思想
7.1.2 随机数发生器
7.2 舍伍德（Sherwood）型概率算法l
7.2.1 选择问题
7.3 拉斯维加斯（LasVegas）型概率算法
7.3.1 八皇后问题
7.3.2 整数因子分解问题
7.4 蒙特卡罗（Monte Carlo）型概率算法
7.4.1 主元素问题
实验7——随机数发生器
阅读材料7随机数生成原理
习题7
第8章 近似算法
8.1 概述
8.1.1 近似算法的设计思想
8.1.2 近似算法的性能
8.2 顶点覆盖问题
8.3 平方根问题
8.4 TSP问题
实验8——TsP问题的近似算法
阅读材料8 若干NP困难的组合最优化问题的近似算法
习题8
国际大学生程序设计竞赛试题——The Triangle
模拟试题
参考文献