Donald KnuthErshovArchive
On this page
- Quotes
- McCarthy
- Knuth
- Alpha-Beta
- See also
- Selected Publications
- 1960 …
- 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 …
- 1980 …
- 1990 …
- 2000 …
- 2010 …
- External Links
- Donald Knuth
- Ershov Archive
- 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
- Topics
- Videos
- References
[ 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.
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](Branching_Factor "Branching Factor") of the chess move [tree](Search_Tree "Search Tree"). The ideas that work for chess are inadequate for [go](Go "Go"). [Alpha-beta pruning](Alpha-Beta "Alpha-Beta") characterizes human play, but it wasn't noticed by [early chess programmers](Category:Pioneer "Category:Pioneer") - [Turing](Alan_Turing "Alan Turing"), [Shannon](Claude_Shannon "Claude Shannon"), [Pasta](John_Pasta "John Pasta") and [Ulam](Stanislaw_Ulam "Stanislaw Ulam"), and [Bernstein](Alex_Bernstein "Alex Bernstein"). We humans are not very good at identifying the heuristics we ourselves use. Approximations to alpha-beta used by [Samuel](Arthur_Samuel "Arthur Samuel"), [Newell](Allen_Newell "Allen Newell") and [Simon](Herbert_Simon "Herbert Simon"), McCarthy. Proved equivalent to [minimax](Minimax "Minimax") by [Hart](Timothy_Hart "Timothy Hart") and [Levin](Michael_Levin "Michael Levin"), independently by [Brudno](Alexander_Brudno "Alexander 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