算法设计与分析

第1章  算法引论                  
 1. 1  算法与程序                  
 1. 2  表达算法的抽象机制                  
 1. 3  描述算法                  
 1. 4  算法复杂性分析                  
 小结                  
 习题                  
                   
 第2章  递归与分治策略                  
 2. 1  递归的概念                  
 2. 2  分治法的基本思想                  
 2. 3  二分搜索技术                  
 2. 4  大整数的乘法                  
 2. 5  Strassen矩阵乘法                  
 2. 6  棋盘覆盖                  
 2. 7  合并排序                  
 2. 8  快速排序                  
 2. 9  线性时间选择                  
 2. 10  最接近点对问题                  
 2. 11  循环赛日程表                  
 小结                  
 习题                  
                   
 第3章  动态规划                  
 3. 1  矩阵连乘问题                  
 3. 2  动态规划算法的基本要素                  
 3. 3  最长公共子序列                  
 3. 4  凸多边形最优三角剖分                  
 3. 5  多边形游戏                  
 3. 6  图像压缩                  
 3. 7  电路布线                  
 3. 8  流水作业调度                  
 3. 9  0-1背包问题                  
 3. 10  最优二叉搜索树                  
 小结                  
 习题                  
                   
 第4章  贪心算法                  
 4. 1  活动安排问题                  
 4. 2  贪心算法的基本要素                  
 4. 2. 1  贪心选择性质                  
 4. 2. 2  最优子结构性质                  
 4. 2. 3  贪心算法与动态规划算法的差异                  
 4. 3  最优装载                  
 4. 4  哈夫曼编码                  
 4. 4. 1  前缀码                  
 4. 4. 2  构造哈夫曼编码                  
 4. 4. 3  哈夫曼算法的正确性                  
 4. 5  单源最短路径                  
 4. 5. 1  算法基本思想                  
 4. 5. 2  算法的正确性和计算复杂性                  
 4. 6  最小生成树                  
 4. 6. 1  最小生成树性质                  
 4. 6. 2  Prim算法                  
 4. 6. 3  Kruskal算法                  
 4. 7  多机调度问题                  
 4. 8  贪心算法的理论基础                  
 4. 8. 1  拟阵                  
 4. 8. 2  带权拟阵的贪心算法                  
 4. 8. 3  任务时间表问题                  
 小结                  
 习题                  
                   
 第5章  回溯法                  
 5. 1  回溯法的算法框架                  
 5. 1. 1  问题的解空间                  
 5. 1. 2  回溯法的基本思想                  
 5. 1. 3  递归回溯                  
 5. 1. 4  迭代回溯                  
 5. 1. 5  子集树与排列树                  
 5. 2  装载问题                  
 5. 3  批处理作业调度                  
 5. 4  符号三角形问题                  
 5. 5  n后问题                  
 5. 6  0-1背包问题                  
 5. 7  最大团问题                  
 5. 8  图的m着色问题                  
 5. 9  旅行售货员问题                  
 5. 10  圆排列问题                  
 5. 11  电路板排列问题                  
 5. 12  连续邮资问题                  
 5. 13  回溯法的效率分析                  
 小结                  
 习题                  
                   
 第6章  分支限界法                  
 6. 1  分支限界法的基本思想                  
 6. 2  单源最短路径问题                  
 6. 3  装载问题                  
 6. 4  布线问题                  
 6. 5  0-1背包问题                  
 6. 6  最大团问题                  
 6. 7  旅行售货员问题                  
 6. 8  电路板排列问题                  
 6. 9  批处理作业调度                  
 小结                  
 习题                  
                   
 第7章  概率算法                  
 7. 1  随机数                  
 7. 2  数值概率算法                  
 7. 2. 1  用随机投点法计算n值                  
 7. 2. 2  计算定积分                  
 7. 2. 3  解非线性方程组                  
 7. 3  舍伍德算法                  
 7. 3. 1  线性时间选择算法                  
 7. 3. 2  跳跃表                  
 7. 4  拉斯维加斯算法                  
 7. 4. 1  n后问题                  
 7. 4. 2  整数因子分解                  
 7. 5  蒙特卡罗算法                  
 7. 5. 1  蒙特卡罗算法的基本思想                  
 7. 5. 2  主元素问题                  
 7. 5. 3  素数测试                  
 小结                  
 习题                  
                   
 第8章  NP完全性理论                  
 8. 1  计算模型                  
 8. 1. 1  随机存取机RAM                  
 8. 1. 2  随机存取存储程序机RASP                  
 8. 1. 3  RAM模型的变形与简化                  
 8. 1. 4  图灵机                  
 8. 1. 5  图灵机模型与RAM模型的关系                  
 8. 1. 6  问题变换与计算复杂性归约                  
 8. 2  P类与NP类问题                  
 8. 2. 1  非确定性图灵机                  
 8. 2. 2  P类与NP类语言                  
 8. 2. 3  多项式时间验证                  
 8. 3  NP完全问题                  
 8. 3. 1  多项式时间变换                  
 8. 3. 2  Cook定理                  
 8. 4  一些典型的NP完全问题                  
 8. 4. 1  合取范式的可满足性问题                  
 8. 4. 2  3元合取范式的可满足性问题                  
 8. 4. 3  团问题                  
 8. 4. 4  顶点覆盖问题                  
 8. 4. 5  子集和问题                  
 8. 4. 6  哈密顿回路问题                  
 8. 4. 7  旅行售货员问题                  
 小结                  
 习题                  
                   
 第9章  近似算法                  
 9. 1  近似算法的性能                  
 9. 2  顶点覆盖问题的近似算法                  
 9. 3  旅行售货员问题近似算法                  
 9. 3. 1  具有三角不等式性质的旅行售货员问题                  
 9. 3. 2  一般的旅行售货员问题                  
 9. 4  集合覆盖问题的近似算法                  
 9. 5  子集和问题的近似算法                  
 9. 5. 1  子集和问题的指数时间算法                  
 9. 5. 2  子集和问题的完全多项式时间近似格式                  
 小结                  
 习题                  
                   
 第10章  算法优化策略                  
 10. 1  算法设计策略的比较与选择                  
 10. 1. 1  最大子段和问题的简单算法                  
 10. 1. 2  最大子段和问题的分治算法                  
 10. 1. 3  最大子段和问题的动态规划算法                  
 10. 1. 4  最大子段和问题与动态规划算法的推广                  
 10. 2  动态规划加速原理                  
 10. 2. 1  货物储运问题                  
 10. 2. 2  算法及其优化                  
 10. 3  问题的算法特征                  
 10. 3. 1  贪心策略                  
 10. 3. 2  对贪心策略的改进                  
 10. 3. 3  算法三部曲                  
 10. 3. 4  算法实现                  
 10. 3. 5  算法复杂性                  
 10. 4  优化数据结构                  
 10. 4. 1  带权区间最短路问题                  
 10. 4. 2  算法设计思想                  
 10. 4. 3  算法实现方案                  
 10. 4. 4  并查集                  
 10. 4. 5  可并优先队列                  
 10. 5  优化搜索策略                  
 小结                  
 习题                  
 参考文献