Donald Knuth – författare

Now Includes the Long-Anticipated Volume 4B!

Countless readers have spoken about the profound personal influence of Knuth's work. Scientists have marveled at the beauty and elegance of his analysis, while ordinary programmers have successfully applied his "cookbook" solutions to their day-to-day problems. All have admired Knuth for the breadth, clarity, accuracy, and good humor found in his books.

Primarily written as a reference, some people have nevertheless found it possible and interesting to read each volume from beginning to end. A programmer in China even compared the experience to reading a poem. Whatever your background, if you need to do any serious computer programming, you will find your own good reason to make each volume in this series a readily accessible part of your scholarly or professional library.

These five books comprise what easily could be the most important set of information on any serious programmer's bookshelf.

This set now includes Volume 4B, the sequel to Volume 4A, which extends Knuth's exploration of combinatorial algorithms. These algorithms are of keen interest to software designers because ". . . a single good idea can save years or even centuries of computer time."

"Donald Knuth may very well be a great master of the analysis of algorithms, but more than that, he is an incredible and tireless storyteller who always strikes the perfect balance between theory, practice, and fun. [The Art of Computer Programming, Volume 4B, Combinatorial Algorithms, Part 2,] dives deep into the fascinating exploration of search spaces (which is quite like looking for a needle in a haystack or, even harder, to prove the absence of a needle in a haystack), where actions performed while moving forward must be meticulously undone when backtracking. It introduces us to the beauty of dancing links for removing and restoring the cells of a matrix in a dance which is both simple to implement and very efficient. And it studies the iconic and versatile satisfiability problem and carefully analyses various ingredients of SAT solvers." --Christine Solnon, Department of Computer Science, INSA Lyon

This box set includes the following volumes: The Art of Computer Programming: Volume 1: Fundamental Algorithms, 3rd EditionThe Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd EditionThe Art of Computer Programming: Volume 3: Sorting and Searching, 2nd EditionThe Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1The Art of Computer Programming, Volume 4B: Combinatorial Algorithms, Part 2

The bible of all fundamental algorithms and the work that taught many of today's software developers most of what they know about computer programming.

–Byte, September 1995

 

I can't begin to tell you how many pleasurable hours of study and recreation they have afforded me! I have pored over them in cars, restaurants, at work, at home... and even at a Little League game when my son wasn't in the line-up.

–Charles Long

 

If you think you're a really good programmer... read [Knuth's] Art of Computer Programming... You should definitely send me a resume if you can read the whole thing.

–Bill Gates

 

It's always a pleasure when a problem is hard enough that you have to get the Knuths off the shelf. I find that merely opening one has a very useful terrorizing effect on computers.

–Jonathan Laventhol

 

This first volume in the series begins with basic programming concepts and techniques, then focuses more particularly on information structures–the representation of information inside a computer, the structural relationships between data elements and how to deal with them efficiently. Elementary applications are given to simulation, numerical methods, symbolic computing, software and system design. Dozens of simple and important algorithms and techniques have been added to those of the previous edition. The section on mathematical preliminaries has been extensively revised to match present trends in research.

The Art of Computer Programming is a multivolume work on the analysis of algorithms and has long been recognized as the definitive description of classical computer science. The five volumes published to date--Volumes 1, 2, 3, 4A, and 4B--already comprise a unique and invaluable resource in programming theory and practice. Countless readers have spoken about the profound personal influence of Knuth's writings. Scientists have marveled at the beauty and elegance of his analysis, while practicing programmers have successfully applied his "cookbook" solutions to their day-to-day problems. All have admired Knuth for the breadth, clarity, accuracy, and good humor found in his books.

To continue the set, and to update parts of the existing volumes, Knuth has created a series of small books called fascicles, which are published at regular intervals. Each fascicle encompasses a section or more of wholly new or revised material. Ultimately, the content of these fascicles will be rolled up into the comprehensive, final versions of each volume, and the enormous undertaking that began in 1962 will be complete.

