Donald E. Knuth: The Art of Computer Programming, Volumn 4 !

JerryZhou

http://www.cs.utsa.edu/~wagner/knuth/

arxor

还没出来吧......
Combinatorial Algorithms...值得期待...

freesky64

这里有人读这套书吗？交流一下经验呀。

JerryZhou

http://www-cs-faculty.stanford.edu/~knuth/taocp.html#vol4

Volume 4

Combinatorial Algorithms, in preparation. (Some parts are already available; see below.)
Present plans are to publish ``Volume 4'' as at least three separate subvolumes:

    * Volume 4A, Enumeration and Backtracking
          o 7. Introduction
          o 7.1. Boolean techniques (aka bit fiddling)
          o 7.2. Generating all possibilities
          o 7.2.1. Combinatorial generators
          o 7.2.2. Basic backtrack
          o 7.2.3. Efficient backtracking
          o 7.3. Shortest paths
    * Volume 4B, Graph and Network Algorithms
          o 7.4. Graph algorithms
          o 7.4.1. Components and traversal
          o 7.4.2. Special classes of graphs
          o 7.4.3. Expander graphs
          o 7.4.4. Random graphs
          o 7.5. Network algorithms
          o 7.5.1. Distinct representatives
          o 7.5.2. The assignment problem
          o 7.5.3. Network flows
          o 7.5.4. Optimum subtrees
          o 7.5.5. Optimum matching
          o 7.5.6. Optimum orderings
          o 7.6. Independence theory
          o 7.6.1. Independence structures
          o 7.6.2. Efficient matroid algorithms
    * Volume 4C and possibly 4D, Optimization and Recursion
          o 7.7. Discrete dynamic programming
          o 7.8. Branch-and-bound techniques
          o 7.9. Herculean tasks (aka NP-hard problems)
          o 7.10. Near-optimization
          o 8. Recursion

The material will first appear in beta-test form as fascicles of approximately 128 pages each, issued approximately twice per year. These fascicles will represent my best attempt to write a comprehensive account, but computer science has grown to the point where I cannot hope to be an authority on all the material covered in these books. Therefore I'll need feedback from readers in order to prepare the official volumes later.

Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005), v+128pp. ISBN 0-201-85393-0
Volume 4 Fascicle 3, Generating All Combinations and Partitions (2005), vi+150pp. ISBN 0-201-85394-9
Some "pre-fascicles" are also available for alpha-testing: Pre-Fascicle 0b (Boolean basics); Pre-Fascicle 4a (Generating all trees); Pre-Fascicle 4b (History of combinatorial generation). I've put them online primarily so that experts in the field can check the contents before I inflict them on a wider audience. But if you want to help debug them, please go right ahead.
Volume 5

Syntactic Algorithms, in preparation.

    * 9. Lexical scanning (includes also string search and data compression)
    * 10. Parsing techniques

Estimated to be ready in 2010.
Future plans

As I write Volumes 4 and 5, I'll need to refer to topics that belong logically in Volumes 1--3 but weren't invented yet when I wrote those books. Instead of putting such material artificially into Volumes 4 or 5, I'll put it into fascicle form. The first such fascicle is in fact ready now (see above): It describes MMIX, a RISC machine that will take the place of MIX in all subsequent editions.

Download the 16 Feb 2004 version of Volume 1 Fascicle 1 (583KB of compressed PostScript)

After Volume 5 has been completed, I will revise Volumes 1--3 again to bring them up to date. In particular, the new material for those volumes that has been issued in beta-test fascicles will be incorporated at that time.

Then I will publish a ``reader's digest'' edition of Volumes 1--5, condensing the most important material into a single book.

And after Volumes 1--5 are done, God willing, I plan to publish Volume 6 (the theory of context-free languages) and Volume 7 (Compiler techniques), but only if the things I want to say about those topics are still relevant and still haven't been said. Volumes 1--5 represent the central core of computer programming for sequential machines; the subjects of Volumes 6 and 7 are important but more specialized.