|
|
Concrete Mathematics: A Foundation for Computer Science (2nd Edition) (Hardcover)
by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik
| Category:
Programming, Language & tools, Computer science, Mathematics |
| Market price: ¥ 700.00
MSL price:
¥ 578.00
[ Shop incentives ]
|
| Stock:
Pre-order item, lead time 3-7 weeks upon payment [ COD term does not apply to pre-order items ] |
MSL rating:
 Good for Gifts |
| MSL Pointer Review:
Overall this is a must-have book for anyone in CS even thought it's a little bit too hard for non math-trained people. |
| If you want us to help you with the right titles you're looking for, or to make reading recommendations based on your needs, please contact our consultants. |
Detail |
Author |
Description |
Excerpt |
Reviews |
|
|
|
Author: Ronald L. Graham, Donald E. Knuth, and Oren Patashnik
Publisher: Addison-Wesley Professional; 2 edition
Pub. in: March, 1994
ISBN: 0201558025
Pages: 672
Measurements: 9.3 x 7.5 x 1.4 inches
Origin of product: USA
Order code: BA01554
Other information: ISBN-13: 978-0201558029
|
|
Rate this product:
|
|
- MSL Picks -
This book's title can be misleading. I would say it is more of an advanced textbook on the mathematics that is a foundation for computer science than a foundational book on the mathematics of computer science. I think this misreading of the title and thus the book's content is what is behind much of the heartache that readers have when trying to tackle it. This book expands on the "Mathematical Preliminaries" portion of "The Art of Computer Programming" series of books by Knuth, and thus this book has a style much like that series of books. The book is complete and clear, but it is also densely packed with lots of theory and proofs and will require much effort and time to understand well. It is really not meant to be an applied mathematics textbook at all. I show the table of contents next. Note that there are exercises at the conclusion of each chapter with solutions in the back of the book. However, most of the exercises are not so simple that you can just glimpse at the solution and figure out how to get from A to B. I recommend it if you have the time. It can really bring out thoughts and the beauty of mathematics that you may not have considered before.
1. Recurrent Problems.
The Tower of Hanoi.
Lines in the Plane.
The Josephus Problem.
Exercises.
2. Sums.
Notation.
Sums and Recurrences.
Manipulation of Sums.
Multiple Sums.
General Methods.
Finite and Infinite Calculus.
Infinite Sums.
Exercises.
3. Integer Functions.
Floors and Ceilings.
Floor/Ceiling Applications.
Floor/Ceiling Recurrences.
'mod': The Binary Operation.
Floor/Ceiling Sums.
Exercises.
4. Number Theory.
Divisibility.
Factorial Factors.
Relative Primality.
'mod': The Congruence Relation.
Independent Residues.
Additional Applications.
Phi and Mu.
Exercises.
5. Binomial Coefficients.
Basic Identities.
Basic Practice.
Tricks of the Trade.
Generating Functions.
Hypergeometric Functions.
Hypergeometric Transformations.
Partial Hypergeometric Sums.
Mechanical Summation.
Exercises.
6. Special Numbers.
Stirling Numbers.
Eulerian Numbers.
Harmonic Numbers.
Harmonic Summation.
Bernoulli Numbers.
Fibonacci Numbers.
Continuants.
Exercises.
7. Generating Functions.
Domino Theory and Change.
Basic Maneuvers.
Solving Recurrences.
Special Generating Functions.
Convolutions.
Exponential Generating Functions.
Dirichlet Generating Functions.
Exercises.
8. Discrete Probability.
Definitions.
Mean and Variance.
Probability Generating Functions.
Flipping Coins.
Hashing.
Exercises.
9. Asymptotics.
A Hierarchy.
O Notation.
O Manipulation.
Two Asymptotic Tricks.
Euler's Summation Formula.
Final Summations.
Exercises.
A. Answers to Exercises.
B. Bibliography.
(From quoting a guest reviewer)
Target readers:
Computer science majors and undergraduated math students.
|
|
Customers who bought this product also bought:
 |
