Resumo de The Art Of Computer Programming

The tale of how Donald Knuth took a decade off from writing The
Art of Computer Programming to create the TeX typesetting language is one of the great
legends of computer science. The appearance of a third edition of The Art
of Computer Programming ? typeset in you will never guess what! ? is
therefore a landmark event.

For those unfamiliar with the work, it is not about computer programming in
the broad sense, but about the algorithms and methods which lie at the heart of
most computer systems. Fundamental Algorithms contains background
information for the series. Chapter one provides mathematical preliminaries and
basic programming concepts, along with an introduction to the MIX assembly
language, used throughout for implementations. Chapter two covers simple
information structures: lists, trees, and related data structures.

The two chapters in Seminumerical Algorithms cover pseudo-random
numbers ? their generation and statistical testing ? and numerical computation
? doing arithmetic with floating point numbers, rationals, and polynomials.
Almost everyone who has ever programmed has written a bubble sort at some
point, but the full complexities of sorting algorithms are another story
entirely. After an introduction to the mathematics of permutations, Sorting
and Searching presents and analyses an extensive array of algorithms for
sorting in memory (insertion, exchange, selection, merging, and distribution
algorithms), sorting on secondary storage, and searching.

The Art of Computer Programming is not a work for everyone, not
even for all programmers. It will be a valuable reference for those working on
the implementation and optimization of key algorithms and data structures, but
the more mathematically inclined will dip into it simply for pleasure. Knuth
himself clearly enjoys the subtleties of the mathematics as much as anything:
he writes at one point

Even if sorting were almost useless, there would be plenty
of rewarding reasons for studying it anyway! The ingenious algorithms that have
been discovered show that sorting is an extremely interesting topic to explore
in its own right. Many fascinating unsolved problems remain in this area, as
well as quite a few solved ones.

And he provides some gloriously learned historical tidbits and mathematical
digressions. The mathematics is heavy going in places, but the more
difficult sections are marked and the material is laid out in such a way that
those seeking algorithms to implement and performance analyses can skip the
proofs and derivations and the more esoteric material.

Exercises are liberally provided, along with proper answers, which take up
around a quarter of each volume. The exercises are carefully graded in
difficulty on a scale from 0 to 50, and range from trivial tests of definitions
to unsolved research problems. Reading The Art of Programming is a
serious enough undertaking in itself but
anyone who succeeds in doing all the exercises will have earned themselves
several doctorates.

There is plenty of new material in this third edition, including new
algorithms, examples, and exercises. The somewhat archaic MIX language has been
retained, but we are promised its replacement by a modern, RISC MMIX in the
next edition. Another incentive to purchase this edition, for those who already
have the second, is the vastly improved typesetting. But the most exciting news
of all is that volumes four and five are finally going to appear, followed by
another revision of volumes one to three and then maybe by volumes six and
seven (on the theory of languages and compilers).

Resumos Relacionados