算法设计与分析习题解答(第2版)

《算法设计与分析习题解答(第2版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章算法引论11.1算法与程序11.2表达算法的抽象机制11.3描述算法31.4算法复杂性分析13小结16习题17第2章递归与分治策略192.1递归的概念192.2分治法的基本思想262.3二分搜索技术272.4大整数的乘法282.5Strassen矩阵乘法302.6棋盘覆盖322.7合并排序342.8快速排序372.9线性时间选择392.10最接近点对问题432.11循环赛日程表53小结54习题54第3章动态规划613.1矩阵连乘问题62目录算法设计与分析(第2版)3.2动态规划算法的基本要素673

2、.3最长公共子序列713.4凸多边形最优三角剖分753.5多边形游戏793.6图像压缩823.7电路布线853.8流水作业调度883.90-1背包问题923.10最优二叉搜索树98小结101习题102第4章贪心算法1074.1活动安排问题1074.2贪心算法的基本要素1104.2.1贪心选择性质1114.2.2最优子结构性质1114.2.3贪心算法与动态规划算法的差异1114.3最优装载1144.4哈夫曼编码1164.4.1前缀码1174.4.2构造哈夫曼编码1174.4.3哈夫曼算法的正确性1194.

3、5单源最短路径1214.5.1算法基本思想1214.5.2算法的正确性和计算复杂性1234.6最小生成树1254.6.1最小生成树性质1254.6.2Prim算法1264.6.3Kruskal算法1284.7多机调度问题1304.8贪心算法的理论基础1334.8.1拟阵1334.8.2带权拟阵的贪心算法1344.8.3任务时间表问题137小结141习题141第5章回溯法1465.1回溯法的算法框架1465.1.1问题的解空间1465.1.2回溯法的基本思想1475.1.3递归回溯1495.1.4迭代回溯

4、1505.1.5子集树与排列树1515.2装载问题1525.3批处理作业调度1605.4符号三角形问题1625.5n后问题1655.60

5、1背包问题1685.7最大团问题1715.8图的m着色问题1745.9旅行售货员问题1775.10圆排列问题1795.11电路板排列问题1815.12连续邮资问题1855.13回溯法的效率分析187小结190习题191第6章分支限界法1956.1分支限界法的基本思想1956.2单源最短路径问题1986.3装载问题2026.4布线问题2116.50

6、1背包问题216

7、6.6最大团问题2226.7旅行售货员问题2256.8电路板排列问题2296.9批处理作业调度232小结237习题238第7章概率算法2407.1随机数2417.2数值概率算法2447.2.1用随机投点法计算π值2447.2.2计算定积分2457.2.3解非线性方程组2477.3舍伍德算法2507.3.1线性时间选择算法2507.3.2跳跃表2527.4拉斯维加斯算法2597.4.1n后问题2607.4.2整数因子分解2647.5蒙特卡罗算法2667.5.1蒙特卡罗算法的基本思想2667.5.2主元

8、素问题2687.5.3素数测试270小结273习题273第8章NP完全性理论2788.1计算模型2798.1.1随机存取机RAM2798.1.2随机存取存储程序机RASP2878.1.3RAM模型的变形与简化2918.1.4图灵机2958.1.5图灵机模型与RAM模型的关系2978.1.6问题变换与计算复杂性归约2998.2P类与NP类问题3018.2.1非确定性图灵机3018.2.2P类与NP类语言3028.2.3多项式时间验证3048.3NP完全问题3058.3.1多项式时间变换3058.3.2Co

9、ok定理3078.4一些典型的NP完全问题3108.4.1合取范式的可满足性问题3118.4.23元合取范式的可满足性问题3128.4.3团问题3138.4.4顶点覆盖问题3148.4.5子集和问题3158.4.6哈密顿回路问题3178.4.7旅行售货员问题322小结323习题323第9章近似算法3269.1近似算法的性能3279.2顶点覆盖问题的近似算法3289.3旅行售货员问题近似算法3299.3.1具有三角不等式性质的旅行售货员问题3309.3.2一般的旅行售货员问题3319.4集合覆盖问题的近似

10、算法3339.5子集和问题的近似算法3369.5.1子集和问题的指数时间算法3369.5.2子集和问题的完全多项式时间近似格式337小结340习题340第10章算法优化策略34510.1算法设计策略的比较与选择34510.1.1最大子段和问题的简单算法34510.1.2最大子段和问题的分治算法34610.1.3最大子段和问题的动态规划算法34810.1.4最大子段和问题与动态规划算法的推广34910.2动态规划加速原理35210.2.1货物