算法解锁：计算机解决问题的核心

需积分: 32 51 浏览量更新于2024-07-21 1 收藏 2.57MB PDF 举报

"Algorithms Unlocked(MTI,2013)" 是一本由Thomas Cormen编写的书籍，旨在向非专业读者介绍计算机算法的基础知识。这本书用简洁易懂的语言解释了算法如何在现实生活中发挥作用，例如GPS导航、互联网交易安全等。书中涵盖了搜索、排序、图论、字符串处理、密码学、数据压缩以及NP完全问题等内容。在本书中，读者将了解到： 1. 计算机算法的本质：它们是解决问题的数学公式，可以被转化为计算机程序。通过对算法的理解，我们可以知道计算机如何高效地处理信息。 2. 搜索算法：书中可能会讲解线性搜索、二分搜索等基础方法，帮助读者理解如何在计算机中快速查找所需的信息。 3. 排序算法：包括冒泡排序、插入排序、选择排序、快速排序、归并排序等，这些方法用于组织和整理计算机中的数据。 4. 图论：通过图模型，可以解决如道路网络、任务依赖和财务关系等问题。书中可能涉及DFS（深度优先搜索）和BFS（广度优先搜索）等概念。 5. 字符串处理：对于DNA结构等字符串数据，可能会介绍KMP算法、模式匹配等技术。 6. 密码学基础：讨论加密和解密的原理，如对称加密（如DES）、非对称加密（如RSA）以及哈希函数等，这些都是网络安全的重要组成部分。 7. 数据压缩：了解如何减少数据存储需求，如霍夫曼编码和LZ77压缩算法。 8. NP完全问题：介绍一些尚未找到高效解决方案的问题，如旅行商问题，这些问题在理论上可能需要不切实际的时间来解决。 9. 书的结构和作者：Thomas Cormen是算法领域的专家，他也是《算法导论》这本知名教材的合著者，这本书适合对计算机科学感兴趣但缺乏专业背景的读者。通过阅读《Algorithms Unlocked》，读者不仅能够理解算法的基本概念，还能学习到如何描述和评估算法的效率，从而增进对计算机科学核心的理解。此外，书中可能还会提供一些实践练习和实例，帮助读者将理论知识应用到实际场景中。

1 What Are Algorithms and Why

Should You Care?

Let’s start with the question that I’m often asked: “What is an algo-

rithm?”

A broad answer would be “a set of steps to accomplish a task.” You

have algorithms that you run in your everyday life. You have an al-

gorithm to brush your teeth: open the toothpaste tube, pick up your

toothbrush, squeeze toothpaste onto the brush until you have applied

enough to the brush, close the tube, put the brush into one quadrant of

your mouth, move the brush up and down for N seconds, etc. If you

have to commute to a job, you have an algorithm for your commute.

And so on.

But this book is about algorithms that run on computers or, more

generally, computational devices. Just as algorithms that you run af-

fect your everyday life, so do algorithms that run on computers. Do

you use your GPS to ﬁnd a route to travel? It runs what we call a

“shortest-path” algorithm to ﬁnd the route. Do you buy products on

the Internet? Then you use (or should be using) a secure website that

runs an encryption algorithm. When you buy products on the Internet,

are they delivered by a private delivery service? It uses algorithms to

assign packages to individual trucks and then to determine the order in

which each driver should deliver packages. Algorithms run on comput-

ers all over the place—on your laptop, on servers, on your smartphone,

on embedded systems (such as in your car, your microwave oven, or

climate-control systems)—everywhere!

What distinguishes an algorithm that runs on a computer from an

algorithm that you run? You might be able to tolerate it when an algo-

rithm is imprecisely described, but a computer cannot. For example, if

you drive to work, your drive-to-work algorithm might say “if trafﬁc is

bad, take an alternate route.” Although you might know what you mean

by “bad trafﬁc,” a computer does not.

So a computer algorithm is a set of steps to accomplish a task that

is described precisely enough that a computer can run it. If you have

Or, as a fellow with whom I used to play hockey would ask, “What’s a nalgorithm?”

2 Chapter 1: What Are Algorithms and Why Should You Care?

done even a little computer programming in Java, C, C++, Python, For-

tran, Matlab, or the like, then you have some idea of what that level of

precision means. If you have never written a computer program, then

perhaps you will get a feel for that level of precision from seeing how I

describe algorithms in this book.

