包邮算法设计导论

**部分 基础知识 第1章 算法设计的基础 1 1.1 算法的基本概念 1 1.1.1 算法的定义和特征 1 1.1.2 算法设计实例 3 1.2 算法的伪代码描述 6 1.2.1 伪代码的定义 6 1.2.2 算法的伪代码实例描述 6 1.3 算法复杂度分析 7 1.3.1 时间复杂度分析 7 1.3.2 空间复杂度分析 10 1.4 学习和研究算法的原因 12 1.4.1 算法在问题求解中的地位 13 1.4.2 算法训练能够提高计算思维能力 15 1.4.3 算法设计的基本步骤 16 习题1 17 第2章 算法的数学基础 19 2.1 常用的函数和公式 19 2.1.1 整数函数 19 2.1.2 对数函数 20 2.1.3 排列、组合和二项式系数 20 2.1.4 级数求和 21 2.2 求解递归方程 22 2.2.1 用特征方程求解递归方程 22 2.2.2 用递归树方法求解递归方程 25 2.3 用递推方法求解递归方程 26 2.3.1 递推 26 2.3.2 用递推法求解变系数递归方程 27 2.3.3 换名 28 习题2 30 第3章 排序问题的操作 33 3.1 基于堆的排序 33 3.1.1 堆的定义 33 3.1.2 堆的操作 34 3.1.3 堆的建立 38 3.1.4 堆的排序 40 3.2 基数排序 41 3.2.1 基数排序算法的思想方法 41 3.2.2 基数排序算法的实现 43 3.2.3 基数排序算法的分析 45 3.3 合并排序 46 3.3.1 合并排序算法的实现 46 3.3.2 合并排序算法的分析 48 3.4 选择排序 49 3.5 起泡排序 50 习题3 51 第二部分 基本算法设计 第4章 递归与分治 53 4.1 基于归纳的递归算法 53 4.1.1 归纳的设计思想 53 4.1.2 递归算法的示例分析 54 4.1.3 递归在排列中的应用 56 4.1.4 整数划分问题 57 4.2 分治法 59 4.2.1 分治法的设计思想 59 4.2.2 快速排序和归并排序的分析 60 4.2.3 多项式乘积的分治算法 65 4.2.4 平面点集的*接近点对问题 68 4.2.5 棋盘覆盖问题 73 习题4 76 第5章 贪婪法 77 5.1 贪婪法的设计思想 77 5.2 背包问题 78 5.2.1 背包问题贪婪法的实现 79 5.2.2 背包问题贪婪法的分析 80 5.3 *小生成树问题 81 5.3.1 *小生成树引言 81 5.3.2 克鲁斯卡尔算法 82 5.3.3 普里姆算法 87 5.4 *短路径问题 90 5.4.1 解*短路径的狄斯奎诺算法 91 5.4.2 狄斯奎诺算法的实现与分析 92 5.5 图的着色问题 94 习题5 96 第6章 动态规划 98 6.1 动态规划的示例——货郎担问题 98 6.2 多段图的动态规划法 100 6.2.1 多段图的*短路径问题 100 6.2.2 多源点*短路径问题 103 6.3 *长公共子序列问题 105 6.3.1 *长公共子序列的搜索问题 105 6.3.2 *长递增子序列问题 108 6.4 资源分配问题 110 6.4.1 资源分配策略 110 6.4.2 资源分配算法的实现 113 6.5 0/1背包问题 115 6.6 查找问题中的*优二叉查找树 118 习题6 120 第三部分 基于搜索的算法设计 第7章 回溯法 122 7.1 回溯法的设计思想 122 7.1.1 问题的解空间 122 7.1.2 回溯法的设计思想 123 7.2 图的回溯法 124 7.2.1 图的着色问题的求解 124 7.2.2 哈密尔顿回路的求解 128 7.3 n后问题 130 7.3.1 4后问题的求解 130 7.3.2 8后问题的求解 131 7.4 批处理作业调度问题 133 习题7 134 第8章 分支与限界 136 8.1 分支与限界的设计思想 136 8.2 0/1背包问题 137 8.3 *大团问题 139 8.4 货郎担问题 140 8.5 圆排列问题 141 8.6 连续邮资问题 144 习题8 145 第四部分 算法的限制 第9章 随机算法 147 9.1 随机算法的设计思想 147 9.2 舍伍德随机算法 148 9.2.1 随机快速排序 149 9.2.2 随机选择算法 150 9.3 拉斯维加斯算法 152 9.3.1 8后问题 152 9.3.2 整数因子问题 153 9.4 蒙特卡罗算法 155 9.4.1 主元素问题 155 9.4.2 素数测试问题 157 习题9 159 第10章 NP完全问题与近似算法 161 10.1 P类和NP类问题 161 10.1.1 P类问题 161 10.1.2 NP类问题 162 10.2 NP完全问题 163 10.2.1 NP完全问题的定义 164 10.2.2 典型的NP完全问题 165 10.2.3 NP问题的求解 171 10.3 近似算法概述 171 10.3.1 近似算法的设计思想 171 10.3.2 近似算法的性能 172 10.4 图中的近似问题 173 10.4.1 顶点覆盖 173 10.4.2 *短路径问题 175 10.5 多项式的近似求解 177 10.5.1 0/1背包问题的多项式 近似方案求解 177 10.5.2 子集求和问题的完全多项式 近似方案求解 180 习题10 182 第11章 专用算法设计技术 184 11.1 数据压缩算法 184 11.1.1 数据压缩概述 184 11.1.2 无损压缩算法 186 11.1.3 有损压缩算法 193 11.2 数据加密算法 199 11.2.1 数据加密概述 200 11.2.2 传统加密算法 200 11.2.3 非对称加密算法 205 11.3 遗传算法 208 11.3.1 遗传算法概述 208 11.3.2 遗传算法 215 11.3.3 TSP问题 215 习题11 222 参考文献 223