ProofWiki:Mathematicians/Donald Ervin Knuth
From ProofWiki
Pronounced K-Nooth.
Hugely influential American computer scientist famous for his multi-volume The Art of Computer Programming, still famously a work in progress.
The "father of analysis of algorithms".
Pioneered research and design of the representation of mathematics via computer.
Contents |
Nationality
American
History
- Born: January 10, 1938
Theorems and Definitions
- Knuth-Morris-Pratt Algorithm (with Vaughan Pratt, independently of James H. Morris)
- Knuth-Bendix Completion Algorithm
Books, Papers and Other Creations
The Art of Computer Programming
- 1968 +: The Art of Computer Programming:
- 1968: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd edition: 1997) (ISBN 0-201-89683-4)
- 1969: The Art of Computer Programming: Volume 2: Seminumerical Algorithms (3rd edition: 1997) (ISBN 0-201-89684-2)
- 1973: The Art of Computer Programming: Volume 3: Sorting and Searching (2nd edition: 1998) (ISBN 0-201-89685-0)
- The Art of Computer Programming: Volume 4: Combinatorial Algorithms (in preparation)
- The Art of Computer Programming, fascicles:
- 2005: Volume 1, Fascicle 1: MMIX - A RISC Computer for the New Millennium (ISBN 0-201-85392-2)
- 2008: Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions (ISBN 0-321-53496-4)
- 2009: Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams (ISBN 0-321-58050-8)
- 2005: Volume 4, Fascicle 2: Generating All Tuples and Permutations (ISBN 0-201-85393-0)
- 2005: Volume 4, Fascicle 3: Generating All Combinations and Partitions (ISBN 0-201-85394-9)
- 2006: Volume 4, Fascicle 4: Generating All Trees - History of Combinatorial Generation (ISBN 0-321-33570-8)
Computers and Typesetting
- 1986: Computers and Typesetting:
- 1984: Volume A: The TeXbook. Describes the TeX typesetting language. (Softcover: ISBN 0-201-13448-9, hardcover ISBN 0-201-13447-0)
- 1986: Volume B: TeX: The program. A documented listing of the source code of the TeX interpreter. (Hardcover: ISBN 0-201-13437-3)
- 1986: Volume C: The METAFONTbook. Describes the METAFONT font description language. (Hardcover: ISBN 0-201-13445-4, softcover: ISBN 0-201-13444-6)
- 1986: Volume D: Metafont: The program. A documented listing of the source code of the Metafont interpreter. (Hardcover ISBN 0-201-13438-1, paperback ISBN 0-201-60658-5)
- 1986: Volume E: Computer Modern Typefaces. A character-by-character listing (in the Metafont language) of the source code for the Computer Modern typefaces (cmr, cmbx, cmti, etc) used by TeX. (Hardcover: ISBN 0-201-13446-2, softcover: ISBN 0-201-60660-7)
- Hardcover boxed set with the latest editions as of the year 2000: ISBN 0-201-73416-8.
Other Books
- 1974: Surreal Numbers
- 1989: Concrete Mathematics: A Foundation for Computer Science (with Ronald L. Graham and Oren Patashnik) (2nd edition: 1994)
- 1990: 3:16 Bible Texts Illuminated (ISBN 0-89579-252-4)
- 1992: Literate Programming (ISBN 978-0937073803)
- 2001: Things a Computer Scientist Rarely Talks About (ISBN 1-57586-326-X)
Selected Papers series
- 1992: Literate Programming (ISBN 0-937073-80-6)
- 1996: Selected Papers on Computer Science (ISBN 1-881526-91-7)
- 2000: Selected Papers on Analysis of Algorithms (ISBN 1-57586-212-3)
- 2003: Selected Papers on Computer Languages (Cloth binding: ISBN 1-57586-381-2, paperback: ISBN 1-57586-382-0)
- 2003: Selected Papers on Discrete Mathematics (Cloth binding: ISBN 1-57586-249-2, paperback: ISBN 1-57586-248-4)
- 2010: Selected Papers on Design of Algorithms (Cloth binding: ISBN 1-57586-583-1, paperback: ISBN 1-57586-582-3)
- Planned late 2010: Selected Papers on Fun and Games
Papers and Articles
- 1957: Potrzebie System of Weights and Measures
- 1963: Finite semifields and projective planes (PhD thesis)
- 1965: On the translation of languages from left to right
- 1977: Fast pattern matching in strings (in which the Knuth-Morris-Pratt Algorithm is introduced)
- 1991: Efficient representation of perm groups
- 1992: Two Notes on Notation (in which Iverson's Convention is discussed)
- 1993: Johann Faulhaber and sums of powers
Other Creations
- TeX: the definitive tools for typographical rendition of mathematical symbols.
- METAFONT: a software tool for alphabet design.
- The Computer Modern family of typefaces.
- MIX and MMIX, a virtual computer architecture (and its successor) designed to teach the basics of machine-level programming.
Notable Quotes
"Beware of bugs in the above code; I have only proved it correct, not tried it."
Notes
- ↑ It is impossible accurately to assess the impact of TeX on the ability to communicate mathematics via computer. This website would not have been possible without it.
