Dasgupta-Papadimitriou-Vazirani算法教材：全面探讨与NP完全问题及量子算法

需积分: 16 144 浏览量更新于2024-07-19 收藏 1.66MB PDF 举报

《算法导论》（Dasgupta, Papadimitriou, Vazirani 著）是一本权威的算法教材，排名仅次于经典的《算法导引》(CLRS)。本书涵盖了算法设计的基础技术，深入探讨了NP完全问题以及量子算法，适合对算法理论和实践有深入理解的学习者。在本书的开篇部分，"Prologue"介绍了书籍的目的和背景，强调了算法在计算机科学中的核心地位，同时通过Fibonacci数列和实际问题的引入，引导读者理解算法的基本概念。"Big-O notation"这一章则介绍了算法复杂度分析的重要工具，帮助读者衡量算法的效率。第1章"Algorithms with numbers"涵盖了基础的数值运算，如基本算术、模运算、素数检验，以及密码学原理和通用哈希函数，这些都是设计和分析算法的基础。这一章的目的是让读者掌握处理数字数据时的高效算法策略。第二部分深入探讨了"Divide-and-conquer algorithms"，涉及乘法的优化、递归关系的应用、排序算法如归并排序、求解中位数、矩阵乘法，以及快速傅里叶变换等高级技巧。这些算法设计的核心原则在解决复杂问题时展现出强大的力量。第三章"Decomposition of graphs"关注图论在算法中的应用，包括为何研究图、深度优先搜索（DFS）及其在有向图中的扩展、强连通分量的识别等，这些都是网络结构分析和最短路径问题的关键。第4章"Paths in graphs"专门讨论图的路径问题，包括距离计算、广度优先搜索(BFS)、边权重的考虑、迪杰斯特拉(Dijkstra)算法以及优先队列实现，这些都是关键的路径查找和优化技术，对于网络和路径问题的解决方案至关重要。随机化算法作为一个"virtual chapter"，引入了概率和随机性在算法设计中的角色，这对于解决某些问题时具有显著优势，尤其是在面对不确定性或难以确定最优解的情况下。《Dasgupta, Papadimitriou, Vazirani》以其全面而深入的内容，帮助读者从基础到进阶理解算法的设计与分析，为计算机科学专业学生和研究人员提供了一个不可或缺的学习资料。无论是在理论研究还是实际编程中，它都能提供强大的支持。

Algorithms

Figure 0.2 Which running time is better?

1 2 3 4 5 6 7 8 9 10

100

2n+20

disregard what happens for small values of n. For example, suppose we are choosing between

two algorithms for a particular computational task. One takes f

(n) = n

steps, while the

other takes f

(n) = 2n + 20 steps (Figure 0.2). Which is better? Well, this depends on the

value of n. For n ≤ 5, f

is smaller; thereafter, f

is the clear winner. In this case, f

scales

much better as n grows, and therefore it is superior.

This superiority is captured by the big-O notation: f

= O(f

), because

(n)

2n + 20

≤ 22

for all n; on the other hand, f

6= O(f

), since the ratio f

(n)/f

(n) = n

/(2n + 20) can get

arbitrarily large, and so no constant c will make the deﬁnition work.

Now another algorithm comes along, one that uses f

(n) = n + 1 steps. Is this better

than f

? Certainly, but only by a constant factor. The discrepancy between f

and f

is tiny

compared to the huge gap between f

and f

. In order to stay focused on the big picture, we

treat functions as equivalent if they differ only by multiplicative constants.

Returning to the deﬁnition of big-O, we see that f

= O(f

(n)

2n + 20

n + 1

≤ 20,

and of course f

= O(f

), this time with c = 1.

Just as O(·) is an analog of ≤, we can also deﬁne analogs of ≥ and = as follows:

f = Ω(g) means g = O(f )

f = Θ(g) means f = O(g) and f = Ω(g).

S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

Similarly,







0 1

1 1









0 1

1 1







and in general



n+1





0 1

1 1







So, in order to compute F

, it sufﬁces to raise this 2 × 2 matrix, call it X, to the nth power.

(a) Show that two 2 × 2 matrices can be multiplied using 4 additions and 8 multiplications.

But how many matrix multiplications does it take to compute X

(b) Show that O(log n) matrix multiplications sufﬁce for computing X

. (Hint: Think about

computing X

Thus the number of arithmetic operations needed by our matrix-based algorithm, call it fib3, is

just O(log n), as compared to O(n) for fib2. Have we broken another exponential barrier?

The catch is that our new algorithm involves multiplication, not just addition; and multiplica-

tions of large numbers are slower than additions. We have already seen that, when the complex-

ity of arithmetic operations is taken into account, the running time of fib2 becomes O(n

(d) Let M(n) be the running time of an algorithm for multiplying n-bit numbers, and assume

that M(n) = O(n

) (the school method for multiplication, recalled in Chapter 1, achieves

this). Prove that the running time of fib3 is O(M (n) log n).

(e) Can you prove that the running time of fib3 is O(M(n))? (Hint: The lengths of the num-

bers being multiplied get doubled with every squaring.)

In conclusion, whether fib3 is faster than fib2 depends on whether we can multiply n-bit

integers faster than O(n

). Do you think this is possible? (The answer is in Chapter 2.)

Finally, there is a formula for the Fibonacci numbers:

√

1 +

√

−

√

1 −

√

So, it would appear that we only need to raise a couple of numbers to the nth power in order to

compute F

. The problem is that these numbers are irrational, and computing them to sufﬁcient

accuracy is nontrivial. In fact, our matrix method fib3 can be seen as a roundabout way of

raising these irrational numbers to the nth power. If you know your linear algebra, you should

see why. (Hint: What are the eigenvalues of the matrix X?)

剩余335页未读，继续阅读

elessar_elessar

粉丝: 0
资源: 1

Dasgupta-Papadimitriou-Vazirani算法教材：全面探讨与NP完全问题及量子算法

Algorithm-Algorithms-by-S.Dasgupta.zip

Algorithms,.S..Dasgupta,.C.H..Papadimitriou,.U.V..Vazirani,.MGH,.2008.pdf

《算法》- Dasgupta, Papadimitriou, Vazirani 合著经典

Dasgupta, Papadimitriou & Vazirani算法教材：经典与实践

leetcode算法导论-algorithm:带有解释和时间复杂度分析的我的LeetCode解决方案

Vazirani与Dasgupta算法详解：核心技术与应用

《Papadimitriou 算法》：探索图解算法与复杂性

实用算法精要：Papadimitrion's最新教材概览

utlog.sqlite

钢结构原理课程设计：露顶式平面钢闸门设计任务及指南

最新资源