算法设计与分析PDF电子书下载
- 电子书积分:10 积分如何计算积分?
- 作 者:屈婉玲,张立昂,王捍贫等编著
- 出 版 社:北京:清华大学出版社
- 出版年份:2011
- ISBN:9787302247562
- 页数:219 页
第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章 分治策略 25
2.1 分治策略的基本思想 25
2.1.1 两个熟悉的例子 25
2.1.2 分治算法的一般性描述 26
2.2 分治算法的分析技术 26
2.3 改进分治算法的途径 30
2.3.1 通过代数变换减少子问题个数 30
2.3.2 利用预处理减少递归内部的计算量 33
2.4 典型实例 36
2.4.1 快速排序算法 36
2.4.2 选择问题 39
2.4.3 n—1次多项式在全体2n次方根上的求值 43
习题2 46
第3章 动态规划 51
3.1 动态规划的设计思想 51
3.1.1 多起点、多终点的最短路径问题 51
3.1.2 使用动态规划技术的必要条件 53
3.2 动态规划算法的设计要素 54
3.2.1 子问题的划分和递推方程 55
3.2.2 动态规划算法的递归实现 56
3.2.3 动态规划算法的迭代实现 57
3.2.4 一个简单实例的计算过程 58
3.3 动态规划算法的典型应用 59
3.3.1 投资问题 59
3.3.2 背包问题 61
3.3.3 最长公共子序列LCS 64
3.3.4 图像压缩 67
3.3.5 最大子段和 71
3.3.6 最优二分检索树 74
3.3.7 生物信息学中的动态规划算法 78
习题3 81
第4章 贪心法 85
4.1 贪心法的设计思想 85
4.2 关于贪心法的正确性证明 88
4.3 对贪心法得不到最优解情况的处理 92
4.4 贪心法的典型应用 96
4.4.1 最优前缀码 96
4.4.2 最小生成树 101
4.4.3 单源最短路径 106
习题4 108
第5章 回溯与分支限界 112
5.1 回溯算法的基本思想和适用条件 112
5.1.1 几个典型的例子 112
5.1.2 回溯算法的适用条件 116
5.2 回溯算法的设计步骤 117
5.2.1 回溯算法的递归实现和迭代实现 117
5.2.2 几个典型的例子 118
5.3 回溯算法的平均效率和改进途径 120
5.4 分支限界 122
5.4.1 背包问题 123
5.4.2 最大团问题 125
5.4.3 货郎问题 125
5.4.4 圆排列问题 127
5.4.5 连续邮资问题 129
习题5 130
第6章 算法分析与问题的计算复杂度 132
6.1 平凡下界 133
6.2 直接计数求解该问题所需要的最少运算 134
6.3 决策树 135
6.4 检索算法的时间复杂度分析 136
6.5 排序算法的时间复杂度分析 138
6.5.1 冒泡排序算法 138
6.5.2 堆排序算法 139
6.5.3 排序算法的决策树与算法类时间复杂度的下界 144
6.6 选择算法的时间复杂度分析 146
6.6.1 找最大和最小问题 147
6.6.2 找第二大问题 148
6.6.3 找中位数的问题 150
6.7 通过归约确认问题计算复杂度的下界 152
习题6 153
第7章 NP完全性 155
7.1 P类与NP类 155
7.1.1 易解的问题与难解的问题 155
7.1.2 判定问题 157
7.1.3 NP类 159
7.2 多项式时间变换与NP完全性 160
7.2.1 多项式时间变换 160
7.2.2 NP完全性 162
7.2.3 Cook-Levin定理——第一个NP完全问题 163
7.3 几个NP完全问题 163
7.3.1 最大可满足性与三元可满足性 163
7.3.2 顶点覆盖、团与独立集 165
7.3.3 哈密顿回路与货郎问题 167
7.3.4 恰好覆盖 169
7.3.5 子集和、背包、装箱与双机调度 171
习题7 174
第8章 近似算法 176
8.1 近似算法及其近似比 176
8.2 多机调度问题 177
8.2.1 贪心的近似算法 177
8.2.2 改进的贪心近似算法 178
8.3 货郎问题 179
8.3.1 最邻近法 179
8.3.2 最小生成树法 180
8.3.3 最小权匹配法 181
8.4 背包问题 182
8.4.1 一个简单的贪心算法 182
8.4.2 多项式时间近似方案 182
8.4.3 伪多项式时间算法与完全多项式时间近似方案 183
习题8 185
第9章 随机算法 187
9.1 概率论预备知识 187
9.2 对随机快速排序算法的分析 189
9.3 随机算法的分类及其局限性 191
9.3.1 拉斯维加斯型随机算法 191
9.3.2 蒙特卡洛型随机算法 191
9.3.3 随机算法的局限性 192
9.4 素数检验和多项式恒等检验 193
9.4.1 素数检验 193
9.4.2 多项式恒等检验 194
9.5 随机游动算法 195
9.5.1 有限马氏链及其表示 195
9.5.2 求解二元布尔可满足性问题的随机游动算法 196
习题9 197
第10章 处理难解问题的策略 198
10.1 对问题施加限制 198
10.1.1 二元可满足性问题 199
10.1.2 霍恩公式可满足性问题 200
10.2 固定参数算法 201
10.3 改进指数时间算法 203
10.4 启发式方法 205
10.5 平均情形的复杂性 206
10.6 难解算例生成 208
10.6.1 相变现象与难解性 208
10.6.2 隐藏解的难解算例 210
10.7 基于统计物理的消息传递算法 211
10.7.1 消息传递算法与回溯法、局部搜索算法的比较 211
10.7.2 基于统计物理的消息传递算法 212
10.8 量子算法简介 213
10.8.1 量子比特 213
10.8.2 正交测量 214
10.8.3 量子门 215
10.8.4 一个量子算法 216
习题10 218
参考文献 219
- 《水面舰艇编队作战运筹分析》谭安胜著 2009
- 《分析化学》陈怀侠主编 2019
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《设计十六日 国内外美术院校报考攻略》沈海泯著 2018
- 《影响葡萄和葡萄酒中酚类特征的因素分析》朱磊 2019
- 《计算机辅助平面设计》吴轶博主编 2019
- 《高校转型发展系列教材 素描基础与设计》施猛责任编辑;(中国)魏伏一,徐红 2019
- 《仪器分析技术 第2版》曹国庆 2018
- 《景观艺术设计》林春水,马俊 2019
- 《全国普通高等中医药院校药学类专业十三五规划教材 第二轮规划教材 分析化学实验 第2版》池玉梅 2018
- 《市政工程基础》杨岚编著 2009
- 《家畜百宝 猪、牛、羊、鸡的综合利用》山西省商业厅组织技术处编著 1959
- 《《道德经》200句》崇贤书院编著 2018
- 《高级英语阅读与听说教程》刘秀梅编著 2019
- 《计算机网络与通信基础》谢雨飞,田启川编著 2019
- 《看图自学吉他弹唱教程》陈飞编著 2019
- 《法语词汇认知联想记忆法》刘莲编著 2020
- 《培智学校义务教育实验教科书教师教学用书 生活适应 二年级 上》人民教育出版社,课程教材研究所,特殊教育课程教材研究中心编著 2019
- 《国家社科基金项目申报规范 技巧与案例 第3版 2020》文传浩,夏宇编著 2019
- 《流体力学》张扬军,彭杰,诸葛伟林编著 2019
- 《大学计算机实验指导及习题解答》曹成志,宋长龙 2019
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《大学生心理健康与人生发展》王琳责任编辑;(中国)肖宇 2019
- 《大学英语四级考试全真试题 标准模拟 四级》汪开虎主编 2012
- 《大学英语教学的跨文化交际视角研究与创新发展》许丽云,刘枫,尚利明著 2020
- 《北京生态环境保护》《北京环境保护丛书》编委会编著 2018
- 《复旦大学新闻学院教授学术丛书 新闻实务随想录》刘海贵 2019
- 《大学英语综合教程 1》王佃春,骆敏主编 2015
- 《大学物理简明教程 下 第2版》施卫主编 2020
- 《指向核心素养 北京十一学校名师教学设计 英语 九年级 上 配人教版》周志英总主编 2019