Volume 4, Fascicle 7, which is brimming with lively examples, forms the first third of what will eventually become hardcover Volume 4C. It introduces and explores an important general framework for modeling and solving combinatorial problems, called the Constraint Satisfaction Problem (CSP). The concluding sections of Volume 4B contain expositions of two analogous frameworks, namely XCC ("exact covering with colors") and SAT ("Boolean satisfiability"); the XCC solvers and SAT solvers are now joined by CSP solvers, completing a powerful trio of techniques. Each member of the trio has its own strengths, while separately helping to understand the other two.

This fascicle illuminates how the CSP framework is tied to dozens of other parts of computer science: Scene analysis (computer vision); efficient algorithms that embed one graph in another; fascinating instances of "graceful graphs"; new ways to look ahead when backtracking; new heuristics to guide a search that backtracks through a massive space of possibilities; situations when backtracking isn't necessary.

New sparse-set data structures are introduced, leading to a technique called "dancing cells"--which often is even better than "dancing links"! Recreational topics appear throughout, including some new takes on the classic problem of a knight's tour, as well as modern puzzles such as fillomino.

Nearly 500 exercises are provided, arranged carefully for self-instruction, together with detailed answers (in fact, sometimes also with answers to the answers). All the while, the author pays significant attention to the history of the subject and its human dimensions.

The Art of Computer Programming is Knuth's multivolume analysis of algorithms. With the addition of this new volume, it continues to be the definitive description of classical computer science.

Volume 4B, the sequel to Volume 4A, extends Knuth's exploration of combinatorial algorithms. These algorithms are of keen interest to software designers because ". . . a single good idea can save years or even centuries of computer time."

The book begins with coverage of Backtrack Programming, together with a set of data structures whose links perform "delightful dances" and are ideally suited to this domain. New techniques for important applications such as optimum partitioning and layout are thereby developed.

Knuth's writing is playful, and he includes dozens of puzzles to illustrate the algorithms and techniques, ranging from popular classics like edge-matching to more recent crazes like sudoku. Recreational mathematicians and computer scientists will not be disappointed!

In the second half of the book, Knuth addresses Satisfiability, one of the most fundamental problems in all of computer science. Innovative techniques developed at the beginning of the twenty-first century have led to game-changing applications, for such things as optimum scheduling, circuit design, and hardware verification. Thanks to these tools, computers are able to solve practical problems involving millions of variables that only a few years ago were regarded as hopeless.

The Mathematical Preliminaries Redux section of the book is a special treat, which presents basic techniques of probability theory that have become prominent since the original "preliminaries" were discussed in Volume 1.

As in every volume of this remarkable series, the book includes hundreds of exercises that employ Knuth's ingenious rating system, making it easy for readers of varying degrees of mathematical training to find challenges suitable to them. Detailed answers are provided to facilitate self-study.

"Professor Donald E. Knuth has always loved to solve problems. In Volume 4B he now promotes two brand new and practical general problem solvers, namely (0) the Dancing Links Backtracking and (1) the SAT Solver. To use them, a problem is defined declaratively (0) as a set of options, or (1) in Boolean formulae. Today's laptop computers, heavily armoured with very high speed processors and ultra large amounts of memory, are able to run either solver for problems having big input data. Each section of Volume 4B contains a multitudinous number of tough exercises which help make understanding surer. Happy reading!" --Eiiti Wada, an elder computer scientist, UTokyo

"Donald Knuth may very well be a great master of the analysis of algorithms, but more than that, he is an incredible and tireless storyteller who always strikes the perfect balance between theory, practice, and fun. [Volume 4B, Combinatorial Algorithms, Part 2] dives deep into the fascinating exploration of search spaces (which is quite like looking for a needle in a haystack or, even harder, to prove the absence of a needle in a haystack), where actions performed while moving forward must be meticulously undone when backtracking. It introduces us to the beauty of dancing links for removing and restoring the cells of a matrix in a dance which is both simple to implement and very efficient." --Christine Solnon, Department of Computer Science, INSA Lyon

Register your book for convenient access to downloads, updates, and/or corrections as they become available.

The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1

