Concrete Mathematics - A Foundation for Computer Science.pdf - 9_Misc - musli_com

CONCRETE

MATHEMATICS

Dedicated to Leonhard Euler (1707-l 783)

CONCRETE

MATHEMATICS

Dedicated to Leonhard Euler (1707-l 783)

CONCRETE

MATHEMATICS

Ronald L. Graham

AT&T Bell Laboratories

Donald E. Knuth

Stanford University

Oren Patashnik

Stanford University

ADDISON-WESLEY

PUBLISHING

COMPANY

New York

Reading, Massachusetts

Menlo Park, California

Don Mills, Ontario

Wokingham, England

Amsterdam

Bonn

Sydney

Singapore

Tokyo

Madrid

San Juan

Preface

THIS BOOK IS BASED on a course of the same name that has been taught

annually at Stanford University since 1970. About fifty students have taken it

each year-juniors and seniors, but mostly graduate students-and alumni

of these classes have begun to spawn similar courses elsewhere. Thus the time

seems ripe to present the material to a wider audience (including sophomores).

It was a dark and stormy decade when Concrete Mathematics was born.

Long-held values were constantly being questioned during those turbulent

years; college campuses were hotbeds of controversy. The college curriculum

itself was challenged, and mathematics did not escape scrutiny. John Ham-

mersley had just written a thought-provoking article “On the enfeeblement of

mathematical skills by ‘Modern Mathematics’ and by similar soft intellectual

trash in schools and universities” [145]; other worried mathematicians [272]

even asked, “Can mathematics be saved?” One of the present authors had

embarked on a series of books called The Art of Computer Programming, and

in writing the first volume he (DEK) had found that there were mathematical

tools missing from his repertoire; the mathematics he needed for a thorough,

well-grounded understanding of computer programs was quite different from

what he’d learned as a mathematics major in college. So he introduced a new

course, teaching what he wished somebody had taught him.

The course title “Concrete Mathematics” was originally intended as an

antidote to “Abstract Mathematics,” since concrete classical results were rap-

idly being swept out of the modern mathematical curriculum by a new wave

of abstract ideas popularly called the “New Math!’ Abstract mathematics is a

wonderful subject, and there’s nothing wrong with it: It’s beautiful, general,

and useful. But its adherents had become deluded that the rest of mathemat-

ics was inferior and no longer worthy of attention. The goal of generalization

had become so fashionable that a generation of mathematicians had become

unable to relish beauty in the particular, to enjoy the challenge of solving

quantitative problems, or to appreciate the value of technique. Abstract math-

ematics was becoming inbred and losing touch with reality; mathematical ed-

ucation needed a concrete counterweight in order to restore a healthy balance.

When DEK taught Concrete Mathematics at Stanford for the first time,

he explained the somewhat strange title by saying that it was his attempt

“A odience, level,

and treatment -

a description of

such matters is

what prefaces are

supposed to be

about.”

- P. R. Halmos 11421

“People do acquire

a little brief author-

ity by equipping

themselves with

jargon: they can

pontificate and air a

superficial expertise.

But what we should

ask of educated

mathematicians is

not what they can

speechify about,

nor even what they

know about the

existing corpus

of mathematical

knowledge, but

rather what can

they now do with

their learning and

whether they can

actually solve math-

ematical problems

arising in practice.

In short, we look for

deeds not words.”

- J. Hammersley [145]

vi PREFACE

to teach a math course that was hard instead of soft. He announced that,

contrary to the expectations of some of his colleagues, he was not going to

teach the Theory of Aggregates, nor Stone’s Embedding Theorem, nor even

the Stone-Tech compactification. (Several students from the civil engineering

department got up and quietly left the room.)

Although Concrete Mathematics began as a reaction against other trends,

the main reasons for its existence were positive instead of negative. And as

the course continued its popular place in the curriculum, its subject matter

“solidified” and proved to be valuable in a variety of new applications. Mean-

while, independent confirmation for the appropriateness of the name came

from another direction, when Z. A. Melzak published two volumes entitled

Companion to Concrete Mathematics [214].

The material of concrete mathematics may seem at first to be a disparate

bag of tricks, but practice makes it into a disciplined set of tools. Indeed, the

techniques have an underlying unity and a strong appeal for many people.

When another one of the authors (RLG) first taught the course in 1979, the

students had such fun that they decided to hold a class reunion a year later.

But what exactly is Concrete Mathematics? It is a blend of continuous

and diSCRETE mathematics. More concretely, it is the controlled manipulation

of mathematical formulas, using a collection of techniques for solving prob-

lems. Once you, the reader, have learned the material in this book, all you

will need is a cool head, a large sheet of paper, and fairly decent handwriting

in order to evaluate horrendous-looking sums, to solve complex recurrence

relations, and to discover subtle patterns in data. You will be so fluent in

algebraic techniques that you will often find it easier to obtain exact results

than to settle for approximate answers that are valid only in a limiting sense.

The major topics treated in this book include sums, recurrences, ele-

mentary number theory, binomial coefficients, generating functions, discrete

probability, and asymptotic methods. The emphasis is on manipulative tech-

nique rather than on existence theorems or combinatorial reasoning; the goal

is for each reader to become as familiar with discrete operations (like the

greatest-integer function and finite summation) as a student of calculus is

familiar with continuous operations (like the absolute-value function and in-

finite integration).

Notice that this list of topics is quite different from what is usually taught

nowadays in undergraduate courses entitled “Discrete Mathematics!’ There-

fore the subject needs a distinctive name, and “Concrete Mathematics” has

proved to be as suitable as any other.

The original textbook for Stanford’s course on concrete mathematics was

the “Mathematical Preliminaries” section in The Art of Computer Program-

ming [173]. But the presentation in those 110 pages is quite terse, so another

author (OP) was inspired to draft a lengthy set of supplementary notes. The

“The heart of math-

ematics consists

of concrete exam-

ples and concrete

problems. ”

-P. R. Halmos 11411

“lt is downright

sinful to teach the

abstract before the

concrete. ”

-Z. A. Melzak

12141

Concrete Ma the-

matics is a bridge

to abstract mathe-

matics.

“The advanced

reader who skips

parts that appear

too elementary

may

miss more than

the less advanced

reader who skips

parts that appear

too complex. ”

-G. Pdlya [238]

(We’re not bold

enough to try

Distinuous Math-

ema tics.)

Concrete Mathematics - A Foundation for Computer Science.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: