The Art of Computer Programming
The Art of Computer Programming ( TAOCP , German The Art of Computer Programming ) is a multi-volume work by the US computer scientist Donald E. Knuth on basic algorithms and data structures , for whose typesetting he developed the programs TeX and Metafont .
The example programs are presented in an assembly language devised by Knuth , which he developed for a fictitious "ideal" computer called MIX ; this was replaced with volume 4a by the "successor model" MMIX . It uses the assembler language MIXAL (MIX-Assembler-Language). It is planned to revise volumes 1–3 and to rewrite all code examples on MMIX. Knuth justified the radical step of using his own assembly language, consistently with both technical and educational arguments and the intention of creating a long-term work that should not be influenced by the respective fashion programming language.
From a compiler book to a multi-volume basic work
Originally, the publisher had commissioned Knuth, who was still a graduate student at the time, to write a single book about compilers . However, Knuth wanted to present all the necessary knowledge on this topic and in a fully developed form.
“I figured, as long as I'm going to do a book on compilers, I should include a few other chapters on basic techniques that people would use before they got all the way to compilers. So I threw in a chapter on everything I was interested in. ”
“I thought if I was writing a book on compilers I should include a few chapters on basic techniques that people would encounter before they encounter compilers. So I put a chapter on every topic that I was interested in. "
After completing his studies, he wrote to the publisher asking for permission to describe things in a little more detail.
"Do you mind if I make this book a little bit longer, because I think there's a need for explaining these things in somewhat more detail."
"Would you mind if I made the book a little more extensive, as I think these things need a little more detailed explanation."
The response from his publisher was positive.
“They said, 'Oh no, go right ahead. Make it as long as you feel necessary. '”
“They said, 'But no, get started right away. Make it as extensive as you think necessary. '"
The first handwritten draft from 1967 was 3900 pages. So the plan arose to write a seven-part series covering the essential basics of computer programming .
Structure of the book series
The series is planned as follows:
- Volume 1. Fundamental Algorithms (first edition 1968)
- Chapter 1: Basic Concepts
- Chapter 2: Information Structures
- Volume 2. Seminumerical Algorithms (first edition 1969)
- Chapter 3: Random Numbers
- Chapter 4: Arithmetic
- Volume 3. Sorting and Searching (first edition 1973)
- Chapter 5: Sorting
- Chapter 6: Searching
- Volume 4. Combinatorial Algorithms (first edition 2011)
- Chapter 7: Combinatorial Searching
- Chapter 8: Recursion
- Volume 5. Syntactical Algorithms (planned release date 2025)
- Chapter 9: Lexical Scanning
- Chapter 10: Parsing
- Volume 6. The Theory of Context Free Languages
- Chapter 11: The Theory of Context Free Languages
- Volume 7. Compilers
- Chapter 12: Compilers
So far, the first three parts and one chapter have been published, in several revised editions. A fascicle with the specification of MMIX was published in 2005 for volume 1 . Volume 4 has also been published in advance in the form of two fascicles per year since 2005. Volume 4A has been available since February 2011. On Knuth's website, the first pre-fascicles are available as fascicles before they are published, so that interested parties can find the first errors before printing. Volumes 4B and 4C (and possibly more) are to follow.
In addition to the books mentioned above, there is another by Graham / Knuth / Patashnik Concrete Mathematics , which deals with the mathematical fundamentals of Volume 1 in more detail.
Work progress and appreciation of the work
Although Knuth began writing in 1962, it is not yet possible to foresee when the work will be completed. The author expects volume 5 to be completed in 2025 and then plans to (again) update and revise volumes 1 to 3 and to summarize the most important contents of the five volumes in a new work. He then only wanted to write the "more specialized" volumes 6 and 7 if their topics were then "still relevant and not yet said".
Knuth has been retired since 1992 to devote himself exclusively to completing his book series. He doesn't get a salary as a result, on the other hand The Art of Computer Programming is a commercially very successful series: from the first publication date to 1987 between 1000 and 2000 copies were sold every month.
While working on the revised new edition of Volume 2, Knuth struggled with the inadequacies of the typesetting techniques of the time and finally developed his own system, the TeX digital typesetting system , which has now become the standard for publications in mathematics and the natural sciences.
The accuracy of his work, which the American Scientist counts as one of the best twelve scientific monographs of the 20th century, is so important to Knuth that he regularly publishes extensive error corrections down to the smallest typographical error and the first to find any error with a check for US $ 256 -Cent for errors in content or 32 US cents for comma errors and Ä. honored. However, the checks are not cashed by most recipients - only nine were cashed - but framed. Since October 2008, however, the checks are no longer issued in US dollars, but in the virtual, hexadecimal currency of the Bank of San Serriff - Knuth justifies this with the fear of check fraud.
At the end of each chapter there is a section on history and bibliography with historical information. The exercises are classified according to the level of difficulty (and marked accordingly), ranging from extremely easy (00) to a research problem that has not yet been solved (50).
literature
- Karen A. Frenkel: Donald E. Knuth - Scholar with a Passion for the Particular. In: Communications of the ACM. Vol. 30, No. October 10, 1987
- Donald E. Knuth: The Art of Computer Programming
- Vol. 1: Fundamental Algorithms. 3rd edition. Addison-Wesley 1997, ISBN 0-201-89683-4 , 672 pages
- Vol. 1, Fascicle 1: MMIX - A RISC Computer for the New Millennium. Addison-Wesley 2005, ISBN 0-201-85392-2 , 134 pages
- Vol. 2: Seminumerical Algorithms. 3rd edition. Addison-Wesley 1998, ISBN 0-201-89684-2 , 784 pages
- Vol. 3: Sorting and Searching. 2nd edition. Addison-Wesley 1998, ISBN 0-201-89685-0 , 800 pages
- Vol. 4A: Combinatorial Algorithms. Addison-Wesley 2011, ISBN 0-201-03804-8 , 883 pages
Web links
- The Art of Computer Programming (TAOCP) on Donald E. Knuth's website
Footnotes
- ^ A b Karen A. Frenkel: Donald E. Knuth - Scholar with a Passion for the Particular. In: Communications of the ACM. Vol. 30, No. October 10, 1987
- ^ Don Knuth: The Art of Computer Programming (TAOCP) - Future Plans
- ^ Philip & Phylis Morrison: 100 or so Books that Shaped a Century of Science . In: American Scientist. November / December 1999
- ↑ https://www.heise.de/newsticker/meldung/Zahlen-bitte-Der-hexadezimale-Dollar-von-Donald-E-Knuth-3579447.html
- ^ Don Knuth: Recent News: Financial Fiasco