Donald Knuth
Donald Knuth [1]
Donald Ervin Knuth,
a renowned computer scientist, mathematician, writer, scholar, and Professor Emeritus at Stanford University, California, United States [2]. 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 [3]. Beside his fundamental contributions to several branches of computer science and mathematics, Knuth is the creator of the TeX computer typesetting system.
Contents
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 [4]
- A mathematical formula should never be "owned" by anybody! Mathematics belong to God. [5]
- Beware of bugs in the above code; I have only proved it correct, not tried it. [6]
- We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. [7]
Alpha-Beta
Alpha-Beta F2 and Iterative Solution [8]
See also
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 [11]
- Donald Knuth (1968 ...). The Art of Computer Programming (TAOCP) [12]
- 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 [13]
- Donald Knuth (1974). Surreal Numbers - How two ex-students turned on to pure mathematics and found total happiness. Addison-Wesley [14] [15]
- 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 [16]
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 [17]
- 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 [18]
- 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
Videos
- Vienna Gödel Lecture 2013: Donald E. Knuth, Vienna University of Technology, YouTube Video
References
- ↑ Donald Knuth at a reception for the Open Content Alliance, hosted by the Internet Archive. Taken October 25, 2005 by Jacob Appelbaum in San Francisco, Donald Knuth from Wikipedia
- ↑ Computer Musings by Professor Donald E. Knuth | Stanford University Online
- ↑ 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 - Wikiquote
- ↑ Donald Knuth (1999). Digital Typography. CSLI lecture notes series 78
- ↑ Knuth: Frequently Asked Questions - What's the exact citation of your oft-cited comment about bugs?
- ↑ Donald Knuth (1974). Structured Programming with go to Statements. ACM Computing Surveys, Vol. 6, No. 4, pdf
- ↑ 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, pdf
- ↑ Preprints of Recent Papers including dancing links
- ↑ dblp: Donald E. Knuth
- ↑ Backus–Naur Form from Wikipedia
- ↑ The Art of Computer Programming from Wikipedia
- ↑ Re: Perft(15) estimate after averaging 800 MC samples by Daniel Shawul, CCC, November 21, 2013 » Perft
- ↑ Surreal number from Wikipedia
- ↑ John H. Conway (1976). On Numbers and Games. Academic Press
- ↑ Knuth–Morris–Pratt algorithm from Wikipedia
- ↑ TeX from Wikipedia
- ↑ Literate programming from Wikipedia
