Donald Knuth

Home * People * Donald Knuth

Donald Knuth ¹

Donald Ervin Knuth,
a renowned computer scientist, mathematician, writer, scholar, and Professor Emeritus at Stanford University, California, United States ¹. He is the author of the multi-volume work The Art of Computer Programming, and been called the "father" of the analysis of algorithms - in 1975 he analyzed Alpha-Beta along with Ronald W. Moore, first formulating its Node Types ². Beside his fundamental contributions to several branches of computer science and mathematics, Knuth is the creator of the TeX computer typesetting system.

Quotes

McCarthy

Quote by John McCarthy from Human-Level AI is harder than it seemed in 1955 on the Dartmouth workshop:

Chess programs catch some of the human chess playing abilities but rely on the limited effective branching of the chess move tree. The ideas that work for chess are inadequate for go. Alpha-beta pruning characterizes human play, but it wasn't noticed by early chess programmers - Turing, Shannon, Pasta and Ulam, and Bernstein. We humans are not very good at identifying the heuristics we ourselves use. Approximations to alpha-beta used by Samuel, Newell and Simon, McCarthy. Proved equivalent to minimax by Hart and Levin, independently by Brudno. Knuth gives details.

Knuth

Selected quotes by Donald Knuth ³

• A mathematical formula should never be "owned" by anybody! Mathematics belong to God. ⁴
• Beware of bugs in the above code; I have only proved it correct, not tried it. ⁵
• We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. ⁶

Alpha-Beta

Alpha-Beta F2 and Iterative Solution ⁷

• Knuth and Moore‘s famous Function F2, aka AlphaBeta
• Knuth already introduced an iterative solution

See also

• Backtracking
• History of Computer Chess
• History of Alpha-Beta

Selected Publications

⁸⁹

1960 ...

• Donald Knuth (1960). An Imaginary Number System. Communications of the ACM, Vol. 3, No. 4
• Donald Knuth (1962). The calculation of Easter. Communications of the ACM, Vol. 5, No. 4
• Donald Knuth (1964). backus normal form vs. Backus Naur form. Communications of the ACM, Vol. 7, No. 12 ¹⁰
• Donald Knuth (1968 ...). The Art of Computer Programming (TAOCP) ¹¹

Volume 1 - Fundamental Algorithms (1968)

Volume 2 - Seminumerical Algorithms (1969)

Volume 3 - Sorting and Searching (1973)

Volume 4A - Combinatorial Algorithms, Part 1 (2011)

New material for Volume 4 will first appear in beta-test form as fascicles

Volume 4 Fascicle 0, Introduction to Combinatorial Algorithms and Boolean Functions (2008)

Volume 4 Fascicle 1, Bitwise Tricks & Techniques; Binary Decision Diagrams (2009)

Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005)

Volume 4 Fascicle 3, Generating All Combinations and Partitions (2005)

Volume 4 Fascicle 4, Generating All Trees; History of Combinatorial Generation (2006)

Volume 5 - Syntactic Algorithms, planned (estimated in 2020).

1970 ...

• Donald Knuth (1970). Von Neumann's First Computer Program. ACM Computing Surveys, Vol. 2, No. 4
• Donald Knuth (1974). Structured Programming with go to Statements. ACM Computing Surveys, Vol. 6, No. 4, pdf » goto
• Ole Amble, Donald Knuth (1974). Ordered Hash Tables. The Computer Journal, Vol. 17
• Donald Knuth (1974). Estimating efficiency of backtrack programs. STAN-CS-74-442, CS-Department, Stanford University ¹²
• Donald Knuth (1974). Surreal Numbers - How two ex-students turned on to pure mathematics and found total happiness. Addison-Wesley ^{13 14}
• Donald Knuth (1974). Computer Programming as an Art. Communications of the ACM, Vol. 17, No. 12
• Donald Knuth (1974). Computer Programming as an Art. Turing Award Lecture, pdf
• Donald Knuth (1975). Estimating the Efficiency of Backtrack Programs. Mathemathics of Computation, Vol. 29 » Backtracking
• Donald Knuth, Ronald W. Moore (1975). An analysis of alpha-beta pruning. Artificial Intelligence, Vol. 6, No. 4, pp 293–326. Reprinted in Donald Knuth (2000). Selected Papers on Analysis of Algorithms. CSLI lecture notes series 102, ISBN 1-57586-212-3
• Donald Knuth, James H. Morris, Jr., Vaughan R. Pratt (1977). Fast Pattern Matching in Strings. SIAM Journal on Computing, Vol. 6, No. 2 ¹⁵

1980 ...

