Concrete Mathematics.pdf

(11524 KB) Pobierz
CONCRETE
MATHEMATICS
Dedicated to Leonhard Euler (1707-l 783)
CONCRETE
MATHEMATICS
Dedicated to Leonhard Euler (1707-l 783)
CONCRETE
MATHEMATICS
AT&T
Bell
Laboratories
Ronald L. Graham
Donald E. Knuth
Stanford University
Oren Patashnik
Stanford University
A
ADDISON-WESLEY PUBLISHING COMPANY
New York
Reading, Massachusetts
Menlo Park, California
Don Mills, Ontario
Amsterdam
Bonn
Wokingham, England
Sydney
Singapore
Tokyo
Madrid
San Juan
Library of Congress Cataloging-in-Publication Data
Graham, Ronald Lewis, 1935-
Concrete mathematics : a foundation for computer science / Ron-
ald L. Graham, Donald E. Knuth, Oren Patashnik.
xiii,625 p. 24 cm.
Bibliography: p. 578
Includes index.
ISBN o-201-14236-8
1. Mathematics--1961-
2. Electronic data processing--Mathematics.
I. Knuth, Donald Ervin, 1938-
. II. Patashnik, Oren, 1954-
.
III. Title.
QA39.2.C733 1988
510--dc19
88-3779
CIP
Sixth
printing,
with
corrections,
October
1990
Copyright @ 1989 by Addison-Wesley Publishing Company
All rights reserved. No part of this publication may be reproduced, stored in a
retrieval system or transmitted, in any form or by any means, electronic, mechani-
cal,
photocopying, recording, or otherwise, without the prior written permission of
the publisher. Printed in the United States of America. Published simultaneously
in Canada.
FGHIJK-HA-943210
Preface
annually at Stanford University since 1970. About fifty students have taken it
each year-juniors and seniors, but mostly graduate students-and alumni
such matters is
of these classes have begun to spawn similar courses elsewhere. Thus the time
what prefaces are
supposed to be
seems ripe to present the material to a wider audience (including sophomores).
about.”
It was a dark and stormy decade when Concrete Mathematics was born.
- P. R. Halmos 11421
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]
“People do
acquire
even asked, “Can mathematics be saved?” One of the present authors had
a little brief author- embarked on a series of books called
The
Art of Computer Programming, and
ity
by
equipping
in writing the first volume he (DEK) had found that there were mathematical
themselves with
tools missing from his repertoire; the mathematics he needed for a thorough,
jargon:
they
can
pontificate
and
air
a
well-grounded understanding of computer programs was quite different from
superficial expertise. what he’d learned as a mathematics major in college. So he introduced a new
But
what we should
course, teaching what he wished somebody had taught him.
ask
of educated
mathematicians is
The course title “Concrete Mathematics” was originally intended as an
not
what
they can
antidote to “Abstract Mathematics,” since concrete classical results were rap-
speechify
about,
idly being swept out of the modern mathematical curriculum by a new wave
nor even
what they
of abstract ideas popularly called the “New Math!’ Abstract mathematics is a
know
about
the
existing corpus
wonderful subject, and there’s nothing wrong with it: It’s beautiful, general,
of mathematical
and useful. But its adherents had become deluded that the rest of mathemat-
knowledge, but
ics was inferior and no longer worthy of attention. The goal of generalization
rather what
can
they now do with
had become so fashionable that a generation of mathematicians had become
their learning and
unable to relish beauty in the particular, to enjoy the challenge of solving
whether
they can
actually solve
math- quantitative problems, or to appreciate the value of technique. Abstract math-
ematical
problems
ematics was becoming inbred and losing touch with reality; mathematical ed-
arising in practice.
ucation needed a concrete counterweight in order to restore a healthy balance.
In short, we look for
When DEK taught Concrete Mathematics at Stanford for the first time,
deeds not words.”
- J. Hammersley [145]
he explained the somewhat strange title by saying that it was his attempt
a description of
V
“A
odience, level,
and treatment -
THIS BOOK IS BASED on
a course of the same name that has been taught

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin