《计算机算法设计与分析》PDF下载

  • 购买积分:12 如何计算积分?
  • 作  者:郑丽英,孟昱煜,王海涌等编著
  • 出 版 社:北京:中国铁道出版社
  • 出版年份:2009
  • ISBN:9787113096298
  • 页数:302 页
图书介绍:本书以算法设计策略为知识单元,围绕算法设计的基本方法,对计算机应用领域中许多常用的非数值算法作了系统的描述,并分析了这些算法所需的时间和空间。全书共分十三章,前七章介绍了递归技术、分治法、贪心法、动态规划、回溯法及分支限界等基本设计方法,第八到十一章介绍NP完全理论和NP难问题、近似算法、字符串匹配、概率算法的相关知识,第十二、十三章则对近年来广泛受到关注的网络路由算法及生物信息算法的基本设计方法作了介绍。书中既涉及传统算法的实例分析,更有算法领域热点研究课题追踪,具有较高的实用价值。

第一章 导论 1

第一节 算法与程序 1

第二节 算法的描述 4

第三节 算法的评价与优化 5

第四节 算法的复杂度 7

习题 17

第二章 递归技术 19

第一节 递归过程 19

第二节 递归技术 20

第三节 递归过程的实现 24

第四节 递归函数 25

第五节 递归方程 26

第六节 递归方程求解 28

第七节 递归消除 37

习题 43

第三章 分治策略 44

第一节 分治法的基本思想 44

第二节 二分搜索技术 46

第三节 大整数的乘法 47

第四节 Strassen矩阵乘法 49

第五节 棋盘覆盖 50

第六节 合并排序 53

第七节 快速排序 55

第八节 找最大和最小元素 58

习题 61

第四章 动态规划 62

第一节 一般方法 62

第二节 矩阵连乘问题 63

第三节 动态规划算法的基本要素 68

第四节 最长公共子序列 72

第五节 最大子段和 76

第六节 电路布线 83

第七节 流水作业调度 86

第八节 0-1背包问题 89

第九节 整数规划问题 95

第十节 流动推销员(或旅行商)问题 102

习题 107

第五章 贪心法 109

第一节 引言 109

第二节 背包问题 111

第三节 最小生成树 113

第四节 单源最短路径问题 117

第五节 文件存储问题 120

第六节 有期限的任务安排问题 123

习题 124

第六章 回溯法 126

第一节 回溯法的一般方法 126

第二节 n皇后问题 132

第三节 图的着色问题 136

第四节 流水作业车间调度 139

第五节 装载问题 141

第六节 0-1背包问题 149

第七节 马的遍历问题 152

习题 154

第七章 分支限界法 156

第一节 分支限界法的基本思想 157

第二节 旅行推销员问题 159

第三节 单源最短路径问题 167

第四节 布线问题 170

第五节 0-1背包问题 175

第六节 装载问题 180

习题 188

第八章 P、NP和NP完全问题 190

第一节 引言 190

第二节 确定型图灵机及P 191

第三节 非确定型图灵机及NP 196

第四节 可满足性问题及Cook定理 199

第五节 若干NP完全问题及NP难题 202

第六节 近似算法 210

习题 217

第九章 字符串匹配 218

第一节 简单的字符串匹配算法 218

第二节 Knuth-Morris-Pratt串匹配算法 219

第三节 Boyer-Moore串匹配算法 223

第四节 Karp-Rabin串匹配算法 226

第五节 允许k-差别的近似串匹配算法 228

习题 231

第十章 网络路由算法 232

第一节 网络路由的概念 232

第二节 LS路由算法 234

第三节 DV路由算法 236

第四节 分层路由 238

第五节 无QoS约束的组播路由算法 240

第六节 基于时延约束的组播路由算法 241

第七节 无线移动通信网络的路由算法 242

习题 248

第十一章 随机算法 249

第一节 随机算法的一般性原理 249

第二节 应用 253

第三节 随机算法的性能分布 262

习题 264

第十二章 概率算法·数论算法·计算几何 265

第一节 概率算法 265

第二节 随机数与素数测试 267

第三节 数论算法 269

第四节 线段问题 271

第五节 凸包 276

习题 278

第十三章 生物信息处理算法 280

第一节 DNA计算的基本原理与模型及算法 280

第二节 基因的基本结构 284

第三节 生物信息数据库与查询 285

第四节 生物序列比对模型及算法 289

习题 300

参考文献 302