Knuth’s multivolume analysis of algorithms is widely recognized as the definitive description of classical computer science. The first three volumes of this work have long comprised a unique and invaluable resource in programming theory and practice. Scientists have marveled at the beauty and elegance of Knuth’s analysis, while practicing programmers have successfully applied his “cookbook” solutions to their day-to-day problems.

The level of these first three volumes has remained so high, and they have displayed so wide and deep a familiarity with the art of computer programming, that a sufficient “review” of future volumes could almost be: “Knuth, Volume n has been published.”

–Data Processing Digest

Knuth, Volume n has been published, where n = 4A.

In this long-awaited new volume, the old master turns his attention to some of his favorite topics in broadword computation and combinatorial generation (exhaustively listing fundamental combinatorial objects, such as permutations, partitions, and trees), as well as his more recent interests, such as binary decision diagrams.

The hallmark qualities that distinguish his previous volumes are manifest here anew: detailed coverage of the basics, illustrated with well-chosen examples; occasional forays into more esoteric topics and problems at the frontiers of research; impeccable writing peppered with occasional bits of humor; extensive collections of exercises, all with solutions or helpful hints; a careful attention to history; implementations of many of the algorithms in his classic step-by-step form.

There is an amazing amount of information on each page. Knuth has obviously thought long and hard about which topics and results are most central and important, and then, what are the most intuitive and succinct ways of presenting that material. Since the areas that he covers in this volume have exploded since he first envisioned writing about them, it is wonderful how he has managed to provide such thorough treatment in so few pages.

–Frank Ruskey, Department of Computer Science, University of Victoria

The book is Volume 4A, because Volume 4 has itself become a multivolume undertaking. Combinatorial searching is a rich and important topic, and Knuth has too much to say about it that is new, interesting, and useful to fit into a single volume, or two, or maybe even three. This book alone includes approximately 1500 exercises, with answers for self-study, plus hundreds of useful facts that cannot be found in any other publication. Volume 4A surely belongs beside the first three volumes of this classic work in every serious programmer’s library.

Finally, after a wait of more than thirty-five years, the first part of Volume 4 is at last ready for publication. Check out the boxed set that brings together Volumes 1 - 4A in one elegant case, and offers the purchaser a $50 discount off the price of buying the four volumes individually.

p> The Art of Computer Programming, Volumes 1-4A Boxed Set, 3/e

ISBN: 0321751043

The Art of Computer Programming, Volume 4C: Combinatorial Algorithms, Part 3

This volume will continue the story of methods that make it possible to solve many types of large problems that were long thought to be well beyond the reach of feasible computation. The fascinating field of combinatorial algorithms features numerous instances where a single good idea can make a program run thousands of times faster.

According to present plans, Volume 4C will contain the following sections, which are currently being assembled about seven major subareas:

7.2.2.3 Constraint Satisfaction

[The above section was published in paperback as Volume 4, Fascicle 7.]

7.2.2.4 Hamiltonian paths and cycles

7.2.2.5 Cliques

7.2.2.6 Covers

[The above three sections are planned to appear together as Volume 4, Fascicle 8.]

7.2.2.7 Squares

7.2.2.8 A Potpourri of Puzzles

7.2.2.9 Estimating Backtrack Costs

[The above three sections are planned to appear together as Volume 4, Fascicle 9.]

As usual, the emphasis is on connections between theory and practice, with careful attention to the history of the subject, together with hundreds of worked exercises.

Nearly 30 years ago, John Horton Conway introduced a new way to construct numbers. Donald E. Knuth, in appreciation of this revolutionary system, took a week off from work on The Art of Computer Programming to write an introduction to Conway's method. Never content with the ordinary, Knuth wrote this introduction as a work of fiction--a novelette. If not a steamy romance, the book nonetheless shows how a young couple turned on to pure mathematics and found total happiness. The book's primary aim, Knuth explains in a postscript, is not so much to teach Conway's theory as "to teach how one might go about developing such a theory." He continues: "Therefore, as the two characters in this book gradually explore and build up Conway's number system, I have recorded their false starts and frustrations as well as their good ideas. I wanted to give a reasonably faithful portrayal of the important principles, techniques, joys, passions, and philosophy of mathematics, so I wrote the story as I was actually doing the research myself."...It is an astonishing feat of legerdemain. An empty hat rests on a table made of a few axioms of standard set theory.Conway waves two simple rules in the air, then reaches into almost nothing and pulls out an infinitely rich tapestry of numbers that form a real and closed field.Every real number is surrounded by a host of new numbers that lie closer to it than any other "real" value does. The system is truly "surreal." quoted from Martin Gardner, Mathematical Magic Show, pp. 16--19 Surreal Numbers, now in its 13th printing, will appeal to anyone who might enjoy an engaging dialogue on abstract mathematical ideas, and who might wish to experience how new mathematics is created. 0201038129B04062001

