图书介绍
算法设计与分析 第2版pdf电子书版本下载
- 屈婉玲等编 著
- 出版社： 北京：清华大学出版社
- ISBN：9787302424505
- 出版时间：2016
- 标注页数：298页
- 文件大小：40MB
- 文件页数：312页
- 主题词：电子计算机－算法设计－高等学校－教材；电子计算机－算法分析－高等学校－教材
PDF下载
下载说明
算法设计与分析 第2版PDF格式电子书版下载
下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如 BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！
（文件页数 要大于 标注页数，上中下等多册电子书除外）
注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具
图书目录
第1章 基础知识 1
1.1 有关算法的基本概念 1
1.2 算法的伪码描述 5
1.3 算法的数学基础 6
1.3.1 函数的渐近的界 6
1.3.2 求和的方法 10
1.3.3 递推方程求解方法 12
习题1 21
第2章 分治策略 26
2.1 分治策略的基本思想 26
2.1.1 两个熟悉的例子 26
2.1.2 分治算法的一般性描述 27
2.2 分治算法的分析技术 27
2.3 改进分治算法的途径 31
2.3.1 通过代数变换减少子问题个数 31
2.3.2 利用预处理减少递归内部的计算量 34
2.4 典型实例 37
2.4.1 快速排序算法 37
2.4.2 选择问题 40
2.4.3 n—1次多项式在全体2n次方根上的求值 44
习题2 47
第3章 动态规划 52
3.1 动态规划的设计思想 52
3.1.1 多起点、多终点的最短路径问题 52
3.1.2 使用动态规划技术的必要条件 54
3.2 动态规划算法的设计要素 55
3.2.1 子问题的划分和递推方程 56
3.2.2 动态规划算法的递归实现 57
3.2.3 动态规划算法的迭代实现 58
3.2.4 一个简单实例的计算过程 59
3.3 动态规划算法的典型应用 60
3.3.1 投资问题 60
3.3.2 背包问题 63
3.3.3 最长公共子序列LCS 65
3.3.4 图像压缩 68
3.3.5 最大子段和 72
3.3.6 最优二分检索树 75
3.3.7 生物信息学中的动态规划算法 79
习题3 82
第4章 贪心法 87
4.1 贪心法的设计思想 87
4.2 关于贪心法的正确性证明 90
4.3 对贪心法得不到最优解情况的处理 94
4.4 贪心法的典型应用 98
4.4.1 最优前缀码 98
4.4.2 最小生成树 103
4.4.3 单源最短路径 108
习题4 110
第5章 回溯与分支限界 114
5.1 回溯算法的基本思想和适用条件 114
5.1.1 几个典型的例子 114
5.1.2 回溯算法的适用条件 118
5.2 回溯算法的设计步骤 119
5.2.1 回溯算法的递归实现和迭代实现 119
5.2.2 几个典型的例子 120
5.3 回溯算法的效率估计和改进途径 122
5.4 分支限界 124
5.4.1 背包问题 125
5.4.2 最大团问题 127
5.4.3 货郎问题 127
5.4.4 圆排列问题 129
5.4.5 连续邮资问题 131
习题5 132
第6章 线性规划 134
6.1 线性规划模型 134
6.1.1 模型 134
6.1.2 二维线性规划的图解法 137
6.2 标准形 138
6.2.1 标准形基本概念 138
6.2.2 标准形的可行解的性质 140
6.3 单纯形法 142
6.3.1 确定初始基本可行解 143
6.3.2 最优性检验 143
6.3.3 基变换 144
6.3.4 单纯形表 146
6.3.5 人工变量和两阶段法 148
6.3.6 单纯形法的有限终止 154
6.4 对偶性 155
6.4.1 对偶线性规划 155
6.4.2 对偶单纯形法 159
6.5 整数线性规划的分支限界算法 160
习题6 165
第7章 网络流算法 171
7.1 最大流问题 171
7.1.1 网络流及其性质 171
7.1.2 Ford-Fulkerson算法 173
7.1.3 Dinic有效算法 176
7.2 最小费用流 184
7.2.1 Floyd算法 184
7.2.2 最小费用流的负回路算法 186
7.2.3 最小费用流的最短路径算法 188
7.3 运输问题 189
7.3.1 确定初始调运方案 191
7.3.2 改进调运方案 191
7.3.3 表上作业法 193
7.4 二部图匹配 194
7.4.1 二部图的最大匹配 194
7.4.2 赋权二部图的匹配 197
习题7 203
第8章 算法分析与问题的计算复杂度 208
8.1 平凡下界 209
8.2 直接计数求解该问题所需要的最少运算 210
8.3 决策树 211
8.4 检索算法的时间复杂度分析 212
8.5 排序算法的时间复杂度分析 214
8.5.1 冒泡排序算法 214
8.5.2 堆排序算法 215
8.5.3 排序算法的决策树与算法类时间复杂度的下界 220
8.6 选择算法的时间复杂度分析 222
8.6.1 找最大和最小问题 223
8.6.2 找第二大问题 224
8.6.3 找中位数的问题 226
8.7 通过归约确认问题计算复杂度的下界 228
习题8 229
第9章 NP完全性 231
9.1 P类与NP类 231
9.1.1 易解的问题与难解的问题 231
9.1.2 判定问题 233
9.1.3 NP类 235
9.2 多项式时间变换与NP完全性 236
9.2.1 多项式时间变换 236
9.2.2 NP完全性及其性质 238
9.2.3 Cook-Levin定理——第一个NP完全问题 239
9.3 几个NP完全问题 239
9.3.1 最大可满足性与三元可满足性 240
9.3.2 顶点覆盖、团与独立集 241
9.3.3 哈密顿回路与货郎问题 243
9.3.4 恰好覆盖 245
9.3.5 子集和、背包、装箱与双机调度 247
9.3.6 整数线性规划 249
习题9 252
第10章 近似算法 255
10.1 近似算法及其近似比 255
10.2 多机调度问题 256
10.2.1 贪心的近似算法 256
10.2.2 改进的贪心近似算法 257
10.3 货郎问题 258
10.3.1 最邻近法 258
10.3.2 最小生成树法 259
10.3.3 最小权匹配法 260
10.4 背包问题 261
10.4.1 一个简单的贪心算法 261
10.4.2 多项式时间近似方案 261
10.4.3 伪多项式时间算法与完全多项式时间近似方案 262
习题10 264
第11章 随机算法 266
11.1 概率论预备知识 266
11.2 对随机快速排序算法的分析 268
11.3 随机算法的分类及其局限性 270
11.3.1 拉斯维加斯型随机算法 270
11.3.2 蒙特卡洛型随机算法 270
11.3.3 随机算法的局限性 271
11.4 素数检验和多项式恒等检验 271
11.4.1 素数检验 271
11.4.2 多项式恒等检验 272
11.5 随机游动算法 274
11.5.1 有限马氏链及其表示 274
11.5.2 求解二元布尔可满足性问题的随机游动算法 275
习题11 276
第12章 处理难解问题的策略 277
12.1 对问题施加限制 277
12.1.1 二元可满足性问题 278
12.1.2 霍恩公式可满足性问题 279
12.2 固定参数算法 280
12.3 改进指数时间算法 282
12.4 启发式方法 284
12.5 平均情形的复杂性 285
12.6 难解算例生成 287
12.6.1 相变现象与难解性 287
12.6.2 隐藏解的难解算例 289
12.7 基于统计物理的消息传递算法 290
12.7.1 消息传递算法与回溯法、局部搜索算法的比较 290
12.7.2 用消息传递算法求解3SAT问题 291
12.8 量子算法简介 292
12.8.1 量子比特 292
12.8.2 正交测量 293
12.8.3 量子门 294
12.8.4 一个量子算法 295
习题12 297
参考文献 298