算法分析与设计

第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）型概率算法l7.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模拟试题参考文献