• Andrei P. Ershov, Donald Knuth (Eds.) (1981). Algorithms in Modern Mathematics and Computer Science. Proceedings, Urgench, Uzbek SSR, September 16-22, 1979. Lecture Notes in Computer Science, Vol. 122, Springer » Ershov Archive
• Donald Knuth (1985). An Analysis of Optimum Caching. Journal of Algorithms, Vol. 6
• Donald Knuth (1986). TeX: The Program. Addison-Wesley ¹⁶
• Donald Knuth (1986, 1996). The TeXbook. Addison-Wesley, pdf
• Ronald L. Graham, Donald Knuth, Oren Patashnik (1989, 1994). Concrete Mathematics. Second Edition, Addison-Wesley

1990 ...

• Lee Sallows, Martin Gardner, Richard K. Guy, Donald Knuth (1991). Serial Isogons of 90 Degrees. Mathematics Magazine, Vol. 64, No. 5
• Donald Knuth (1991). Textbook examples of recursion. arXiv:cs/9301113 » Recursion
• Donald Knuth (1992). Literate Programming. CSLI lecture notes series 27 ¹⁷
• Donald Knuth (1996). Selected Papers on Computer Science. CSLI lecture notes series 59
• Donald Knuth (1999). Digital Typography. CSLI lecture notes series 78

2000 ...

• Donald Knuth (2000). Dancing Links arXiv:cs/0011047v1.
• Donald Knuth (2000). Selected Papers on Analysis of Algorithms. CSLI lecture notes series 102
• Donald Knuth (2001). Arithmetik. Springer, ISBN 978-3-540-66745-2
• Donald Knuth (2003). Selected Papers on Discrete Mathematics. CSLI lecture notes series 106
• Donald Knuth (2003). Selected Papers on Computer Languages. CSLI lecture notes series 139
• Donald Knuth (2003). Things a Computer Scientist Rarely Talks About. CSLI lecture notes series 202

2010 ...

• Donald Knuth (2010). Selected Papers on Design of Algorithms. CSLI lecture notes series 191, Cambridge University Press, ISBN 978-1-57586-582-9
• Donald Knuth (2011). Selected Papers on Fun and Games. CSLI lecture notes series 192, Cambridge University Press, ISBN 978-1-57586-584-3
• Donald Knuth (2012). Companion to the Papers of Donald Knuth. CSLI lecture notes series 202, Cambridge University Press, ISBN 978-1-57586-634-5
• Donald Knuth (2012). Satisfiability and The Art of Computer Programming. SAT 2012, Lecture Notes in Computer Science, Vol. 7317, Springer
• Christos H. Papadimitriou, Leonard Adleman, Richard Karp, Donald Knuth, Robert E. Tarjan, Leslie Valiant (2012). An Algorithmic View of the Universe. ACM-Turing 2012

External Links

Donald Knuth

• Don Knuth’s home page
• Donald Knuth from Wikipedia
• Donald Knuth - Wikiquote
• The Mathematics Genealogy Project - Donald Knuth
• Knuth biography - MacTutor
• Donald E. Knuth - A.M. Turing Award Winner
• Fellow Awards | Donald Knuth from The Computer History Museum
• Computer Musings by Professor Donald E. Knuth | Stanford University Online
• The Programmer Dress Code | CodeThinked by Justin Etheredge, December 6, 2007
• Donald Knuth's First Computer - good coders code, great reuse by Peteris Krumins, February 26, 2010
• In praise of Knuth and Liskov from Bertrand Meyer's technology+ blog, May 22, 2011 » Barbara Liskov
• Donald Knuth in Alan Turing Year from I Programmer - programming, reviews and projects, January 10, 2012 » Alan Turing

Ershov Archive

• Algorithms in Modern Mathematics and Computer Science - 1979 Andrei Ershov Archive » Algorithms in Modern Mathematics and Computer Science - Proceedings

Dancing D. Knuth

Khiva, summer hall; dancers, D.Knuth

Andrey Ershov, Donald E. Knuth

Khiva, summer hall; A. van Wijngaarden, Zemaneks, D.Knuth. F.Strassen, B.Trakhtenbrot

Interviews

• Donald Knuth - Computer Literacy Bookshops Interview, December 07, 1993
• An interview with Donald Knuth (pdf) by Jack Woehr, Dr. Dobb's Journal, April 1996
• Interview with Donald E. Knuth by Gianluca Pignalberi, Free Software Magazine, September 04, 2005
• Interview with Donald Knuth by Donald Knuth and Andrew Binstock, 1, April 25, 2008 » Itanium

Topics

• Dancing Links from Wikipedia
• Knuth's Algorithm X from Wikipedia
• Knuth–Bendix completion algorithm from Wikipedia
• Knuth–Morris–Pratt algorithm from Wikipedia
• Knuth reward check from Wikipedia
• MMIX 2009 a RISC computer for the third millennium

MMIX News

MMIX from Wikipedia

• Robinson–Schensted–Knuth correspondence from Wikipedia
• TeX from Wikipedia

Metafont from Wikipedia

• The Art of Computer Programming
• The Art of Computer Programming from Wikipedia

Videos

• Vienna Gödel Lecture 2013: Donald E. Knuth, Vienna University of Technology, YouTube Video

Watch on YouTube

References