算法概论：分治、图解与最优化策略

需积分: 14 199 浏览量更新于2024-07-25 收藏 1.93MB PDF 举报

"这是一本英文原版的算法教材，涵盖了广泛的算法主题，包括与数字相关的算法、分治策略、图的分解、图中的路径、贪心算法、动态规划、线性规划及其简化、NP完全问题以及量子算法。这本书由S.Dasgupta、C.H.Papadimitriou和U.V.Vazirani三位作者共同编写，旨在深入讲解算法的核心概念和技术。" 详细知识点说明: 1. **算法与数字**：这一部分介绍了基础的算术操作，模运算，素数测试（对于密码学的重要性），以及哈希函数在碰撞避免中的应用。素数测试是加密技术的基础，而哈希函数在数据处理和数据库中广泛使用。 2. **分治算法**：这部分涵盖了如何通过将大问题分解为小问题来解决复杂问题，如快速乘法、递归关系的解析、归并排序、中位数查找以及快速傅里叶变换。这些都是高效解决问题的关键策略，例如在计算密集型任务中。 3. **图的分解**：讨论了为何要研究图，以及如何使用深度优先搜索在无向图和有向图中遍历节点。此外，还讲解了强连通分量的概念，这对于理解和分析复杂网络结构至关重要。 4. **图中的路径**：这部分探讨了如何寻找图中的距离、最短路径问题，如广度优先搜索、Dijkstra算法以及负权边和有向无环图（DAG）中的最短路径。这些算法在路由、网络优化和物流等领域具有实际应用。 5. **贪心算法**：贪心算法是一种每一步都选择局部最优解的方法，期望最终得到全局最优解。这部分可能会涵盖如霍夫曼编码和最小生成树等经典问题，它们在数据压缩和网络设计中有用。 6. **动态规划**：动态规划是一种用于解决具有重叠子问题和最优子结构的优化问题的方法。它在背包问题、最长公共子序列等经典问题中展现出强大的能力。 7. **线性规划和简化**：线性规划是优化问题的一种，常用于找出满足特定约束的最大或最小目标值。简化的线性规划问题有助于解决更复杂的优化问题。 8. **NP完全问题**：这部分介绍了一类难以在多项式时间内求解的问题，如旅行商问题和图着色问题。理解NP完全问题对于判断问题的可解性和寻找近似算法至关重要。 9. **应对NP完全性**：当面对NP完全问题时，可能需要采用启发式方法或近似算法来找到可行的解决方案，尽管它们不保证最优解。 10. **量子算法**：量子算法利用量子计算的特性，如量子叠加和量子纠缠，可以显著提高某些计算任务的速度，如Shor的素数因子分解算法和Grover的搜索算法。这本书对计算机科学和相关领域的学生及从业者来说，是一份宝贵的资源，它深入浅出地解释了各种算法，并提供了丰富的练习题以巩固学习。

Exercises

0.1. In each of the following situations, indicate whether f = O(g), or f = Ω(g), or both (in which case

f = Θ(g)).

f(n) g(n)

(a) n −100 n −200

(b) n

1/2

2/3

(d) n log n 10n log 10n

(e) log 2n log 3n

(f) 10 log n log(n

)

(g) n

1.01

n log

(h) n

/ log n n(log n)

(i) n

0.1

(log n)

(j) (log n)

log n

n/ log n

(k)

√

n (log n)

(l) n

1/2

log

(m) n2

(n) 2

n+1

(o) n! 2

(p) (log n)

log n

(log

(q)

i=1

k+1

0.2. Show that, if c is a positive real number, then g(n) = 1 + c + c

+ ···+ c

is:

(a) Θ(1) if c < 1.

(b) Θ(n) if c = 1.

) if c > 1.

The moral: in big-Θ terms, the sum of a geometric series is simply the ﬁrst term if the series is

strictly decreasing, the last term if the series is strictly increasing, or the number of terms if the

series is unchanging.

0.3. The Fibonacci numbers F

, F

, . . . , are deﬁned by the rule

= 0, F

