《Concrete Mathematics：计算机科学基石》

需积分: 14 146 浏览量更新于2024-07-23 收藏 11.25MB PDF 举报

《Concrete Mathematics: A Foundation for Computer Science》是一本经典的计算机科学著作，由Ronald L. Graham、Donald E. Knuth和Oren Patashnik合著，由Addison-Wesley出版社出版。这本书的创作灵感来源于对数学家Leonhard Euler的敬意，他在18世纪为现代数学的发展做出了重大贡献。该书的核心内容围绕离散数学展开，它是计算机科学的基础，涉及数论、组合数学、图论、概率论等领域的理论和方法。它强调的是将抽象的数学概念与实际的计算机程序设计相结合，帮助读者理解和解决与计算机科学相关的复杂问题。书中详尽阐述了如何运用数学工具来设计算法、分析性能以及优化数据结构。书中涵盖了广泛的数学概念，如计数原理、递归关系、矩阵和线性代数在计算机科学中的应用，以及如何通过组合策略解决实际问题。例如，作者们展示了如何利用组合数学中的排列和组合理论来设计高效的搜索算法，或者利用图论的概念来分析网络连接性和路由问题。此外，《Concrete Mathematics》还深入探讨了数学与计算的关系，通过实例展示了数学公式如何转化为计算机程序，以及如何通过数学推导优化算法的效率。作者们强调了精确性和简洁性的原则，认为数学之美不仅在于其理论深度，更在于其在解决实际问题中的实用性。该书的第六版在1990年发行，包含了先前版本的改正和更新，确保了信息的准确性和时效性。它不仅是计算机科学家和程序员的必备参考书，也是对数学爱好者和理论研究者的宝贵资源。版权方面，所有内容受Addison-Wesley Publishing Company保护，未经许可不得复制或存储。《Concrete Mathematics: A Foundation for Computer Science》是一本具有深远影响力的书籍，它不仅提供了深厚的数学理论基础，而且将这些理论与计算机科学实践紧密相连，是理解和提升计算机科学能力的里程碑之作。

2 RECURRENT PROBLEMS

It’s not immediately obvious that the puzzle has a solution, but a little

thought (or having seen the problem before) convinces us that it does. Now

the question arises: What’s the best we can do? That is, how many moves

are necessary and sufficient to perform the task?

The best way to tackle a question like this is to generalize it a bit. The

Tower of Brahma has 64 disks and the Tower of Hanoi has 8; let’s consider

what happens if there are n disks.

One advantage of this generalization is that we can scale the problem

down even more. In fact, we’ll see repeatedly in this book that it’s advanta-

geous to LOOK AT SMALL CASES first. It’s easy to see how to transfer a tower

that contains only one or two disks. And a small amount of experimentation

shows how to transfer a tower of three.

The next step in solving the problem is to introduce appropriate notation:

NAME AND CONQUER. Let’s say that

T,,

is the minimum number of moves

that will transfer n disks from one peg to another under Lucas’s rules. Then

is obviously

and

= 3.

We can also get another piece of data for free, by considering the smallest

case of all: Clearly

= 0, because no moves at all are needed to transfer a

tower of n = 0 disks! Smart mathematicians are not ashamed to think small,

because general patterns are easier to perceive when the extreme cases are

well understood (even when they are trivial).

But now let’s change our perspective and try to think big; how can we

transfer a large tower? Experiments with three disks show that the winning

idea is to transfer the top two disks to the middle peg, then move the third,

then bring the other two onto it. This gives us a clue for transferring n disks

in general: We first transfer the n

1 smallest to a different peg (requiring

T,-l

moves), then move the largest (requiring one move), and finally transfer

the n- 1 smallest back onto the largest (requiring another

Tn..1

moves). Thus

we can transfer n disks (for n > 0) in at most

2T,-,

+ 1 moves:

2Tn-1

+ 1 ,

for n > 0.

This formula uses

‘

’

instead of

‘

’

because our construction proves only

that 2T+1 + 1 moves suffice; we haven’t shown that 2T,_, + 1 moves are

necessary. A clever person might be able to think of a shortcut.

But is there a better way? Actually no. At some point we must move the

largest disk. When we do, the n

1 smallest must be on a single peg, and it

has taken at least T,_, moves to put them there. We might move the largest

disk more than once, if we’re not too alert. But after moving the largest disk

for the last time, we must transfer the n- 1 smallest disks (which must again

be on a single peg) back onto the largest; this too requires

T,-

1 moves. Hence

Most of the pub-

lished “solutions”

to Lucas’s problem,

like the early one

of Allardice and

Fraser

