25,161
edits
Changes
Created page with "'''Home * People * Donald Knuth''' FILE:KnuthAtOpenContentAlliance.jpg|border|right|thumb| Donald Knuth <ref>Donald Knuth at a reception for the [https://..."
'''[[Main Page|Home]] * [[People]] * Donald Knuth'''
[[FILE:KnuthAtOpenContentAlliance.jpg|border|right|thumb|
Donald Knuth <ref>Donald Knuth at a reception for the [https://en.wikipedia.org/wiki/Open_Content_Alliance Open Content Alliance], hosted by the [https://en.wikipedia.org/wiki/Internet_Archive Internet Archive]. Taken October 25, 2005 by [https://en.wikipedia.org/wiki/Jacob_Appelbaum Jacob Appelbaum] in [https://en.wikipedia.org/wiki/San_Francisco San Francisco], [https://en.wikipedia.org/wiki/Donald_Knuth Donald Knuth from Wikipedia]</ref> ]]
'''Donald Ervin Knuth''',<br/>
a renowned computer scientist, mathematician, writer, scholar, and [https://en.wikipedia.org/wiki/Professor_Emeritus Professor Emeritus] at [[Stanford University]], [https://en.wikipedia.org/wiki/California California], [https://en.wikipedia.org/wiki/United_States United States] <ref>[http://scpd.stanford.edu/knuth/index.jsp Computer Musings by Professor Donald E. Knuth] | [[Stanford University|Stanford University Online]]</ref>. He is the author of the multi-volume work [https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming The Art of Computer Programming], and been called the "father" of the analysis of [[Algorithms|algorithms]] - in [[Timeline#1975|1975]] he analyzed [[Alpha-Beta]] along with Ronald W. Moore, first formulating its [[Node Types]] <ref>[[Donald Knuth]], Ronald W. Moore ('''1975'''). ''[http://www.scribd.com/doc/28194932/An-Analysis-of-Alpha-Beta-Pruning An analysis of alpha-beta pruning].'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6, No. 4, pp 293–326. Reprinted in [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/~uno/aa.html Selected Papers on Analysis of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 102, ISBN 1-57586-212-3</ref>. Beside his fundamental contributions to several branches of computer science and mathematics, Knuth is the creator of the [https://en.wikipedia.org/wiki/TeX TeX] computer typesetting system.
|-
!
| ^
|}
=Quotes=
==McCarthy==
{{Quote McCarthy on Alpha-Beta}}
==Knuth==
Selected quotes by Donald Knuth <ref>[https://en.wikiquote.org/wiki/Donald_Knuth Donald Knuth - Wikiquote]</ref>
* ''A mathematical formula should never be "owned" by anybody! Mathematics belong to God.'' <ref>[[Donald Knuth]] ('''1999'''). ''[http://www-cs-faculty.stanford.edu/~uno/dt.html Digital Typography]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 78</ref>
* ''Beware of bugs in the above code; I have only proved it correct, not tried it.'' <ref>[http://www-cs-faculty.stanford.edu/~uno/faq.html Knuth: Frequently Asked Questions - What's the exact citation of your oft-cited comment about bugs?]</ref>
* ''We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil''. <ref>[[Donald Knuth]] ('''1974'''). ''Structured Programming with go to Statements''. [[ACM#Surveys|ACM Computing Surveys]], Vol. 6, No. 4, [http://cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammingGoTo.pdf pdf]</ref>
=Alpha-Beta=
[[Alpha-Beta]] F2 and [[Iterative Search|Iterative Solution]] <ref>[[Donald Knuth]], [http://www.informatik.uni-trier.de/~ley/pers/hd/m/Moore:Ronald_W= Ronald W. Moore] ('''1975'''). ''An Analysis of Alpha-Beta Pruning''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6, No. 4, pp 293–326. Reprinted in [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/~uno/aa.html Selected Papers on Analysis of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 102, ISBN 1-57586-212-3, [http://www-public.it-sudparis.eu/~gibson/Teaching/CSC4504/ReadingMaterial/KnuthMoore75.pdf pdf]</ref>
* [http://chessprogramming.wikispaces.com/space/showimage/knuth-alpha-beta.JPG Knuth and Moore‘s famous Function F2, aka AlphaBeta]
* [http://chessprogramming.wikispaces.com/space/showimage/knuth-iterative.JPG Knuth already introduced an iterative solution]
=See also=
* [[Backtracking]]
* [[History|History of Computer Chess]]
* [[Alpha-Beta#HistoryAlphaBeta|History of Alpha-Beta]]
=Selected Publications=
<ref>[http://www-cs-faculty.stanford.edu/%7Eknuth/preprints.html Preprints of Recent Papers] including [https://en.wikipedia.org/wiki/Dancing_Links dancing links]</ref><ref>[http://www.informatik.uni-trier.de/~ley/pers/hd/k/Knuth:Donald_E= dblp: Donald E. Knuth]</ref>
==1960 ...==
* [[Donald Knuth]] ('''1960'''). ''An Imaginary Number System''. [[ACM#Communications|Communications of the ACM]], Vol. 3, No. 4
* [[Donald Knuth]] ('''1962'''). ''The calculation of Easter''. [[ACM#Communications|Communications of the ACM]], Vol. 5, No. 4
* [[Donald Knuth]] ('''1964'''). ''backus normal form vs. Backus Naur form''. [[ACM#Communications|Communications of the ACM]], Vol. 7, No. 12 <ref>[https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form Backus–Naur Form from Wikipedia]</ref>
* [[Donald Knuth]] ('''1968 ...'''). ''[http://www-cs-faculty.stanford.edu/~knuth/taocp.html The Art of Computer Programming (TAOCP)]'' <ref>[https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming The Art of Computer Programming from Wikipedia]</ref>
: 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#Surveys|ACM Computing Surveys]], Vol. 2, No. 4
* [[Donald Knuth]] ('''1974'''). ''Structured Programming with go to Statements''. [[ACM#Surveys|ACM Computing Surveys]], Vol. 6, No. 4, [http://cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammingGoTo.pdf pdf] » [[C#Goto|goto]]
* [http://www.informatik.uni-trier.de/~ley/pers/hd/a/Amble:Ole.html Ole Amble], [[Donald Knuth]] ('''1974'''). ''Ordered Hash Tables''. [https://en.wikipedia.org/wiki/The_Computer_Journal The Computer Journal], Vol. 17
* [[Donald Knuth]] ('''1974'''). ''Estimating efficiency of backtrack programs''. STAN-CS-74-442, CS-Department, [[Stanford University]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47740&start=36 Re: Perft(15) estimate after averaging 800 MC samples] by [[Daniel Shawul]], [[CCC]], November 21, 2013 » [[Perft]]</ref>
* [[Donald Knuth]] ('''1974'''). ''[http://www-cs-faculty.stanford.edu/~uno/sn.html Surreal Numbers - How two ex-students turned on to pure mathematics and found total happiness]''. [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley] <ref>[https://en.wikipedia.org/wiki/Surreal_number Surreal number from Wikipedia]</ref> <ref>[[John H. Conway]] ('''1976'''). ''[https://en.wikipedia.org/wiki/On_Numbers_and_Games On Numbers and Games]''. [https://en.wikipedia.org/wiki/Academic_Press Academic Press]</ref>
* [[Donald Knuth]] ('''1974'''). ''Computer Programming as an Art''. [[ACM#Communications|Communications of the ACM]], Vol. 17, No. 12
* [[Donald Knuth]] ('''1974'''). ''Computer Programming as an Art''. [https://en.wikipedia.org/wiki/Turing_Award Turing Award] Lecture, [http://rkka21.ru/docs/turing-award/dk1974e.pdf pdf]
* [[Donald Knuth]] ('''1975'''). ''[http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0373371-6/home.html Estimating the Efficiency of Backtrack Programs]''. [http://www.ams.org/publications/journals/journalsframework/mcom Mathemathics of Computation], Vol. 29 » [[Backtracking]]
* [[Donald Knuth]], [http://www.informatik.uni-trier.de/~ley/pers/hd/m/Moore:Ronald_W= Ronald W. Moore] ('''1975'''). ''[http://www.scribd.com/doc/28194932/An-Analysis-of-Alpha-Beta-Pruning An analysis of alpha-beta pruning].'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6, No. 4, pp 293–326. Reprinted in [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/~uno/aa.html Selected Papers on Analysis of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 102, ISBN 1-57586-212-3
* [[Donald Knuth]], [[Mathematician#JHMorris|James H. Morris, Jr.]], [[Mathematician#VPratt|Vaughan R. Pratt]] ('''1977'''). ''[http://epubs.siam.org/doi/abs/10.1137/0206024 Fast Pattern Matching in Strings]''. [https://en.wikipedia.org/wiki/SIAM_Journal_on_Computing SIAM Journal on Computing], Vol. 6, No. 2 <ref>[https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm Knuth–Morris–Pratt algorithm from Wikipedia]</ref>
==1980 ...==
* <span id="AMMCS"></span>[[Mathematician#Ershov|Andrei P. Ershov]], [[Donald Knuth]] (Eds.) ('''1981'''). ''Algorithms in Modern Mathematics and Computer Science''. Proceedings, [https://en.wikipedia.org/wiki/Urgench Urgench], Uzbek SSR, September 16-22, 1979. [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science Lecture Notes in Computer Science], Vol. 122, Springer » [[Donald Knuth#ErshovArchive|Ershov Archive]]
* [[Donald Knuth]] ('''1985'''). ''An Analysis of Optimum Caching''. [https://en.wikipedia.org/wiki/Elsevier#Resignation_of_editorial_boards Journal of Algorithms], Vol. 6
* [[Donald Knuth]] ('''1986'''). ''TeX: The Program''. [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley] <ref>[https://en.wikipedia.org/wiki/TeX TeX from Wikipedia]</ref>
* [[Donald Knuth]] ('''1986, 1996'''). ''The TeXbook''. [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley], [http://web.mit.edu/jgross/www/LaTeX/texbook.pdf pdf]
* [[Mathematician#RGraham|Ronald L. Graham]], [[Donald Knuth]], [[Mathematician#OPatashnik|Oren Patashnik]] ('''1989, 1994'''). ''[https://en.wikipedia.org/wiki/Concrete_Mathematics Concrete Mathematics]''. [http://www-cs-faculty.stanford.edu/~uno/gkp.html Second Edition], [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley]
==1990 ...==
* [https://en.wikipedia.org/wiki/Lee_Sallows Lee Sallows], [[Martin Gardner]], [[Richard K. Guy]], [[Donald Knuth]] ('''1991'''). ''Serial Isogons of 90 Degrees''. [https://en.wikipedia.org/wiki/Mathematics_Magazine Mathematics Magazine], Vol. 64, No. 5
* [[Donald Knuth]] ('''1991'''). ''Textbook examples of recursion''. [https://arxiv.org/abs/cs/9301113 arXiv:cs/9301113] » [[Recursion]]
* [[Donald Knuth]] ('''1992'''). ''[http://www-cs-faculty.stanford.edu/~uno/lp.html Literate Programming]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 27 <ref>[https://en.wikipedia.org/wiki/Literate_programming Literate programming from Wikipedia]</ref>
* [[Donald Knuth]] ('''1996'''). ''[http://www-cs-faculty.stanford.edu/~uno/cs.html Selected Papers on Computer Science]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 59
* [[Donald Knuth]] ('''1999'''). ''[http://www-cs-faculty.stanford.edu/~uno/dt.html Digital Typography]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 78
==2000 ...==
* [[Donald Knuth]] ('''2000'''). ''[http://arxiv.org/abs/cs/0011047 Dancing Links arXiv:cs/0011047v1]''.
* [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/~uno/aa.html Selected Papers on Analysis of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 102
* [[Donald Knuth]] ('''2001'''). ''Arithmetik''. Springer, ISBN 978-3-540-66745-2
* [[Donald Knuth]] ('''2003'''). ''[http://www-cs-faculty.stanford.edu/~uno/dm.html Selected Papers on Discrete Mathematics]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 106
* [[Donald Knuth]] ('''2003'''). ''[http://www-cs-faculty.stanford.edu/~uno/cl.html Selected Papers on Computer Languages]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 139
* [[Donald Knuth]] ('''2003'''). ''[http://www-cs-staff.stanford.edu/~uno/things.html Things a Computer Scientist Rarely Talks About]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 202
==2010 ...==
* [[Donald Knuth]] ('''2010'''). ''[http://www-cs-faculty.stanford.edu/~uno/da.html Selected Papers on Design of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 191, [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press], ISBN 978-1-57586-582-9
* [[Donald Knuth]] ('''2011'''). ''[http://www-cs-faculty.stanford.edu/~uno/fg.html Selected Papers on Fun and Games]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 192, [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press], ISBN 978-1-57586-584-3
* [[Donald Knuth]] ('''2012'''). ''[http://www-cs-faculty.stanford.edu/~uno/cp.html Companion to the Papers of Donald Knuth]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 202, [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press], ISBN 978-1-57586-634-5
* [[Donald Knuth]] ('''2012'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-642-31612-8_2 Satisfiability and The Art of Computer Programming]''. SAT 2012, [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science Lecture Notes in Computer Science], Vol. 7317, Springer
=External Links=
==Donald Knuth==
* [http://www-cs-faculty.stanford.edu/%7Eknuth/ Don Knuth’s home page]
* [https://en.wikipedia.org/wiki/Donald_Knuth Donald Knuth from Wikipedia]
* [https://en.wikiquote.org/wiki/Donald_Knuth Donald Knuth - Wikiquote]
* [https://genealogy.math.ndsu.nodak.edu/id.php?id=10416 The Mathematics Genealogy Project - Donald Knuth]
* [http://www-history.mcs.st-andrews.ac.uk/Biographies/Knuth.html Knuth biography - MacTutor]
* [http://amturing.acm.org/award_winners/knuth_1013846.cfm Donald E. Knuth - A.M. Turing Award Winner]
* [http://www.computerhistory.org/fellowawards/hall/bios/Donald,Knuth/ Fellow Awards | Donald Knuth] from [[The Computer History Museum]]
* [http://www.adeptis.ru/vinci/m_part3_2.html Donald Knuth - АдептИС: Под знаком Leonardo da Vinci] (Russian)
* [http://scpd.stanford.edu/knuth/index.jsp Computer Musings by Professor Donald E. Knuth] | [[Stanford University|Stanford University Online]]
* [http://www.codethinked.com/the-programmer-dress-code The Programmer Dress Code | CodeThinked] by [http://www.codethinked.com/ Justin Etheredge], December 6, 2007
* [http://www.catonmat.net/blog/donald-knuths-first-computer/ Donald Knuth's First Computer - good coders code, great reuse] by [http://www.catonmat.net/about/ Peteris Krumins], February 26, 2010
* [http://bertrandmeyer.com/2011/05/22/in-praise-of-knuth-and-liskov/ In praise of Knuth and Liskov] from [https://en.wikipedia.org/wiki/Bertrand_Meyer Bertrand Meyer's] [http://bertrandmeyer.com/ technology+ blog], May 22, 2011 » [[Barbara Liskov]]
* [http://www.i-programmer.info/news/82-heritage/3597-donald-knuth-in-alan-turing-year.html Donald Knuth in Alan Turing Year] from [http://www.i-programmer.info/ I Programmer - programming, reviews and projects], January 10, 2012 » [[Alan Turing]]
==Ershov Archive==
* <span id="ErshovArchive"></span>[http://ershov.iis.nsk.su/archive/eaindex.asp?lang=2&gid=515 Algorithms in Modern Mathematics and Computer Science - 1979] [[Mathematician#Ershov|Andrei Ershov]] Archive » [[Donald Knuth#AMMCS|Algorithms in Modern Mathematics and Computer Science - Proceedings]]
: [http://ershov.iis.nsk.su/archive/eaimage.asp?lang=2&did=1441&fileid=85540 Dancing D. Knuth]
: [http://ershov.iis.nsk.su/archive/eaimage.asp?lang=2&did=1444&fileid=85543 Khiva, summer hall; dancers, D.Knuth]
: [http://ershov.iis.nsk.su/archive/eaimage.asp?lang=2&did=2659&fileid=85555 Andrey Ershov, Donald E. Knuth]
: [http://ershov.iis.nsk.su/archive/eaimage.asp?lang=2&did=2674&fileid=85562 Khiva, summer hall; A. van Wijngaarden, Zemaneks, D.Knuth. F.Strassen, B.Trakhtenbrot]
==Interviews==
* [http://tex.loria.fr/historique/interviews/knuth-clb1993.html Donald Knuth - Computer Literacy Bookshops Interview], December 07, 1993
* [http://www.ntg.nl/maps/16/14.pdf An interview with Donald Knuth] (pdf) by [http://www.drdobbs.com/author/Jack-Woehr Jack Woehr], [https://en.wikipedia.org/wiki/Dr._Dobb%27s_Journal Dr. Dobb's Journal], April 1996
* [http://www.freesoftwaremagazine.com/articles/interview_knuth Interview with Donald E. Knuth] by [http://www.freesoftwaremagazine.com/contacts/g.pignalberi Gianluca Pignalberi], [https://en.wikipedia.org/wiki/Free_Software_Magazine Free Software Magazine], September 04, 2005
* [http://www.informit.com/articles/article.aspx?p=1193856 Interview with Donald Knuth] by [[Donald Knuth]] and [http://www.drdobbs.com/author/Andrew-Binstock Andrew Binstock], [https://en.wikipedia.org/wiki/InformIT], April 25, 2008 » [[Itanium]]
==Topics==
* [https://en.wikipedia.org/wiki/Dancing_Links Dancing Links from Wikipedia]
* [https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X Knuth's Algorithm X from Wikipedia]
* [https://en.wikipedia.org/wiki/Knuth%E2%80%93Bendix_completion_algorithm Knuth–Bendix completion algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm Knuth–Morris–Pratt algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Knuth_reward_check Knuth reward check from Wikipedia]
* [http://www-cs-faculty.stanford.edu/~uno/mmix.html MMIX 2009 a RISC computer for the third millennium]
: [http://www-cs-faculty.stanford.edu/~uno/mmix-news.html MMIX News]
: [https://en.wikipedia.org/wiki/MMIX MMIX from Wikipedia]
* [https://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted%E2%80%93Knuth_correspondence Robinson–Schensted–Knuth correspondence from Wikipedia]
* [https://en.wikipedia.org/wiki/TeX TeX from Wikipedia]
: [https://en.wikipedia.org/wiki/Metafont Metafont from Wikipedia]
* [http://www-cs-faculty.stanford.edu/~uno/taocp.html The Art of Computer Programming]
* [https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming The Art of Computer Programming from Wikipedia]
==Videos==
* [http://www.informatik.tuwien.ac.at/english/vienna-goedel-lectures/2013 Vienna Gödel Lecture 2013]: Donald E. Knuth, [[Vienna University of Technology]], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=nAB4EtnQqaM|alignment=left|valignment=top}}
=References=
<references />
'''[[People|Up one level]]'''
[[FILE:KnuthAtOpenContentAlliance.jpg|border|right|thumb|
Donald Knuth <ref>Donald Knuth at a reception for the [https://en.wikipedia.org/wiki/Open_Content_Alliance Open Content Alliance], hosted by the [https://en.wikipedia.org/wiki/Internet_Archive Internet Archive]. Taken October 25, 2005 by [https://en.wikipedia.org/wiki/Jacob_Appelbaum Jacob Appelbaum] in [https://en.wikipedia.org/wiki/San_Francisco San Francisco], [https://en.wikipedia.org/wiki/Donald_Knuth Donald Knuth from Wikipedia]</ref> ]]
'''Donald Ervin Knuth''',<br/>
a renowned computer scientist, mathematician, writer, scholar, and [https://en.wikipedia.org/wiki/Professor_Emeritus Professor Emeritus] at [[Stanford University]], [https://en.wikipedia.org/wiki/California California], [https://en.wikipedia.org/wiki/United_States United States] <ref>[http://scpd.stanford.edu/knuth/index.jsp Computer Musings by Professor Donald E. Knuth] | [[Stanford University|Stanford University Online]]</ref>. He is the author of the multi-volume work [https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming The Art of Computer Programming], and been called the "father" of the analysis of [[Algorithms|algorithms]] - in [[Timeline#1975|1975]] he analyzed [[Alpha-Beta]] along with Ronald W. Moore, first formulating its [[Node Types]] <ref>[[Donald Knuth]], Ronald W. Moore ('''1975'''). ''[http://www.scribd.com/doc/28194932/An-Analysis-of-Alpha-Beta-Pruning An analysis of alpha-beta pruning].'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6, No. 4, pp 293–326. Reprinted in [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/~uno/aa.html Selected Papers on Analysis of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 102, ISBN 1-57586-212-3</ref>. Beside his fundamental contributions to several branches of computer science and mathematics, Knuth is the creator of the [https://en.wikipedia.org/wiki/TeX TeX] computer typesetting system.
|-
!
| ^
|}
=Quotes=
==McCarthy==
{{Quote McCarthy on Alpha-Beta}}
==Knuth==
Selected quotes by Donald Knuth <ref>[https://en.wikiquote.org/wiki/Donald_Knuth Donald Knuth - Wikiquote]</ref>
* ''A mathematical formula should never be "owned" by anybody! Mathematics belong to God.'' <ref>[[Donald Knuth]] ('''1999'''). ''[http://www-cs-faculty.stanford.edu/~uno/dt.html Digital Typography]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 78</ref>
* ''Beware of bugs in the above code; I have only proved it correct, not tried it.'' <ref>[http://www-cs-faculty.stanford.edu/~uno/faq.html Knuth: Frequently Asked Questions - What's the exact citation of your oft-cited comment about bugs?]</ref>
* ''We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil''. <ref>[[Donald Knuth]] ('''1974'''). ''Structured Programming with go to Statements''. [[ACM#Surveys|ACM Computing Surveys]], Vol. 6, No. 4, [http://cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammingGoTo.pdf pdf]</ref>
=Alpha-Beta=
[[Alpha-Beta]] F2 and [[Iterative Search|Iterative Solution]] <ref>[[Donald Knuth]], [http://www.informatik.uni-trier.de/~ley/pers/hd/m/Moore:Ronald_W= Ronald W. Moore] ('''1975'''). ''An Analysis of Alpha-Beta Pruning''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6, No. 4, pp 293–326. Reprinted in [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/~uno/aa.html Selected Papers on Analysis of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 102, ISBN 1-57586-212-3, [http://www-public.it-sudparis.eu/~gibson/Teaching/CSC4504/ReadingMaterial/KnuthMoore75.pdf pdf]</ref>
* [http://chessprogramming.wikispaces.com/space/showimage/knuth-alpha-beta.JPG Knuth and Moore‘s famous Function F2, aka AlphaBeta]
* [http://chessprogramming.wikispaces.com/space/showimage/knuth-iterative.JPG Knuth already introduced an iterative solution]
=See also=
* [[Backtracking]]
* [[History|History of Computer Chess]]
* [[Alpha-Beta#HistoryAlphaBeta|History of Alpha-Beta]]
=Selected Publications=
<ref>[http://www-cs-faculty.stanford.edu/%7Eknuth/preprints.html Preprints of Recent Papers] including [https://en.wikipedia.org/wiki/Dancing_Links dancing links]</ref><ref>[http://www.informatik.uni-trier.de/~ley/pers/hd/k/Knuth:Donald_E= dblp: Donald E. Knuth]</ref>
==1960 ...==
* [[Donald Knuth]] ('''1960'''). ''An Imaginary Number System''. [[ACM#Communications|Communications of the ACM]], Vol. 3, No. 4
* [[Donald Knuth]] ('''1962'''). ''The calculation of Easter''. [[ACM#Communications|Communications of the ACM]], Vol. 5, No. 4
* [[Donald Knuth]] ('''1964'''). ''backus normal form vs. Backus Naur form''. [[ACM#Communications|Communications of the ACM]], Vol. 7, No. 12 <ref>[https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form Backus–Naur Form from Wikipedia]</ref>
* [[Donald Knuth]] ('''1968 ...'''). ''[http://www-cs-faculty.stanford.edu/~knuth/taocp.html The Art of Computer Programming (TAOCP)]'' <ref>[https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming The Art of Computer Programming from Wikipedia]</ref>
: 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#Surveys|ACM Computing Surveys]], Vol. 2, No. 4
* [[Donald Knuth]] ('''1974'''). ''Structured Programming with go to Statements''. [[ACM#Surveys|ACM Computing Surveys]], Vol. 6, No. 4, [http://cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammingGoTo.pdf pdf] » [[C#Goto|goto]]
* [http://www.informatik.uni-trier.de/~ley/pers/hd/a/Amble:Ole.html Ole Amble], [[Donald Knuth]] ('''1974'''). ''Ordered Hash Tables''. [https://en.wikipedia.org/wiki/The_Computer_Journal The Computer Journal], Vol. 17
* [[Donald Knuth]] ('''1974'''). ''Estimating efficiency of backtrack programs''. STAN-CS-74-442, CS-Department, [[Stanford University]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47740&start=36 Re: Perft(15) estimate after averaging 800 MC samples] by [[Daniel Shawul]], [[CCC]], November 21, 2013 » [[Perft]]</ref>
* [[Donald Knuth]] ('''1974'''). ''[http://www-cs-faculty.stanford.edu/~uno/sn.html Surreal Numbers - How two ex-students turned on to pure mathematics and found total happiness]''. [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley] <ref>[https://en.wikipedia.org/wiki/Surreal_number Surreal number from Wikipedia]</ref> <ref>[[John H. Conway]] ('''1976'''). ''[https://en.wikipedia.org/wiki/On_Numbers_and_Games On Numbers and Games]''. [https://en.wikipedia.org/wiki/Academic_Press Academic Press]</ref>
* [[Donald Knuth]] ('''1974'''). ''Computer Programming as an Art''. [[ACM#Communications|Communications of the ACM]], Vol. 17, No. 12
* [[Donald Knuth]] ('''1974'''). ''Computer Programming as an Art''. [https://en.wikipedia.org/wiki/Turing_Award Turing Award] Lecture, [http://rkka21.ru/docs/turing-award/dk1974e.pdf pdf]
* [[Donald Knuth]] ('''1975'''). ''[http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0373371-6/home.html Estimating the Efficiency of Backtrack Programs]''. [http://www.ams.org/publications/journals/journalsframework/mcom Mathemathics of Computation], Vol. 29 » [[Backtracking]]
* [[Donald Knuth]], [http://www.informatik.uni-trier.de/~ley/pers/hd/m/Moore:Ronald_W= Ronald W. Moore] ('''1975'''). ''[http://www.scribd.com/doc/28194932/An-Analysis-of-Alpha-Beta-Pruning An analysis of alpha-beta pruning].'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6, No. 4, pp 293–326. Reprinted in [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/~uno/aa.html Selected Papers on Analysis of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 102, ISBN 1-57586-212-3
* [[Donald Knuth]], [[Mathematician#JHMorris|James H. Morris, Jr.]], [[Mathematician#VPratt|Vaughan R. Pratt]] ('''1977'''). ''[http://epubs.siam.org/doi/abs/10.1137/0206024 Fast Pattern Matching in Strings]''. [https://en.wikipedia.org/wiki/SIAM_Journal_on_Computing SIAM Journal on Computing], Vol. 6, No. 2 <ref>[https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm Knuth–Morris–Pratt algorithm from Wikipedia]</ref>
==1980 ...==
* <span id="AMMCS"></span>[[Mathematician#Ershov|Andrei P. Ershov]], [[Donald Knuth]] (Eds.) ('''1981'''). ''Algorithms in Modern Mathematics and Computer Science''. Proceedings, [https://en.wikipedia.org/wiki/Urgench Urgench], Uzbek SSR, September 16-22, 1979. [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science Lecture Notes in Computer Science], Vol. 122, Springer » [[Donald Knuth#ErshovArchive|Ershov Archive]]
* [[Donald Knuth]] ('''1985'''). ''An Analysis of Optimum Caching''. [https://en.wikipedia.org/wiki/Elsevier#Resignation_of_editorial_boards Journal of Algorithms], Vol. 6
* [[Donald Knuth]] ('''1986'''). ''TeX: The Program''. [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley] <ref>[https://en.wikipedia.org/wiki/TeX TeX from Wikipedia]</ref>
* [[Donald Knuth]] ('''1986, 1996'''). ''The TeXbook''. [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley], [http://web.mit.edu/jgross/www/LaTeX/texbook.pdf pdf]
* [[Mathematician#RGraham|Ronald L. Graham]], [[Donald Knuth]], [[Mathematician#OPatashnik|Oren Patashnik]] ('''1989, 1994'''). ''[https://en.wikipedia.org/wiki/Concrete_Mathematics Concrete Mathematics]''. [http://www-cs-faculty.stanford.edu/~uno/gkp.html Second Edition], [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley]
==1990 ...==
* [https://en.wikipedia.org/wiki/Lee_Sallows Lee Sallows], [[Martin Gardner]], [[Richard K. Guy]], [[Donald Knuth]] ('''1991'''). ''Serial Isogons of 90 Degrees''. [https://en.wikipedia.org/wiki/Mathematics_Magazine Mathematics Magazine], Vol. 64, No. 5
* [[Donald Knuth]] ('''1991'''). ''Textbook examples of recursion''. [https://arxiv.org/abs/cs/9301113 arXiv:cs/9301113] » [[Recursion]]
* [[Donald Knuth]] ('''1992'''). ''[http://www-cs-faculty.stanford.edu/~uno/lp.html Literate Programming]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 27 <ref>[https://en.wikipedia.org/wiki/Literate_programming Literate programming from Wikipedia]</ref>
* [[Donald Knuth]] ('''1996'''). ''[http://www-cs-faculty.stanford.edu/~uno/cs.html Selected Papers on Computer Science]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 59
* [[Donald Knuth]] ('''1999'''). ''[http://www-cs-faculty.stanford.edu/~uno/dt.html Digital Typography]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 78
==2000 ...==
* [[Donald Knuth]] ('''2000'''). ''[http://arxiv.org/abs/cs/0011047 Dancing Links arXiv:cs/0011047v1]''.
* [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/~uno/aa.html Selected Papers on Analysis of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 102
* [[Donald Knuth]] ('''2001'''). ''Arithmetik''. Springer, ISBN 978-3-540-66745-2
* [[Donald Knuth]] ('''2003'''). ''[http://www-cs-faculty.stanford.edu/~uno/dm.html Selected Papers on Discrete Mathematics]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 106
* [[Donald Knuth]] ('''2003'''). ''[http://www-cs-faculty.stanford.edu/~uno/cl.html Selected Papers on Computer Languages]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 139
* [[Donald Knuth]] ('''2003'''). ''[http://www-cs-staff.stanford.edu/~uno/things.html Things a Computer Scientist Rarely Talks About]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 202
==2010 ...==
* [[Donald Knuth]] ('''2010'''). ''[http://www-cs-faculty.stanford.edu/~uno/da.html Selected Papers on Design of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 191, [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press], ISBN 978-1-57586-582-9
* [[Donald Knuth]] ('''2011'''). ''[http://www-cs-faculty.stanford.edu/~uno/fg.html Selected Papers on Fun and Games]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 192, [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press], ISBN 978-1-57586-584-3
* [[Donald Knuth]] ('''2012'''). ''[http://www-cs-faculty.stanford.edu/~uno/cp.html Companion to the Papers of Donald Knuth]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 202, [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press], ISBN 978-1-57586-634-5
* [[Donald Knuth]] ('''2012'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-642-31612-8_2 Satisfiability and The Art of Computer Programming]''. SAT 2012, [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science Lecture Notes in Computer Science], Vol. 7317, Springer
=External Links=
==Donald Knuth==
* [http://www-cs-faculty.stanford.edu/%7Eknuth/ Don Knuth’s home page]
* [https://en.wikipedia.org/wiki/Donald_Knuth Donald Knuth from Wikipedia]
* [https://en.wikiquote.org/wiki/Donald_Knuth Donald Knuth - Wikiquote]
* [https://genealogy.math.ndsu.nodak.edu/id.php?id=10416 The Mathematics Genealogy Project - Donald Knuth]
* [http://www-history.mcs.st-andrews.ac.uk/Biographies/Knuth.html Knuth biography - MacTutor]
* [http://amturing.acm.org/award_winners/knuth_1013846.cfm Donald E. Knuth - A.M. Turing Award Winner]
* [http://www.computerhistory.org/fellowawards/hall/bios/Donald,Knuth/ Fellow Awards | Donald Knuth] from [[The Computer History Museum]]
* [http://www.adeptis.ru/vinci/m_part3_2.html Donald Knuth - АдептИС: Под знаком Leonardo da Vinci] (Russian)
* [http://scpd.stanford.edu/knuth/index.jsp Computer Musings by Professor Donald E. Knuth] | [[Stanford University|Stanford University Online]]
* [http://www.codethinked.com/the-programmer-dress-code The Programmer Dress Code | CodeThinked] by [http://www.codethinked.com/ Justin Etheredge], December 6, 2007
* [http://www.catonmat.net/blog/donald-knuths-first-computer/ Donald Knuth's First Computer - good coders code, great reuse] by [http://www.catonmat.net/about/ Peteris Krumins], February 26, 2010
* [http://bertrandmeyer.com/2011/05/22/in-praise-of-knuth-and-liskov/ In praise of Knuth and Liskov] from [https://en.wikipedia.org/wiki/Bertrand_Meyer Bertrand Meyer's] [http://bertrandmeyer.com/ technology+ blog], May 22, 2011 » [[Barbara Liskov]]
* [http://www.i-programmer.info/news/82-heritage/3597-donald-knuth-in-alan-turing-year.html Donald Knuth in Alan Turing Year] from [http://www.i-programmer.info/ I Programmer - programming, reviews and projects], January 10, 2012 » [[Alan Turing]]
==Ershov Archive==
* <span id="ErshovArchive"></span>[http://ershov.iis.nsk.su/archive/eaindex.asp?lang=2&gid=515 Algorithms in Modern Mathematics and Computer Science - 1979] [[Mathematician#Ershov|Andrei Ershov]] Archive » [[Donald Knuth#AMMCS|Algorithms in Modern Mathematics and Computer Science - Proceedings]]
: [http://ershov.iis.nsk.su/archive/eaimage.asp?lang=2&did=1441&fileid=85540 Dancing D. Knuth]
: [http://ershov.iis.nsk.su/archive/eaimage.asp?lang=2&did=1444&fileid=85543 Khiva, summer hall; dancers, D.Knuth]
: [http://ershov.iis.nsk.su/archive/eaimage.asp?lang=2&did=2659&fileid=85555 Andrey Ershov, Donald E. Knuth]
: [http://ershov.iis.nsk.su/archive/eaimage.asp?lang=2&did=2674&fileid=85562 Khiva, summer hall; A. van Wijngaarden, Zemaneks, D.Knuth. F.Strassen, B.Trakhtenbrot]
==Interviews==
* [http://tex.loria.fr/historique/interviews/knuth-clb1993.html Donald Knuth - Computer Literacy Bookshops Interview], December 07, 1993
* [http://www.ntg.nl/maps/16/14.pdf An interview with Donald Knuth] (pdf) by [http://www.drdobbs.com/author/Jack-Woehr Jack Woehr], [https://en.wikipedia.org/wiki/Dr._Dobb%27s_Journal Dr. Dobb's Journal], April 1996
* [http://www.freesoftwaremagazine.com/articles/interview_knuth Interview with Donald E. Knuth] by [http://www.freesoftwaremagazine.com/contacts/g.pignalberi Gianluca Pignalberi], [https://en.wikipedia.org/wiki/Free_Software_Magazine Free Software Magazine], September 04, 2005
* [http://www.informit.com/articles/article.aspx?p=1193856 Interview with Donald Knuth] by [[Donald Knuth]] and [http://www.drdobbs.com/author/Andrew-Binstock Andrew Binstock], [https://en.wikipedia.org/wiki/InformIT], April 25, 2008 » [[Itanium]]
==Topics==
* [https://en.wikipedia.org/wiki/Dancing_Links Dancing Links from Wikipedia]
* [https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X Knuth's Algorithm X from Wikipedia]
* [https://en.wikipedia.org/wiki/Knuth%E2%80%93Bendix_completion_algorithm Knuth–Bendix completion algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm Knuth–Morris–Pratt algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Knuth_reward_check Knuth reward check from Wikipedia]
* [http://www-cs-faculty.stanford.edu/~uno/mmix.html MMIX 2009 a RISC computer for the third millennium]
: [http://www-cs-faculty.stanford.edu/~uno/mmix-news.html MMIX News]
: [https://en.wikipedia.org/wiki/MMIX MMIX from Wikipedia]
* [https://en.wikipedia.org/wiki/Robinson%E2%80%93Schensted%E2%80%93Knuth_correspondence Robinson–Schensted–Knuth correspondence from Wikipedia]
* [https://en.wikipedia.org/wiki/TeX TeX from Wikipedia]
: [https://en.wikipedia.org/wiki/Metafont Metafont from Wikipedia]
* [http://www-cs-faculty.stanford.edu/~uno/taocp.html The Art of Computer Programming]
* [https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming The Art of Computer Programming from Wikipedia]
==Videos==
* [http://www.informatik.tuwien.ac.at/english/vienna-goedel-lectures/2013 Vienna Gödel Lecture 2013]: Donald E. Knuth, [[Vienna University of Technology]], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=nAB4EtnQqaM|alignment=left|valignment=top}}
=References=
<references />
'''[[People|Up one level]]'''