Beautiful Code: Leading Programmers Explain How They Think (Theory in Practice (O'Reilly)) [ILLUSTRATED] (Paperback)
by Andy Oram, Greg Wilson
A programming book that is simply a beauty in the eye of the programmer. |
 |
Combinatorial Optimization: Algorithms and Complexity [UNABRIDGED] (Paperback)
by Christos H. Papadimitriou, Kenneth Steiglitz
Published in 1952, this books is a masterpiece on Combinatorial Optimisation. |
 |
Introduction to Algorithms (Hardcover)
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
An academic masterpiece, this book is the definitive reference for data structures and algorithms with rigorous coverage of the most widely used algorithms. |
 |
C: A Reference Manual (5th Edition) (Paperback)
by Samuel P. Harbison, Guy L. Steele
Simply indespensible, this widely acclaimed is probably the only C reference a serious programmer needs. |
 |
Programming Pearls (2nd Edition) (ACM Press) (Paperback)
by Jon Bentley
A compendium of 15 columns previously published in Communications of the ACM, Jon Bentley's book has been a real classic on computer programming. |
 |
Code Complete, Second Edition (Paperback)
by Steve McConnell
Focusing on actual code construction, but touching on every aspect of software engineering including psychology/behavior, this book is an essential reading for every and all developers. |
 |
The Pragmatic Programmer: From Journeyman to Master (Paperback)
by Andrew Hunt, David Thomas
A classic reading on programming ranking with Code Complete and The Mythtical Man-Month. |
 |
Rapid Development (Paperback)
by Steve McConnell
A succinct, well organized and must-read collection of the lessons learned and best practices in software engineering over the last three decades. |
 |
Refactoring: Improving the Design of Existing Code (Hardcover)
by Martin Fowler, Kent Beck, John Brant, William Opdyke, Don Roberts
Full of code examples in Java, easy to read and right into target, this book is a masterly and comprehensive reference on refactoring. |
 |
The Mythical Man-Month: Essays on Software Engineering, 20th Anniversary Edition (Paperback)
by Frederick P. Brooks
Focusing on the human elements of software engineering, this classic offers insight for anyone managing complex development projects. |
 |
Head First Design Patterns (Head First) [ILLUSTRATED] (Paperback)
by Elisabeth Freeman, Eric Freeman, Bert Bates, Kathy Sierra
Written in a typically Head First refreshing style, this is one of the easiest to read and absorb among the major reference sources for design patterns. |
 |
Effective Java Programming Language Guide (Paperback)
by Joshua Bloch
An essential reference on the nuances of Java, which you’ll consult from time to time. A must-own for Java developers. |
 |
Effective C++: 55 Specific Ways to Improve Your Programs and Designs (3rd Edition) (Addison-Wesley Professional Computing Series) (Paperback)
by Scott Meyers
Focusing on productive and practical techniques and offering clearly well thought out advice, this classic on C++ language has always been worth your money and time. |
 |
The C++ Standard Library: A Tutorial and Reference (Hardcover)
by Nicolai M. Josuttis
Extremely well organized and well written, this book is an excellent reference to advanced C++ features. |
 |
The C++ Programming Language (Special 3rd Edition) (Hardcover)
by Bjarne Stroustrup
Presents the complete C++ language and a discussion of design and software development issues. Provides an emphasis on tutorial aspects aimed at the serious programmer. |
 |
Design Patterns: Elements of Reusable Object-Oriented Software (Addison-Wesley Professional Computing Series) (Hardcover)
by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides
A modern classic in the literature of object-oriented development, it's a book of design patterns that describe simple and elegant solutions to specific problems in object-oriented software design. |
|
|
Donald E. Knuth is known throughout the world for his pioneering work on algorithms and programming techniques, for his invention of the Tex and Metafont systems for computer typesetting, and for his prolific and influential writing. Professor Emeritus of The Art of Computer Programming at Stanford University, he currently devotes full time to the completion of these fascicles and the seven volumes to which they belong.
|
|
From Publisher
This book introduces the mathematics that supports advanced computer programming and the analysis of algorithms. The primary aim of its well-known authors is to provide a solid and relevant base of mathematical skills - the skills needed to solve complex problems, to evaluate horrendous sums, and to discover subtle patterns in data. It is an indispensable text and reference not only for computer scientists - the authors themselves rely heavily on it! - but for serious users of mathematics in virtually every discipline.
Concrete Mathematics is a blending of CONtinuous and disCRETE mathematics. "More concretely," the authors explain, "it is the controlled manipulation of mathematical formulas, using a collection of techniques for solving problems." The subject matter is primarily an expansion of the Mathematical Preliminaries section in Knuth's classic Art of Computer Programming, but the style of presentation is more leisurely, and individual topics are covered more deeply. Several new topics have been added, and the most significant ideas have been traced to their historical roots. The book includes more than 500 exercises, divided into six categories. Complete answers are provided for all exercises, except research problems, making the book particularly valuable for self-study.
Major topics include:
- Sums
- Recurrences
- Integer functions
- Elementary number theory
- Binomial coefficients
- Generating functions
- Discrete probability
- Asymptotic methods
This second edition includes important new material about mechanical summation. In response to the widespread use of the first edition as a reference book, the bibliography and index have also been expanded, and additional nontrivial improvements can be found on almost every page. Readers will appreciate the informal style of Concrete Mathematics. Particularly enjoyable are the marginal graffiti contributed by students who have taken courses based on this material. The authors want to convey not only the importance of the techniques presented, but some of the fun in learning and using them.
|
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 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 Hammersley 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" 176 ; other worried mathematicians 332 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 rapidly 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 mathematics 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 mathematics was becoming inbred and losing touch with reality; mathematical education 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 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, not Stone's Embedding Theorem, nor even the Stone-Cech 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. Meanwhile, independent confirmation for the appropriateness of the name came from another direction, when Z.A. Melzak published two volumes entitled Companion to Concrete Mathematics 267.
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 problems. 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, elementary number theory, binomial coefficients, generating functions, discrete probability, and asymptotic methods. The emphasis is on manipulative techniques rather than on existence theorems or combinatorial reasoning; the goal is for each reader to become as familiar with discrete operation (like the greatest integer function and finite summation) as a student of calculus is familiar with continuous operations (like the absolute-value function and infinite integration)
Notice that this list of topics is quite different from what is usually taught nowadays in undergraduate course entitled "Discrete Mathematics." Therefore the subject needs a distinctive name, and "Concrete Mathematics" has proved to be as suitable as another
The original textbook for Stanford's course on concrete mathematics was the "Mathematical Preliminaries" section in The Art of Computer Programming 207. 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 present book is an outgrowth of those notes; it is an expansion of, and a more leisurely introduction to, the material if Mathematical Preliminaries. Some of the more advanced parts have been omitted; on the other hand, several topics not found there have been included here so that the story will be complete
The authors have enjoyed putting this book together because the subject began to jell and to take on a life of its own before our eyes; this book almost seemed to write itself. Moreover, the somewhat unconventional approaches we have adopted in several places have seemed to fit together so well, after these years of experience, that we can't help feeling that this book is a kind of manifesto about our favorite way to do mathematics. So we think the book has turned out to be a tale of mathematical beauty and surprise, and we hope that our readers will share at least of the pleasure we had while writing it.
Since this book was born in a university setting, we have tried to capture the spirit of a contemporary classroom by adopting an informal style. Some people think that mathematics is a serious business that must always be cold and dry; but we think mathematics is fun, and we aren't ashamed to admit the fact. Why should a strict boundary line be drawn between work and play? Concrete mathematics is full of appealing patterns; the manipulations are not always easy, but the answers can be astonishingly attractive. The joy and sorrows of mathematical work are reflected explicitly in this book because they are part of our lives.
Students always know better than their teachers, so we have asked the first students of this material to contribute their frank opinions, as "graffiti" in the margins. Some of these marginal markings are merely corny, some are profound; some of them warn about ambiguities or obscurities, others are typical comments made by wise guys in the back row; some are positive, some are negative, some are zero. But they all are real indications of feelings that should make the text material easier to assimilate. (the inspiration for such marginal notes comes from a student handbook entitled Approaching Stanford, where the official university line is counterbalanced by the remarks of outgoing students. For example, Stanford says, "There are a few things you cannot miss in this amorphous .. what the h*** does that mean? Typical of the pseudo-intellectualism around her." Stanford: There is no end to the potential of a group of students living together." Graffito: "Stanford dorms are like zoos without a keeper."
The margins also include direct quotations from famous mathematicians of past generations, giving the actual words in which they announced some of their fundamental discoveries. Somehow it seems appropriate to mix the words of Leibniz, Euler, Gauss, and others with those of the people who will be continuing the work. Mathematics is an ongoing endeavor for people everywhere; many strands are being woven into one rich fabric.
This book contains more than 500 exercises, divided into six categories:
- Warmups are exercises that every reader should try to do when first reading the material.
- Basics are exercises to develop facts that are best learned by trying one's own derivation rather than by reading somebody else's.
- Homework exercises are problems intended to deepen an understanding of material in the current chapter.
- Exam problems typically involve ideas from two or more chapters simultaneously; they are generally intended for use in take-home exams (not for in-class exams under time pressure).
- Bonus problems go beyond what an average student of concrete mathematics is expected to handle while taking a course based on this book; they extend the text in interesting ways. Bonus problems go beyond what an average student of concrete mathematics is expected to handle while taking a course based on this book; they extend the text in interesting ways.
- Research problems may or may not be humanly solvable, but the ones presented here seen to be worth a try (without time pressure).
Answers to all the exercises appear in Appendix A, often with additional information about related results. (Of course the "answers" to research problems are incomplete; but even in these cases, partial results or hints are given that might prove to be helpful.) Readers are encouraged to look at the answers especially the answers to the warmup problems, but only after making a serious attempt to solve the problems without peeking.
|
|
A guest reviewer (MSL quote), Canada
<2008-11-12 00:00>
This book is perhaps one of the most beautifully written books I have ever read. All the proofs presented here are elegant. When reading the proofs in this book, you can feel that one sentence logically and smoothly follows from the previous sentence. This is partly because of the elegant and effective notations adopted by the authors. [Note: Donald Knuth, one of the authors, has been one of the biggest proponents of good mathematical notations. See his book titled "Mathematical Writing".]
Other reviewers have provided a summary of this book. So, I will only say that every computer scientist and combinatorialist should read at least chapters 1, 2, 5, 7, and 9. Chapter 5 is very highly recommended. Trust me: once you have mastered these chapters, you will be able to do things your colleagues just can't. Even just familiarizing yourself with the notations in this book will help you produce proofs that you probably won't be able to otherwise. [Great ideas are of course always important in every proof - but without good notations, you probably won't be able to come up with the ideas in the first place.]
There is pretty much nothing bad about this book that I am aware of. I will just say though that it takes a lot of time and effort to acquire mastery of the material. As for my own story, I started reading chapter 1 and 2 when I just got interested in discrete mathematics. It took me about 1/2 year (part time) to get through this. I came back to this book again when I took a course on "generatingfunctionology". I found that chapter 5 and 7 were indispensable. I was also forced to reread chapter 2 again because the lecturer, as most people do, just waived his hands when it comes to manipulating sums and binomial coefficients. However, all the effort that I put in paid off in the end as I could solve problems in the final exam which all my other friends could not.
In summary, I strongly recommend this book to every computer scientist and combinatorialist. I will finally remark that, if you are serious about learning concrete mathematics, you will probably find that generating functions pop up pretty much everywhere. To understand these beasts, I highly recommend Sedgewick and Flajolet's "Introduction to Analysis of Algorithms" and "Analytic Combinatorics" (not yet published, but next-to-final draft is available at Flajolet's web site), and Wilf's "Generatingfunctionology". |
|
|
|
|
