没有合适的资源?快使用搜索试试~ 我知道了~
首页《算法设计与分析:现代视角》- 探索多模态计算与性能优化
《算法设计与分析:现代视角》- 探索多模态计算与性能优化
需积分: 10 11 下载量 201 浏览量
更新于2024-07-17
收藏 3.21MB PDF 举报
"《算法设计与分析:一种现代观点》是一本由Sandeep Sen和Amit Kumar合著的专业教材,由剑桥大学出版社于2019年出版。本书的独特之处在于它不仅沿袭了传统的随机存取机模型下的基础算法讨论和设计方法,还扩展了计算范式的探讨,涵盖了并行计算、缓存敏感设计、流式算法等多个主题。作者强调了这些计算环境在算法设计中的关键作用,通过引入新的性能度量和匹配的下界论证,使内容更加严谨。 书中特别关注了贪心算法、分治策略和动态规划的重要性,这些经典技术被应用于近似算法中,并提供了带有保证的解决方案。作者鼓励读者广泛运用概率分析和随机化技术,这些技术在近年来该领域的许多突破中起到了决定性作用。这反映出算法设计的现代视角更注重结合概率论和随机性来优化问题求解。 此外,书中还包含了一章关于维度降低的技术,这是数据挖掘和统计分析中许多有趣应用的核心,对于处理高维数据和复杂模式识别至关重要。这种技术能够帮助我们在海量数据中提取关键信息,提高计算效率。 《算法设计与分析:一种现代观点》不仅覆盖了广泛的算法类型,而且深入探讨了算法设计背后的理论基础和实际应用,适合对算法有深入理解需求的学生和专业人员研读,有助于他们跟上当代算法研究的前沿趋势。"
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/11305561/bg11.jpg)
Figures
1.1 Algorithm for verifying matrix product 9
2.1 Generating a random permutation of n distinct objects 29
3.1 Euclid’s algorithm 35
3.2 Algorithm based on median of medians 40
3.3 (a) Recursive construction of binomial tree; (b) Binomial heap of 11
elements consisting of three binomial trees 44
4.1 Illustration of the induction proof when root node is
W
59
4.2 Algorithm Gen Greedy 61
4.3 The matching (a,d) is a maximal independent set, but (a,b), (c,d) is a larger
maximal independent set 63
4.4 Kruskal’s minimum spanning tree algorithm 64
4.5 Successive iterations in Kruskal’s greedy algorithm 67
4.6 An example of a Union–Find data structure storing elements {1,2,. .., 12} 69
4.7 An example of a path compression heuristic 70
4.8 Prim’s minimum spanning tree algorithm 74
4.9 Boruvka’s minimum spanning tree algorithm 76
4.10 A convex function of one variable 78
4.11 Gradient descent algorithm 80
4.12 The convex function is non-differentiable at x 82
4.13 The point P should ideally lie on the intersection of the three circles, but
there are some measurement errors 83
4.14 A perceptron with inputs x
1
,x
2
,. . .,x
n
and output determined by the sign of
w
0
+ w
1
x
1
+ . .. + w
n
x
n
84
![](https://csdnimg.cn/release/download_crawler_static/11305561/bg12.jpg)
xvi Figures
4.15 A plot of the function g as an approximation to the sgn function 85
4.16 The points in P are denoted by dots, and those in N by squares 86
5.1 Recursive Fibonacci sequence algorithm 93
5.2 The recursive unfolding of computing F
6
93
5.3 Table (a) implies that the string aba does not belong to the grammar
whereas Table (b) shows that baaba can be generated from S 96
5.4 In (a), the constant function is an average of the y values which minimizes
the sum of squares error. In (b), a 3 step function approximates the 7 point
function 99
5.5 For the label aba and starting vertex v
1
, there are several possible labeled
paths like [v
1
,v
3
,v
4
,v
6
],[v
1
,v
4
,v
5
,v
6
], etc. 101
5.6 In the sequence 13, 5, 8, 12, 9, 14, 15, 2 we have predefined the tree structure
but only the first four numbers have been scanned, i.e., 13, 5, 8, 12 104
6.1 The path traversed while searching for the element 87 111
6.2 Diagrams (a) to (d) depict the rotations required to insert the element 20
having priority 58 starting with the treap for the first four elements.
Diagram (e) is the final tree after the entire insertion sequence. Diagram (f)
shows the schematic for left/right rotations 117
6.3 The shaded leaf nodes correspond to the subset S 123
7.1 The structure of a one-dimensional range search tree where a query interval
is split into at most 2logn disjoint canonical (half)-intervals 130
7.2 The rectangle is the union of the slabs represented by the darkened nodes
plus an overhanging left segment containing p
6
132
7.3 Rectangular range query used in a k–d tree 133
7.4 Each rectangular subdivision corresponds to a node in the k–d tree and is
labeled by the splitting axis – either vertical or horizontal 134
7.5 The query is the semi-infinite upper slab supported by the two bottom
points (0, 4.5) and (10, 4.5) 137
7.6 The figure on the left is convex, whereas the one on the right is not convex 137
7.7 Convex hull of points shown as the shaded region 138
7.8 Jarvis March algorithm for convex hull 140
7.9 Merging upper hulls 141
7.10 Left turn(p
m
, p
2 j−1
, p
2 j
) is true but slope(p
2 j−1
p
2 j
) is less than the median
slope given by L 144
7.11 The shaded vertical region does not contain any intersection points 147
7.12 An example depicting Ω(n
2
) space complexity for n segments 149
7.13 Path copying technique on adjacent slabs s
5
and s
6
149
7.14 Incremental algorithm for closest pair computation 150
![](https://csdnimg.cn/release/download_crawler_static/11305561/bg13.jpg)
Figures xvii
7.15 Maximum number of D-separated points per cell is 4 and the shaded area
is the region within which a point can lie with distance less than D from p 152
8.1 Testing equality of two large numbers 159
8.2 Karp–Rabin string matching algorithm 160
8.3 Knuth–Morris–Pratt string matching algorithm 164
8.4 The suffix tree construction corresponding to the string catca $: (i) Suffix a
starting at position 5, (ii) Suffixes at position 4 and 5, etc. 167
9.1 FFT computation 174
9.2 Computing an eight point FFT using a butterfly network 176
9.3 Matching with wildcards: The pattern is X = 3 2 1 ∗ and r
1
= 6,r
2
= 4,r
3
=
11,r
4
= 0 all chosen from [1.. .16] corresponding to p = 17 182
10.1 Algorithm for Depth First Search 186
10.2 The pair of numbers associated with each vertex denotes the starting time
and finishing time respectively as given by the global counter 187
10.3 The pair of numbers associated with the vertices represent the start and
finish time of the DFS procedure 189
10.4 Finding strongly connected components using two DFS 190
10.5 The component graph for the graph on the left is shown on the right 192
10.6 Bellman–Ford single-source shortest path problem 194
10.7 For every vertex, the successive labels over the iterations of the
Bellman–Ford algorithm are indicated where i denotes ∞ 196
10.8 Dijkstra’s single source shortest path algorithm 196
10.9 An algorithm for weighted 3-spanner 199
10.10 The 3-spanner algorithm – Stages 1 and 2 200
10.11 Stretch bound: (i) Intracluster; (ii) Intercluster 201
10.12 Algorithm for computing t-partition 202
11.1 Greedy algorithm for max-flow: it may not give optimal solution 211
11.2 Example of residual graph 211
11.3 Example of disjoint paths in a graph 217
11.4 Reduction from a matching instance on the left to a max-flow instance on
the right 218
11.5 The matching M is shown by dotted edges 220
11.6 Illustration of Hall’s theorem 221
11.7 The shaded region consisting of s,A,C,D,E,F represents a min s-t cut of
capacity 3 222
11.8 Example of circulation on the left 223
11.9 Figure on the left shows an example of DAG on a set of tasks 225
11.10 Figure for Exercise 11.3. Numbers denote edge capacities 227
12.1 Many-to-one reduction from Π
1
to Π
2
by using a function f : N → N 234
![](https://csdnimg.cn/release/download_crawler_static/11305561/bg14.jpg)
xviii Figures
12.2 Graph illustrating the reduction for the 3-CNF formula 242
12.3 Illustration of the reduction proving NP-completeness of the three coloring
problem. 243
13.1 Gaussian elimination algorithm 263
13.2 A two-dimensional illustration of the SVD subspace V
1
of points
represented by circular dots, where V
1
denotes the subspace spanned by
the first column of V 273
14.1 Parallel odd–even transposition sort 282
14.2 Sorting two rows by alternately sorting rows and columns 284
14.3 Shearsort algorithm for a rectangular mesh 285
14.4 Partition sort in parallel 285
14.5 Parallel prefix computation: this procedure computes prefix of x
a
,x
a+1
,
.. . ,x
b
287
14.6 Parallel prefix computation using blocking 289
14.7 Recursive unfolding of the prefix circuit with 8 inputs in terms of 4-input
and 2-input circuits 289
14.8 Parallel list ranking 292
14.9 The star rooted at vertex 5 is connected to all the stars (dotted edges) on the
right that have higher numbered vertices 296
14.10 Parallel connectivity: We assume that there is a processor assigned to every
vertex v ∈V and to every edge (u,w) ∈ E 297
14.11 Starting from (r, c), the packet is routed to a random row r
0
within the same
column c 303
15.1 The tiling of a p ×q matrix in a row-major layout 310
15.2 Transposing a matrix using minimal transfers 311
15.3 Computing the product Z = X ·Y using tiles of size s 312
15.4 Searching a dictionary in external memory 316
15.5 Consider numbers from 1 to 16 arranged according to the Algorithm in
Fig. 15.4 316
15.6 Algorithm for matrix transpose 317
15.7 Base case: Both A,B fit into cache – no further cache miss 318
15.8 The subsequence σ
i
1
σ
i
1
+1
.. . σ
i
1
+r
1
σ
i
2
have k+1 distinct elements, whereas
the subsequence σ
i
1
σ
i
1
+1
.. . σ
i
1
+r
1
have k distinct elements 319
16.1 The algorithm A receives input x
t
at time t, but has limited space 324
16.2 Boyer–Moore majority voting algorithm 325
16.3 Misra–Gries streaming algorithm for frequent elements 327
16.4 Counting number of distinct elements 328
16.5 Combining reservoir sampling with the estimator for F
k
332
16.6 Estimating F
2
336
剩余394页未读,继续阅读
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
janne2008
- 粉丝: 1
- 资源: 17
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 构建Cadence PSpice仿真模型库教程
- VMware 10.0安装指南:步骤详解与网络、文件共享解决方案
- 中国互联网20周年必读:影响行业的100本经典书籍
- SQL Server 2000 Analysis Services的经典MDX查询示例
- VC6.0 MFC操作Excel教程:亲测Win7下的应用与保存技巧
- 使用Python NetworkX处理网络图
- 科技驱动:计算机控制技术的革新与应用
- MF-1型机器人硬件与robobasic编程详解
- ADC性能指标解析:超越位数、SNR和谐波
- 通用示波器改造为逻辑分析仪:0-1字符显示与电路设计
- C++实现TCP控制台客户端
- SOA架构下ESB在卷烟厂的信息整合与决策支持
- 三维人脸识别:技术进展与应用解析
- 单张人脸图像的眼镜边框自动去除方法
- C语言绘制图形:余弦曲线与正弦函数示例
- Matlab 文件操作入门:fopen、fclose、fprintf、fscanf 等函数使用详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)