Let’s go to the next question: “What do we want from a computer algo-

rithm?”

Computer algorithms solve computational problems. We want two

things from a computer algorithm: given an input to a problem, it should

always produce a correct solution to the problem, and it should use com-

putational resources efﬁciently while doing so. Let’s examine these two

desiderata in turn.

Correctness

What does it mean to produce a correct solution to a problem? We can

usually specify precisely what a correct solution would entail. For ex-

ample, if your GPS produces a correct solution to ﬁnding the best route

to travel, it might be the route, out of all possible routes from where

you are to your desired destination, that will get you there soonest. Or

perhaps the route that has the shortest possible distance. Or the route

that will get you there soonest but also avoids tolls. Of course, the in-

formation that your GPS uses to determine a route might not match re-

ality. Unless your GPS can access real-time trafﬁc information, it might

assume that the time to traverse a road equals the road’s distance di-

vided by the road’s speed limit. If the road is congested, however, the

GPS might give you bad advice if you’re looking for the fastest route.

We can still say that the routing algorithm that the GPS runs is correct,

however, even if the input to the algorithm is not; for the input given to

the routing algorithm, the algorithm produces the fastest route.

Now, for some problems, it might be difﬁcult or even impossible to

say whether an algorithm produces a correct solution. Take optical char-

acter recognition for example. Is this 11  6 pixel image a 5 or an S?

Some people might call it a 5, whereas others might call it an S, so how

could we declare that a computer’s decision is either correct or incor-

Chapter 1: What Are Algorithms and Why Should You Care? 3

rect? We won’t. In this book, we will focus on computer algorithms

that have knowable solutions.

Sometimes, however, we can accept that a computer algorithm might

produce an incorrect answer, as long as we can control how often

it does so. Encryption provides a good example. The commonly

used RSA cryptosystem relies on determining whether large num-

bers—really large, as in hundreds of digits long—are prime. If you

have ever written a computer program, you could probably write one

that determines whether a number n is prime. It would test all candidate

divisors from 2 through n  1, and if any of these candidates is indeed

a divisor of n,thenn is composite. If no number between 2 and n  1

is a divisor of n,thenn is prime. But if n is hundreds of digits long,

that’s a lot of candidate divisors, more than even a really fast computer

could check in any reasonable amount of time. Of course, you could

make some optimizations, such as eliminating all even candidates once

you ﬁnd that 2 is not a divisor, or stopping once you get to

n (since if

d is greater than

n and d is a divisor of n,thenn=d is less than

andisalsoadivisorofn; therefore, if n has a divisor, you will ﬁnd

it by the time you get to

n). If n is hundreds of digits long, then

although

n has only about half as many digits as n does, it’s still a

really large number. The good news is that we know of an algorithm

that tests quickly whether a number is prime. The bad news is that it

can make errors. In particular, if it declares that n is composite, then

n is deﬁnitely composite, but if it declares that n is prime, then there’s

a chance that n is actually composite. But the bad news is not all that

bad: we can control the error rate to be really low, such as one error in

every 2

times. That’s rare enough—one error in about every million

billion times—for most of us to be comfortable with using this method

to determine whether a number is prime for RSA.

Correctness is a tricky issue with another class of algorithms, called

approximation algorithms. Approximation algorithms apply to opti-

mization problems, in which we want to ﬁnd the best solution according

to some quantitative measure. Finding the fastest route, as a GPS does,

is one example, where the quantitative measure is travel time. For some

problems, we have no algorithm that ﬁnds an optimal solution in any

reasonable amount of time, but we know of an approximation algorithm

that, in a reasonable amount of time, can ﬁnd a solution that is almost

optimal. By “almost optimal,” we typically mean that the quantitative

measure of the solution found by the approximation algorithm is within

4 Chapter 1: What Are Algorithms and Why Should You Care?

some known factor of the optimal solution’s quantitative measure. As

long as we specify what the desired factor is, we can say that a correct

solution from an approximation algorithm is any solution that is within

that factor of the optimal solution.

Resource usage

What does it mean for an algorithm to use computational resources ef-

ﬁciently? We alluded to one measure of efﬁciency in the discussion

of approximation algorithms: time. An algorithm that gives a correct

solution but takes a long time to produce that correct solution might

be of little or no value. If your GPS took an hour to determine which

driving route it recommends, would you even bother to turn it on? In-

deed, time is the primary measure of efﬁciency that we use to evalu-

