现代算法设计与分析 大中专理科计算机 (印)桑迪普·森,(印)阿米特·库玛尔
关注算法领域的新概念、新方法和新应用,强调计算模型和计算环境,充分利用概率分析和化技术
¥
56.75
5.7折
¥
99
全新
库存3件
作者(印)桑迪普·森,(印)阿米特·库玛尔
出版社机械工业出版社
ISBN9787111679554
出版时间2021-06
版次1
装帧平装
开本16
页数276页
定价99元
货号315_9787111679554
上书时间2024-10-19
商品详情
- 品相描述:全新
-
正版特价新书
- 商品描述
-
目录:
出版者的话
译者序
前言
致谢
章模型与分析1
1.1计算斐波那契数1
1.2快速乘法3
1.3计算模型3
1.4算法简介4
1.4.1另一种算法6
1.5其他计算模型8
1.5.1外部存储器模型8
1.5.2并行模型8
拓展阅读10
题10
第2章概率基础与尾部不等式13
2.1概率基础13
2.2尾部不等式17
2.3生成数20
2.3.1生成具有任意分布的变量21
2.3.2由顺序文件生成变量21
2.3.3生成置换23
拓展阅读25
题25
第3章热身问题27
3.1计算大公因子的欧几里得算法27
3.1.1扩展欧几里得算法27
3.1.2在密码学中的应用28
3.2寻找第k小的元素28
3.2.1选择的划分元29
3.2.2中位数的中位数30
3.3词的排序32
3.4可归并的堆34
3.4.1归并二项堆35
3.5一个简单的半动态词典35
3.5.1势能法与摊分析36
3.6下界37
拓展阅读39
题39
第4章优化ⅰ:蛮力法与贪婪策略42
4.1启发式搜索方法42
4.1.1博弈树44
4.2贪婪算法的框架46
4.2.1大支撑树49
4.2.2寻找小权值子集49
4.2.3一个调度问题50
4.3小支撑树算法的高效数据结构51
4.3.1并查集的一种简单数据结构52
4.3.2更快的方案53
4.3.3增长慢的函数54
4.3.4整合55
4.3.5仅做道路压缩56
4.4其他不同形式的贪婪策略57
4.5与贪婪策略的折中58
4.6梯度下降59
4.6.1应用63
拓展阅读65
题66
第5章优化ⅱ:动态规划69
5.1背包问题70
5.2上下文无关文法的解析71
5.3长单调子序列72
5.4函数逼近74
5.5大似然估计的viterbi算法75
5.6树中的大权独立集76
拓展阅读76
题77
第6章查找80
6.1跳表——一个简单的字典80
6.1.1跳表的构造80
6.1.2分析81
6.1.3更强的尾部估计82
6.2树堆:查找树83
6.3全域哈希86
6.3.1全域哈希函数的存在88
6.4哈希函数88
6.4.1将期望界转换为差情况的界89
6.5一个复杂度为loglogn的优先级队列89
拓展阅读91
题92
第7章多维查找与几何算法94
7.1区间树与范围树94
7.1.1一维范围查找94
7.1.2二维范围查找96
7.2kd树97
7.3优先级查找树99
7.4面凸包101
7.4.1jarvismarch算法102
7.4.2graham扫描算法102
7.4.3排序与凸包103
7.5快速凸包算法104
7.5.1分析105
7.5.2期望运行时间106
7.6使用持久化数据结构的点定位107
7.7增量构造法109
拓展阅读111
题111
第8章字符串匹配与指纹函数114
8.1rabinkarp指纹字符串查找算法114
8.2kmp算法117
8.2.1kmp算法的分析120
8.2.2模式分析120
8.3字典树及其应用121
拓展阅读123
题123
第9章快速傅里叶变换及其应用125
9.1多项式求值与插值125
9.1.1多项式相乘126
9.2cooleytukey算法126
9.3蝶形网络128
9.4schonagestrassen快速乘法算法129
9.5广义字符串匹配131
9.5.1基于卷积的方法131
拓展阅读133
题133
0章图算法135
10.1深度优先搜索135
10.2深度优先搜索的应用138
10.2.1强连通分支138
10.2.2双连通分支140
10.3道路问题142
10.3.1bellmanford单源短道路算法143
10.3.2dijkstra单源短道路算法143
10.3.3任意两点之间的短道路算法145
10.4计算赋权图中的支撑子145
10.5全局小割148
10.5.1收缩算法149
10.5.2小割的概率149
拓展阅读150
题151
1章大流及其应用153
11.1大流的质与算法155
11.1.1大流与小割155
11.1.2fordfulkerson算法156
11.1.3edmondkarp可增广道路策略157
11.1.4单调引理及迭代次数的界158
11.2大流的应用159
11.2.1边不相交的道路159
11.2.2二部图的匹配159
11.2.3环流问题162
11.2.4项目规划164
拓展阅读165
题165
2章np与近似算法168
12.1分类与可归约170
12.2cooklevin定理172
12.3常见的np问题173
12.4np的证明175
12.4.1顶点覆盖及相关问题175
12.4.2图的3着问题176
12.4.3背包问题及相关问题177
12.5其他重要的复杂度类179
12.6使用近似算法处理困难181
12.6.1大背包问题182
12.6.2小集合覆盖183
12.6.3几何旅行商问题184
12.6.43着问题185
12.6.5大割问题185
拓展阅读186
题186
3章降维188
13.1投影与johnsonlindenstrauss引理188
13.2高斯消元法191
13.3奇异值分解及其应用192
13.3.1矩阵代数与svd定理192
13.3.2使用svd的低秩近似194
13.3.3低秩近似的应用196
13.3.4聚类问题197
13.3.5svd定理的证明199
拓展阅读200
题200
4章并行算法201
14.1并行计算模型201
14.2排序和比较问题202
14.2.1寻找大值202
14.2.2排序204
14.3并行前缀208
14.4基本的图算法212
14.4.1列表排名212
14.4.2连通分支214
14.5基本的几何算法216
14.6并行模型之间的关系217
14.6.1网格上的路由218
拓展阅读220
题220
5章层次化存储结构及高速缓存223
15.1层次化存储模型223
15.2矩阵转置224
15.2.1矩阵乘法225
15.3在外部存储器中进行排序226
15.3.1我们可以改进这个算法吗227
15.4高速缓存参数无关的算法设计228
15.4.1参数无关的矩阵转置229
拓展阅读231
题232
6章流数据模型233
16.1引言233
16.2查找流中的频繁元素233
16.3流中的相异元素236
16.4频数矩问题及其应用238
16.4.1均值的中位数241
16.4.2二阶频数矩的特例241
16.5流模型下界的证明243
拓展阅读244
题245
附录a递推关系与生成函数247
参文献253
内容简介:
本书不仅讲解传统的算法设计策略和,而且关注算法领域不断涌现的新概念、新方法和新应用,帮助读者把握技术热点及发展趋势。书中引入了降维技术、并行算法、算法、层次化存储结构算法和流算法等新内容,大量使用概率分析和化技术,并包含众多新颖的示例,特别是强调计算模型和计算环境,不再局限于理想化的存取机模型。全书内容简洁明快,并配有丰富的题和拓展阅读资料,适合作为高等院校计算机相关专业的教材,也适合业界技术人员阅读参。
作者简介:
作者简介桑迪普?森(andeep en) 印度理工学院德里分校计算机科学与工程系教授,印度科学院院士,印度科学院院士,研究领域包括算法、计算几何、动态图算法和计算模型等。曾在ibm研究实验室、微软研究实验室、北卡罗莱纳大学教堂山分校等机构担任访问研究员。阿米特?库玛尔(amit kumar) 印度理工学院德里分校计算机科学与工程系教授,印度科学院院士,研究领域包括组合优化、调度、图论和聚类等。曾任职于贝尔实验室,并曾在微软印度研究院和ibm印度研究院担任访问教授。曾荣获2018年印度hanti warup bhtanagar数学科学奖。译者简介刘铎 于清华大学计算机科学与技术系获工学博士,现为北京交通大学软件学院副教授。主要研究方向为应用密码学、信息安全、组合算法的设计与分析。主持和参与、省部级科研项目多项,以作者身份在各类重要刊物和会议上发表20余篇,目前主持建设并讲授的“离散数学”课程被评为首批(线上)本科课程。
— 没有更多了 —
以下为对购买帮助不大的评价