= 1, F

= F

n−1

+ F

n−2

In this problem we will conﬁrm that this sequence grows exponentially fast and obtain some

bounds on its growth.

(a) Use induction to prove that F

≥ 2

0.5n

for n ≥ 6.

(b) Find a constant c < 1 such that F

≤ 2

for all n ≥ 0. Show that your answer is correct.

= Ω(2

0.4. Is there a faster way to compute the nth Fibonacci number than by fib2 (page 11)? One idea

involves matrices.

We start by writing the equations F

= F

and F

= F

+ F

in matrix notation:







0 1

1 1







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?)

Bases and logs

Naturally, there is nothing special about the number 10—we just happen to have 10 ﬁngers,

and so 10 was an obvious place to pause and take counting to the next level. The Mayans

developed a similar positional system based on the number 20 (no shoes, see?). And of course

today computers represent numbers in binary.

How many digits are needed to represent the number N ≥ 0 in base b? Let’s see—with k

digits in base b we can express numbers up to b

−1; for instance, in decimal, three digits get

us all the way up to 999 = 10

− 1. By solving for k, we ﬁnd that dlog

(N + 1)e digits (about

log

N digits, give or take 1) are needed to write N in base b.

How much does the size of a number change when we change bases? Recall the rule for

converting logarithms from base a to base b: log

N = (log

N)/(log

b). So the size of integer

N in base a is the same as its size in base b, times a constant factor log

b. In big-O notation,

therefore, the base is irrelevant, and we write the size simply as O(log N). When we do not

specify a base, as we almost never will, we mean log

Incidentally, this function log N appears repeatedly in our subject, in many guises. Here’s

a sampling:

1. log N is, of course, the power to which you need to raise 2 in order to obtain N.

2. Going backward, it can also be seen as the number of times you must halve N to get

down to 1. (More precisely: dlog Ne.) This is useful when a number is halved at each

iteration of an algorithm, as in several examples later in the chapter.

3. It is the number of bits in the binary representation of N . (More precisely: dlog(N +1)e.)

4. It is also the depth of a complete binary tree with N nodes. (More precisely: blog Nc.)

5. It is even the sum 1 +

+ ··· +

, to within a constant factor (Exercise 1.5).

number, the carry is always a single digit, and so at any given step, three single-digit numbers

are added. Here’s an example showing the addition 53 + 35 in binary.

Carry: 1 1 1 1

1 1 0 1 0 1 (53)

1 0 0 0 1 1 (35)

1 0 1 1 0 0 0 (88)

Ordinarily we would spell out the algorithm in pseudocode, but in this case it is so familiar

that we do not repeat it. Instead we move straight to analyzing its efﬁciency.

Given two binary numbers x and y, how long does our algorithm take to add them? This

is the kind of question we shall persistently be asking throughout this book. We want the

answer expressed as a function of the size of the input: the number of bits of x and y, the

number of keystrokes needed to type them in.

Suppose x and y are each n bits long; in this chapter we will consistently use the letter n

for the sizes of numbers. Then the sum of x and y is n + 1 bits at most, and each individual bit

剩余313页未读，继续阅读

teachwj

粉丝: 0
资源: 2

算法概论：分治、图解与最优化策略

Understanding Machine Learning-from theory to algorithm（英文原版）

Aalgorithm_Robert Sedgewick 高清英文原版第四版

Algorithm Design 算法设计 英文版 part1

Computer Vision--Algorithm and Application （英文原版彩色）

算法导论 第三版 英文原版 带有详细书签 introduction to algorithm

最经典的蛙跳算法论文（Shuffled Frog-Leaping Algorithm,英文原版）

MCMC Methods Gibbs Sampling and the Metropolis-Hastings Algorithm（优秀英文原版教材）.pdf

HashCalc 英文原版

PSSM算法英文原版

AlgorithmsandParallelComputingNetworkingBook.pdf 英文原版

最新资源

Algorithm Design 算法设计英文版 part1

算法导论第三版英文原版带有详细书签 introduction to algorithm