ate an algorithm, once we have shown that the algorithm gives a cor-

rect solution. But it is not the only measure. We might be concerned

with how much computer memory the algorithm requires (its “memory

footprint”), since an algorithm has to run within the available memory.

Other possible resources that an algorithm might use: network commu-

nication, random bits (because algorithms that make random choices

need a source of random numbers), or disk operations (for algorithms

that are designed to work with disk-resident data).

In this book, as in most of the algorithms literature, we will focus

on just one resource: time. How do we judge the time required by an

algorithm? Unlike correctness, which does not depend on the particular

computer that the algorithm runs on, the actual running time of an al-

gorithm depends on several factors extrinsic to the algorithm itself: the

speed of the computer, the programming language in which the algo-

rithm is implemented, the compiler or interpreter that translates the pro-

gram into code that runs on the computer, the skill of the programmer

who writes the program, and other activity taking place on the computer

concurrently with the running program. And that all assumes that the

algorithm runs on just one computer with all its data in memory.

If we were to evaluate the speed of an algorithm by implementing it in

a real programming language, running it on a particular computer with

a given input, and measuring the time the algorithm takes, we would

know nothing about how fast the algorithm ran on an input of a different

size, or possibly even on a different input of the same size. And if we

wanted to compare the relative speed of the algorithm with some other

algorithm for the same problem, we would have to implement them both

Chapter 1: What Are Algorithms and Why Should You Care? 5

and run both of them on various inputs of various sizes. How, then, can

we evaluate an algorithm’s speed?

The answer is that we do so by a combination of two ideas. First,

we determine how long the algorithm takes as a function of the size

of its input. In our route-ﬁnding example, the input would be some

representation of a roadmap, and its size would depend on the number

of intersections and the number of roads connecting intersections in the

map. (The physical size of the road network would not matter, since we

can characterize all distances by numbers and all numbers occupy the

same size in the input; the length of a road has no bearing on the input

size.) In a simpler example, searching a given list of items to determine

whether a particular item is present in the list, the size of the input would

be the number of items in the list.

Second, we focus on how fast the function that characterizes the run-

ning time grows with the input size—the rate of growth of the running

time. In Chapter 2, we’ll see the notations that we use to characterize

an algorithm’s running time, but what’s most interesting about our ap-

proach is that we look at only the dominant term in the running time,

and we don’t consider coefﬁcients. That is, we focus on the order of

growth of the running time. For example, suppose we could determine

that a speciﬁc implementation of a particular algorithm to search a list

of n items takes 50n C 125 machine cycles. The 50n term dominates

the 125 term once n gets large enough, starting at n  3 and increas-

ing in dominance for even larger list sizes. Thus, we don’t consider

the low-order term 125 when we describe the running time of this hy-

pothetical algorithm. What might surprise you is that we also drop the

coefﬁcient 50, thereby characterizing the running time as growing lin-

early with the input size n. As another example, if an algorithm took

20n

C 100n

C 300n C 200 machine cycles, we would say that its

running time grows as n

. Again, the low-order terms—100n

, 300n,

and 200—become less and less signiﬁcant as the input size n increases.

In practice, the coefﬁcients that we ignore do matter. But they de-

pend so heavily on the extrinsic factors that it’s entirely possible that if

we were comparing two algorithms, A and B, that have the same order

of growth and are run on the same input, then A might run faster than B

with a particular combination of machine, programming language, com-

piler/interpreter, and programmer, while B runs faster than A with some

other combination. Of course, if algorithms A and B both produce cor-

rect solutions and A always runs twice as fast as B, then, all other things

www.allitebooks.com

剩余236页未读，继续阅读

vanridin

粉丝: 108
资源: 1187

算法解锁：计算机解决问题的核心

Algorithms Unlocked cormen

Algorithms Unlocked(Thomas H. cormen)

分别解释下Continuous control algorithms和Discrete control algorithms

_lib.OpenSSL_add_all_algorithms() AttributeError: module 'lib' has no attribute 'OpenSSL_add_all_algorithms'

Algorithms期刊的CCF分区

ModuleNotFoundError: No module named ‘algorithms’

ModuleNotFoundError: No module named 'algorithms.train_LSTNet'

nx.algorithms.centrality是什么

使用OpenMesh和QT实现Volumetric Repair Algorithms

shardingjdbc 中 sharding-algorithms，怎么结合HintManager使用

最新资源