The Complete Source Code and Program Listing for TeX Now, 35 years after the first edition, the leading worldwide experts on these systems have spent several months inspecting every page thoroughly. We now believe that every "i" has been properly dotted, every "t" has been properly crossed, and every bug has been properly exterminated. Donald E. Knuth, creator of the exciting TeX computer typesetting system, has made available in this volume the fully documented program listing for TeX. Readers who are already familiar with TeX and with its user's guide, The TeXbook, will find much of interest in the source code. Other readers interested in software development and in Knuth's programming style will find this a fascinating and instructive case study. Never before has a computer program of this size been spelled out so clearly and completely. Knuth presents all the algorithms and explains every detail of the TeX program, utilizing the WEB system of structured documentation that he developed as part of his TeX research project. TeX: The Program is the second in a five-volume series on Computers and Typesetting, all authored by Knuth. This series presents the results of nearly a decade of innovative research on the problems of preparing publications of high quality.

The Complete Design of a Large Family of Fonts Now, 35 years after the first edition, the leading worldwide experts on these systems have spent several months inspecting every page thoroughly. We now believe that every "i" has been properly dotted, every "t" has been properly crossed, and every bug has been properly exterminated. This volume contains precise definitions of about 500 letters, numerals, and other symbols, all described with METAFONT, Donald E. Knuth's revolutionary language for the design of typefaces. Readers will learn how to make their own personal variations of the fonts, simply by changing a few parameters. Special symbols that are needed for unusual applications can also be created by using the many examples in this book as a model. More ambitious readers will be able to extend this work to other character sets, such as phonetic or Cyrillic alphabets. A close study of the details captured in these METAFONT programs will reveal many previously unpublished tricks that type designers have learned during the past centuries. Computer Modern is a family of typefaces that includes 75 standard fonts, ranging from the sans-serif faces used to typeset the copy on this book jacket to the more formal alphabets and mathematical symbols used to typeset the text of the book itself. The 75 standard fonts can easily be extended to an essentially infinite number of further variations, because Computer Modern is a "meta-design" rather than a single design. In particular, this means that different point sizes of type can be drawn to different specifications, thereby obtaining better readability. Compatible typefaces can be generated for all sorts of printing equipment, ranging from low-resolution CRT displays to medium-resolution laser printers to high-resolution phototypesetters. Charles Bigelow's introduction explains the history of the "modern" style of the type design, which originated 200 years ago and is being brought up to date by the developments in this book. The type designs are accompanied by almost 750 illustrations, which are interesting in their own right as examples of mechanically constructed letterforms. Specimens of the 75 standard fonts appear near the close of this book, followed by several comprehensive indexes. Computer Modern Typefaces is the fifth in a five-volume series on Computers and Typesetting, all authored by Knuth. This series presents the results of nearly a decade of innovative research on the problems of preparing publications of high typographic quality.

Check out the boxed set that brings together Volumes 1 - 4B in one elegant case.

 

The Art of Computer Programming, Volumes 1-4B Boxed Set

ISBN: 9780137935109

 

Art of Computer Programming, Volume 1, Fascicle 1, The: MMIX -- A RISC Computer for the New Millennium

 

This multivolume work on the analysis of algorithms has long been recognized as the definitive description of classical computer science. The three complete volumes published to date already comprise a unique and invaluable resource in programming theory and practice. Countless readers have spoken about the profound personal influence of Knuth's writings. Scientists have marveled at the beauty and elegance of his analysis, while practicing programmers have successfully applied his "cookbook" solutions to their day-to-day problems. All have admired Knuth for the breadth, clarity, accuracy, and good humor found in his books.