[?I,

fail to ex-

plain why

T,,

must

be 3

2T,,

1 + 1.

2Tn-1

+ 1 ,

for n > 0.

Yeah, yeah.

lseen

that

word

before.

Mathematical in-

duction proves that

we can climb as

high as we like on

ladder, by proving

that we can

climb

onto the bottom

rung (the basis)

and that from each

rung we can climb

up to the next one

(the induction).

1.1 THE TOWER OF HANOI 3

These two inequalities, together with the trivial solution for n = 0, yield

=O;

2T+1

for n > 0.

(1.1)

(Notice that these formulas are consistent with the known values

= 1 and

= 3. Our experience with small cases has not only helped us to discover

a general formula, it has also provided a convenient way to check that we

haven’t made a foolish error. Such checks will be especially valuable when we

get into more complicated maneuvers in later chapters.)

A set of equalities like (1.1) is called a recurrence (a.k.a. recurrence

relation or recursion relation). It gives a boundary value and an equation for

the general value in terms of earlier ones. Sometimes we refer to the general

equation alone as a recurrence, although technically it needs a boundary value

to be complete.

The recurrence allows us to compute

T,,

for any n we like. But nobody

really likes to compute from a recurrence, when n is large; it takes too long.

The recurrence only gives indirect,

“local” information. A solution to the

recurrence would make us much happier. That is, we’d like a nice, neat,

“closed form” for

T,,

that lets us compute it quickly, even for large n. With

a closed form, we can understand what

T,,

really is.

So how do we solve a recurrence? One way is to guess the correct solution,

then to prove that our guess is correct. And our best hope for guessing

the solution is to look (again) at small cases. So we compute, successively,

T~=2~3+1=7;T~=2~7+1=15;T~=2~15+1=31;T~=2~31+1=63.

Aha! It certainly looks as if

2n-1,

for n 3 0.

(1.2)

At least this works for n < 6.

Mathematical induction is a general way to prove that some statement

about the integer n is true for all n 3 no. First we prove the statement

when n has its smallest value, no; this is called the basis. Then we prove the

statement for n > no, assuming that it has already been proved for all values

between no and n

inclusive; this is called the induction. Such a proof

gives infinitely many results with only a finite amount of work.

Recurrences are ideally set up for mathematical induction. In our case,

for example, (1.2) follows easily from (1.1): The basis is trivial, since

2’

1 = 0. And the induction follows for n > 0 if we assume that (1.2) holds

when n is replaced by n

T,,

2T,,

2(2

-l)+l

2n-l.

Hence (1.2) holds for n as well. Good! Our quest for

T,,

has ended successfully.

4 RECURRENT PROBLEMS

Of course the priests’ task hasn’t ended; they’re still dutifully moving

disks, and will be for a while, because for n = 64 there are

264-l

moves (about

18 quintillion). Even at the impossible rate of one move per microsecond, they

will need more than 5000 centuries to transfer the Tower of Brahma. Lucas’s

original puzzle is a bit more practical, It requires

1 = 255 moves, which

takes about four minutes for the quick of hand.

The Tower of Hanoi recurrence is typical of many that arise in applica-

tions of all kinds. In finding a closed-form expression for some quantity of

interest like

T,,

we go through three stages:

Look at small cases. This gives us insight into the problem and helps us

in stages 2 and 3.

Find and prove a mathematical expression for the quantity of interest.

What is a proof?

For the Tower of Hanoi, this is the recurrence (1.1) that allows us, given

“One

ha’fofone

the inclination, to compute

T,,

for any n.

percent

pure alco-

hol.

”

Find and prove a closed form for our mathematical expression. For the

Tower of Hanoi, this is the recurrence solution

(1.2).

The third stage is the one we will concentrate on throughout this book. In

fact, we’ll frequently skip stages 1 and 2 entirely, because a mathematical

expression will be given to us as a starting point. But even then, we’ll be

getting into subproblems whose solutions will take us through all three stages.

Our analysis of the Tower of Hanoi led to the correct answer, but it

required an “inductive leap”;

we relied on a lucky guess about the answer.

One of the main objectives of this book is to explain how a person can solve

recurrences without being clairvoyant. For example, we’ll see that recurrence

(1.1) can be simplified by adding 1 to both sides of the equations:

+ 1 = 1;

Lsl

=2T,-,

+2,

for n > 0.

Now if we let

T,,

we have

uo = 1

;

2&-l,

for n > 0.

Interesting: We get

rid of the

(1.1) by adding, not

(1.3) by subtracting.

It doesn’t take genius to discover that the solution to this recurrence is just

= 2”; hence T, = 2”

1. Even a computer could discover this.

1.2 LINES IN THE PLANE

Our second sample problem has a more geometric flavor: How many

slices of pizza can a person obtain by making n straight cuts with a pizza

knife? Or, more academically: What is the maximum number L, of regions

剩余639页未读，继续阅读

txp914

粉丝: 22
资源: 703

《Concrete Mathematics：计算机科学基石》

Addison.Wesley.Concrete.Mathematics.A.Foundation.for.Computer.Science.part1.rar

Concrete.Mathematics.-.2nd.Edition.pdf

Concrete Mathematics A Foundation for Computer Science

Concrete Mathematics A Foundation for Computer Science, 2nd Edition.pdf

Concrete Mathematics A Foundation for Computer Science(Second Edition)

Concrete Mathematics-A Foundation for Computer Science第二版

Concrete Mathematics: A Foundation for Computer Science (2nd Edition)

具体数学中文版Concrete Mathematics--A Foundation for Computer Science

离散数学 - Discrete Mathematics

Elements of Mathematics:练习基本的数学运算-开源

最新资源