算法分析与设计教程 - 21世纪全国应用型本科计算机案例型规划教材 - 中国高校教材图书网
|
|
书名: |
算法分析与设计教程
21世纪全国应用型本科计算机案例型规划教材
|
ISBN: | 978-7-301-23122-7 |
条码: | 9787301231227 |
作者: |
秦明
相关图书
|
装订: | 0 |
印次: | 1-1 |
开本: | 16开 |
定价: |
¥39.00
折扣价:¥37.05
折扣:0.95
节省了1.95元
|
字数: |
351千字
|
出版社: |
北京大学出版社 |
页数: |
252页
|
发行编号: | |
每包册数: |
|
出版日期: |
2019-03-22 |
|
内容简介: |
本书用最通俗的语言深入浅出地介绍一些基本的算法分析理念以及算法设计思想,如,递归算法与分治算法、贪心算法、动态规划、回溯算法、搜索算法,并介绍了其他一些高性能算法,本书是数据结构的后续课程,可作为本科算机相关专业的教材,也可以作为程序开发人员的参考资料。
|
作者简介: |
副教授,硕士,华中科技大学文华学院,全国软件专业人才设计与开发大赛优秀指导教师,主要研究计算机软件和算法
|
章节目录: |
第1章 算法引论 1 1.1 算法的基本概念 2 1.1.1 算法的重要特性 2 1.1.2 算法的基本内容 3 1.2 算法分析 4 1.2.1 计算时间的渐进表示 6 1.2.2 常用的整数求和公式 8 1.2.3 作时空性能分布图 9 1.3 最优算法概述 10 本章小结 10 习题与思考 10 第2章 递归算法与分治算法 11 2.1 递归算法的实现机制 12 2.1.1 递归函数调用的一般形式 12 2.1.2 值的回传 13 2.1.3 递归函数调用的内部操作 14 2.2 递归算法的设计 14 2.3 递归算法转化为非递归算法 20 2.4 递归关系式的计算 24 2.4.1 生成函数及其性质 24 2.4.2 利用生成函数求解递归 关系式 26 2.4.3 k阶常系数线性齐次递归 关系式 29 2.4.4 k阶常系数线性非齐次递归 关系式 31 2.5 分治算法的基本设计原理 33 2.6 分治算法求解二分搜索问题 37 2.7 分治算法求解归并排序问题 41 2.8 分治算法求解快速排序问题 45 2.8.1 数组的划分 46 2.8.2 快速排序算法的实现 47 2.8.3 快速排序算法的最坏 情况分析 48 2.8.4 快速排序算法的平均 情况分析 49 2.9 分治算法求解选择问题 50 2.9.1 选择问题的思想方法 51 2.9.2 选择问题的算法实现 52 2.9.3 关于选择问题的算法分析 54 本章小结 55 课后阅读材料 55 习题与思考 59 第3章 贪心算法 60 3.1 贪心算法的设计思想 62 3.2 贪心算法求解背包问题 63 3.2.1 背包问题贪心算法的 设计思想 64 3.2.2 背包问题贪心算法的分析 66 3.3 贪心算法求解单源点最短路径问题 67 3.3.1 单源点最短路径贪心算法的 设计思想 67 3.3.2 单源点最短路径贪心算法的 实现 68 3.3.3 单源点最短路径贪心算法的 分析 71 3.4 贪心算法求解最小成本生成树问题 71 3.4.1 最小成本生成树问题 71 3.4.2 普里姆(Prim)算法的 实现过程 72 3.4.3 普里姆算法的分析 75 3.4.4 克鲁斯卡尔算法的思想方法 76 3.4.5 集合的树表示和不相交集合 的合并--树结构应用实例 76 3.4.6 克鲁斯卡尔算法的实现过程 79 3.4.7 克鲁斯卡尔算法的分析 81 本章小结 82 课后阅读材料 82 习题与思考 88 第4章 动态规划算法 90 4.1 动态规划算法的设计思想 91 4.2 多段图的最小成本问题 93 4.2.1 多段图的决策过程 94 4.2.2 多段图模型动态规划算法的 具体实现 96 4.2.3 多段图模型的求解实例 97 4.3 资源分配问题 99 4.3.1 资源分配方案的决策过程 100 4.3.2 动态规划算法求解资源 分配问题的实现 103 4.4 0/1背包问题 105 4.4.1 0/1背包问题的求解过程 105 4.4.2 0/1背包问题的动态 规划算法 107 4.5 最长公共子序列问题 108 4.5.1 最长公共子序列的 搜索过程 109 4.5.2 最长公共子序列的动态 规划算法实现 111 本章小结 113 课后阅读材料 113 习题与思考 120 第5章 回溯算法 123 5.1 回溯算法的设计思想 124 5.2 回溯算法的设计框架 128 5.3 0/1背包问题 131 5.3.1 回溯算法求解0/1背包 问题的求解过程 131 5.3.2 回溯算法求解0/1背包 问题的算法实现 134 5.4 装箱问题 137 5.4.1 装箱问题实现 137 5.4.2 递归回溯算法设计 138 5.4.3 上界函数 139 5.4.4 迭代回溯算法设计 142 5.5 最大通信团体问题 144 5.5.1 最大团体问题的描述及 求解思路 144 5.5.2 最大通信团体问题的描述及 求解思路 144 本章小结 148 课后阅读材料 148 习题与思考 151 第6章 随机化算法 154 6.1 随机化算法引言 155 6.1.1 随机化算法的分类 156 6.1.2 随机数产生器 156 6.2 谢伍德算法 157 6.2.1
|
精彩片段: |
|
书 评: |
|
其 它: |
|
|
|