To begin the fourth and later volumes of the set, and to update parts of the existing three, Knuth has created a series of small books called fascicles, which will be published t regular intervals. Each fascicle will encompass a section or more of wholly new or evised material. Ultimately, the content of these fascicles will be rolled up into the comprehensive, final versions of each volume, and the enormous undertaking that began in 1962 will be complete.

 

Volume 1, Fascicle 1

This first fascicle updates The Art of Computer Programming, Volume 1, Third Edition: Fundamental Algorithms, and ultimately will become part of the fourth edition of that book. Specifically, it provides a programmer's introduction to the long-awaited MMIX, a RISC-based computer that replaces the original MIX, and describes the MMIX assembly language. The fascicle also presents new material on subroutines, coroutines, and interpretive routines.

 

Ebook (PDF version) produced by Mathematical Sciences Publishers (MSP),http://msp.org

The bible of all fundamental algorithms and the work that taught many of today's software developers most of what they know about computer programming.

 

–Byte, September 1995

 

I can't begin to tell you how many pleasurable hours of study and recreation they have afforded me! I have pored over them in cars, restaurants, at work, at home... and even at a Little League game when my son wasn't in the line-up.

 

–Charles Long

 

If you think you're a really good programmer... read [Knuth's] Art of Computer Programming... You should definitely send me a resume if you can read the whole thing.

 

–Bill Gates

 

It's always a pleasure when a problem is hard enough that you have to get the Knuths off the shelf. I find that merely opening one has a very useful terrorizing effect on computers.

 

–Jonathan Laventhol

 

The second volume offers a complete introduction to the field of seminumerical algorithms, with separate chapters on random numbers and arithmetic. The book summarizes the major paradigms and basic theory of such algorithms, thereby providing a comprehensive interface between computer programming and numerical analysis. Particularly noteworthy in this third edition is Knuth's new treatment of random number generators, and his discussion of calculations with formal power series.

The Complete Source Code and Program Listing for METAFONT Now, 35 years after the first edition, the leading worldwide experts on these systems have spent several months inspecting every page thoroughly. We now believe that every "i" has been properly dotted, every "t" has been properly crossed, and every bug has been properly exterminated. This volume contains the fully documented program listing for METAFONT, Donald E. Knuth's revolutionary typeface design language. Readers interested in software development and in Knuth's programming style will find this a fascinating and instructive case study. Never before has a computer program with this much size and variety been spelled out so clearly and completely. Knuth presents all the algorithms and explains every detail of the METAFONT program, utilizing the WEB system of structured documentation that he developed as part of his TeX research project. METFONT's new algorithms for computer graphics make this program especially interesting; traditional algorithms of parsing and macro expansion are present too, often with new twists. This book is an excellent lesson by example on how to put programming theory into practice. METAFONT: The Program is the fourth in a five-volume series on Computers and Typesetting, all authored by Knuth. This series presents the results of nearly a decade of innovative research on the problems of preparing publications of high typographic quality.

Here is the definitive guide to the use of TeX, written by the system's creator, Donald E. Knuth. TeX represents the state of the art in computer typesetting. It is particularly valuable where the document, article, or book to be produced contains a lot of mathematics, and where the user is concerned about typographic quality. TeX software offers both writers and publishers the opportunity to produce technical text of all kinds, in an attractive form, with the speed and efficiency of a computer system. Novice and expert users alike will gain from The TeXbook the level of information they seek. Knuth warns newcomers away from the more difficult areas, while he entices experienced users with new challenges. The novice need not learn much about TeX to prepare a simple manuscript with it. But for the preparation of more complex documents, The TeXbook contains all the detail required. Knuth's familiar wit, and illustrations specially drawn by Duane Bibby, add a light touch to an unusually readable software manual. The TeXbook is the first in a five-volume series on Computers and Typesetting, all authored by Knuth. 0201134470B04062001