1974 唐纳德-E-克努斯

shiyi18

Donald E. Knuth
BIRTH:
January 10, 1938, in Milwaukee, Wisconsin.

EDUCATION:
Graduated from Milwaukee Lutheran High School (1956); BS in mathematics from the Case Institute of Technology (1960), his undergraduate work was so distinguished that he was awarded a simultaneous MS by special vote of the faculty; Ph.D. in mathematics from the California Institute of Technology (1963).

EXPERIENCE:
Assistant and then Associate Professor, California Institute of Technology (1963-1968); A series of full and named professorships, Stanford University (1968-1992); Professor of the Art of Computer Programming, Emeritus, Stanford University (from 1993).

HONORS AND AWARDS:
Knuth has received over 100 awards and honors. Among these are: First ACM Grace Murray Hopper Award (1971); Fellow, American Academy of Arts and Sciences (1973); Alan M. Turing Award (1974); Member, National Academy of Science (1975); Lester R. Ford Award (1975 and 1993); American Mathematical Society Gibbs Lecture (1978); National Medal of Science (1979, awarded by President Carter); Member, National Academy of Engineering (1981); IEEE Computer Society Computer Pioneer Award (1982); Franklin Medal (1988); Harvey Prize (1995); IEEE John von Neumann Medal (1995); Kyoto Prize (1996); Fellow, Computer History Museum (1998).


DONALD ("DON") ERVIN KNUTH DL Author Profile link
United States – 1974
CITATION
For his major contributions to the analysis of algorithms and the design of programming languages, and in particular for his contributions to the "art of computer programming" through his well-known books in a continuous series by this title.

SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE
RESEARCH
SUBJECTS
VIDEO INTERVIEW
Donald Ervin “Don” Knuth was born January 10, 1938, in Milwaukee, Wisconsin. His father was a teacher in a Lutheran high school and a church organist. Don Knuth attended Lutheran high school and, in later life, also became a church organist.

Education

In the 7th and 8th grades Knuth was very interested in the structure of English grammar. In high school he was interested in physics and was good at mathematics. Heading for college, he wondered whether to major in physics or music, but chose the former because he got a scholarship to the Case Institute of Technology in Cleveland, Ohio. In his sophomore year of college he switched his major from physics to mathematics, partly because he had trouble with science labs.

During his freshman year, Knuth worked in the statistics lab drawing graphs, key punching tabulating cards, and using a card sorter. In December of 1956, he spotted the newly installed IBM 650 computer across the hall. The 650 intrigued him, and he spent much of the summer of 1957 getting to know how it worked. He wrote a variety of interesting programs during his undergraduate years, including one to rate the performance of members of the basketball team he managed.

Knuth recalls his first computer programming, for an IBM 650.       
Knuth was so good at mathematical studies at Case that the faculty awarded him an M.S. in mathematics when he finished his B.S. work.

The Art of Computer Programming

While working on his PhD in mathematics at the California Institute of Technology, Knuth also did private consulting, and wrote compilers for various computers.

Knuth describes the Algol compiler he wrote for Burroughs and his decision not to develop commercial software for a living.       
The word got around that he knew a lot about compilers, and in January 1962, in his second year at Cal Tech, Addison-Wesley asked him to write a book on compilers. He sketched 12 chapters and signed a contract. After receiving his PhD in 1963, Knuth began working on a chapter on sorting, a topic related to some compilers. He read many technical articles, and noticed the spotty and sometimes unreliable nature of the literature in the, then new, field of computer science. He saw the need for someone to write a book which organized and reliably presented what was then known about the field. Knuth was a good writer and had an instinct for trying to organize things, so he decided to tackle it.  He used a quantitative rather than qualitative approach, and emphasized aesthetics—the creation of programs that are beautiful. The book grew longer as he wrote it, reaching 3,000 hand-written pages (the equivalent of 2,000 printed pages) by the time he finished the first draft of the 12 chapters in June 1965.

Addison-Wesley decided that the 12 chapters should be reorganized into 7 volumes, with a chapter or two per volume. The first four volumes [1] were to be on basic concepts and information structures (volume 1, chapters 1 and 2), random numbers and arithmetic (volume 2, chapters 3 and 4), sorting and searching (volume 3, chapters 5 and 6), and combinatorial algorithms (volume 4, now scheduled to be divided into at least two volumes). Volumes 5-7 were to be the more compiler specific chapters (lexical scanning and parsing, context free languages, and compiler techniques).

Knuth describes how The Art of Computer Programming series became his lifetime project.       
Volume 1 of The Art of Computer Programming was published in 1968. That same year Knuth moved from Cal Tech to Stanford University, a move motivated partly by the fact Stanford also agreed to hire his colleague Robert Floyd, the 1978 Turing Award winner.

Knuth on Stanford, computer science, and Robert Floyd.       
By 1973 Knuth had published volumes 1-3 of The Art of Computer Programming (“TAOCP”), which did the job Knuth intended of summarizing what was then known about the topics covered in those first six chapters. TAOCP emphasized a mathematical approach for comparing algorithms to find out how good a method is. Knuth says that when he decided this approach, he suggested to his publishers renaming the book The Analysis of Algorithms, but they said "We can’t; it will never sell." Arguably, the books established analysis of algorithms as a computer science topic in its own right. Knuth has stated that developing analysis of algorithms as an academic subject is his proudest achievement.


Turing Award

The first three volumes of TAOCP had great impact on the field and encouraged many people to build on his work. In 1974 Knuth was awarded the ACM's Alan M. Turing Award, with the citation specifically citing his book series. B. A. Galler commented [7]:

The 1974 A.M. Turing Award was presented to Professor Donald E. Knuth of Stanford University for a number of major contributions to analysis of algorithms and the design of programming languages, and in particular for his most significant contributions to the "art of computer programming" through his series of well-known books. The collections of technique, algorithms, and relevant theory in these books have served as a focal point for developing curricula and as an organizing influence on computer science.

The Turing citation also refers to "design of programming languages", the topic that first hooked Knuth on computers, and an area in which he was active from 1957-1971 [d].


TeX and METAFONT: typesetting and font design

Knuth is well-known for his perfectionism, and offers to pay $2.56 for each error found in TAOCP books. Finding one confers prestige on the discoverer, many of whom frame and display the hand-signed check rather than cashing it.

As the topics covered by volumes 1-3 developed, Knuth revised them. He was deeply disappointed when, in 1973, he saw the typesetting from Addison-Wesley for the second edition of volume 2. By then the publishing industry had replaced traditional mechanical typesetting technology with computerized typesetting that did not reproduce the high quality of the original printings of volumes 1-3.

Knuth explains the origins and motivations of the TeX project.       
Consequently, in 1977 Knuth began developing a new typesetting system to enable high quality computerized typesetting, in particular for TAOCP. This system was announced in his 1978 American Mathematical Society Gibbs Lecture entitled "Mathematical Typography" and published in the Bulletin (New Series) of the American Mathematical Society, volume 1, 1979, pp. 337-372. Knuth had two goals for his system:

(1) achieving the finest quality printed documents
(2) creating a system that would be archival in the sense that it was independent of changes in printing technology to the maximum extent possible.

Knuth recalls the design and implementation of TeX.       
Knuth's system, developed with help from Stanford students and colleagues, had three primary components: the TeX typesetting engine, the METAFONT font design system, and the Computer Modern set of type fonts [4].  Combined, these revolutionized digital typesetting. Knuth made his code publicly available, and it has been widely adapted by commercial typesetting systems.

Knuth explains why he hated the initial output of TeX and how he learned to take fonts seriously.       
Knuth put hooks in his TeX engine so that others could make additions, with the condition that any resulting system be give a different name. That produced a vibrant, worldwide community of users and developers for TeX and related systems like LaTeX, ConTeXt, LuaTeX. Knuth's TeX was an early success story for the free and open-source software movement.

Knuth thought his typesetting work would take a year or two, but it was not until 1990 that he announced that he would make no further changes to his systems except to correct serious bugs.

Structured and literate programming

In the early 1970s Knuth learned the "structured programming" methodology promoted by Dijkstra, Hoare,  Dahl, and others. TeX and METAFONT were the first large programs Knuth had written since 1970, and he wrote them using structured programming.

The first version of TeX was written in the SAIL (Stanford Artificial Intelligence Language) programming language. People other than Knuth began to use TeX in the summer of 1978. While working to make a more portable Pascal-language version of TeX, Knuth experimented with typesetting the software itself. This led to a system he called DOC to support structured programming and documentation of the program. DOC was used in the spring of 1980 to create a highly portable version of TeX.

The TeX Users Group was also established in early 1980.  Once enough user feedback was gathered, Knuth decided that TeX and METAFONT needed to be rewritten. The original program was renamed TeX78, and the new program was called TeX82. In writing TeX82, Knuth decided DOC also needed to be rewritten and he created WEB, so called because it created a web of program and documentation that was both a compilable program and beautiful documentation. METAFONT was also rewritten in WEB. The second and fourth volumes of bibliographic item 4 illustrate TeX and METAFONT documented using WEB—what Knuth called literate programming.  Later versions and additions to WEB were based on the C programming language.

Knuth describes the concept of “literate programming”.       
Other activities, TAOCP continued, and Knuth's overall approach

Throughout his career, Knuth has published extensively in a variety of technical areas; bibliographic item [7] lists the volumes of his collected papers in eight different topic areas. At Stanford he supervised more than 30 PhD students. He created important courses such as Analysis of Algorithms [2], Concrete Mathematics [3], and the legendary Programming and Problem Solving Seminar.

In addition to his own teaching and research, Knuth has served the computing community on professional society committees, as an invited lecturer on many occasions, and on the editorial boards of more than 30 technical journals. He is the holder or co-holder of 5 patents.

Knuth considers TAOCP his masterwork, and in 1993 he retired early to spend more time writing additional volumes. He had produced revised editions of volumes 1-3 in 1978-1979. He designed a new hypothetical computer to replace the MIX computer of volumes 1-3 for the analysis of algorithms; this new computer was described in Knuth's 1999 book devoted to the topic [8].

Knuth began releasing volume 4A of TAOCP, on combinatorial algorithms, in fascicles ranging from 128 to 250 pages. In early 2011 the 921-page volume 4A was published, but the later parts of chapter 7 were reserved for future volumes.

Donald Knuth is one of the preeminent computer scientists of our time. He has made major contribution to many areas, in effect pursuing multiple simultaneous and serial careers, any one of which would be a proud lifetime achievement for other people. He credits much of the success of his work to combining theory with practice. Knuth is the rare theoretician who writes many lines of code every day. Programming is an art he practices often.

Knuth married Nancy Jill Carter in 1961. They have two children, John Martin (born 1965) and Jennifer Sierra (born 1966).

Knuth has been widely interviewed, both for print and on video. The TeX Users Group maintains a fairly comprehensive list of his interviews.


Essay Sources

a. "Donald Knuth," Interviewed by Donald J. Albers and Lynn A. Steen, Mathematical People: Profiles and Interviews, Donald J. Albers and G. L. Alexanderson, editors, Birkhauser, Boston, 1985, pp. 182-203.
b. Donald Knuth, "Robert W Floyd, In Memoriam," ACM SIGACT News, Volume 34 Issue 4, December 2003, pp. 3-12.
c. "The Art of Computer Programming," June 2011 interview of Knuth by British Computer Society editor Justin Richards, http://www.bcs.org/content/conWebDoc/40462
d. Donald Knuth, Selected Papers on Computer Languages, see the 2003 volume of bibliographic item 7.
e. Donald Knuth, Digital Typography, see the 1999 volume of bibliographic item 7.
f. Donald Knuth, Selected Papers on Computer Science, see the 1996 volume of bibliographic item 7.
g. Donald Knuth, Literate Programming, see the 1992 volume of bibliographic item 7.
h. Knuth's personal website: http://www-cs-faculty.stanford.edu/~uno/
i. Knuth's curriculum vitae (CV) : http://www-cs-faculty.stanford.edu/~uno/vita.pdf

Author: David Walden



唐纳德-E-克努斯
诞生。
1938年1月10日，在威斯康星州的密尔沃基。

教育经历。
毕业于密尔沃基路德中学（1956年）；凯斯理工学院数学学士（1960年），他的本科工作非常出色，经学院特别投票，他被同时授予硕士学位；加州理工学院数学博士（1963年）。

工作经验。
加州理工学院助理教授，然后是副教授（1963-1968）；斯坦福大学一系列全职和指定教授职位（1968-1992）；斯坦福大学计算机编程艺术荣誉教授（1993年起）。

荣誉和奖项。
克努斯获得了100多个奖项和荣誉。其中包括。第一届ACM格雷斯-默里-霍普奖（1971年）；美国艺术与科学院院士（1973年）；艾伦-M-图灵奖（1974年）；美国国家科学院院士（1975年）；莱斯特-R-福特奖（1975年和1993年）；斯坦福大学计算机编程艺术荣誉教授（从1993年开始）。福特奖（1975年和1993年）；美国数学学会吉布斯讲座（1978年）；国家科学奖（1979年，由卡特总统颁发）；国家工程院院士（1981年）；IEEE计算机协会计算机先锋奖（1982年）；富兰克林奖（1988年）；哈维奖（1995年）；IEEE约翰-冯-诺伊曼奖（1995年）；京都奖（1996年）；计算机历史博物馆研究员（1998年）。


DONALD ("DON") ERVIN KNUTH DL作者简介链接
美国 - 1974年
嘉奖
因其对算法分析和编程语言设计的重大贡献，特别是通过其著名的连续系列书籍对 "计算机编程艺术 "的贡献，以这个标题。

简短注释
书目
亚马逊图灵奖
讲座
研究
题目
视频采访
Donald Ervin "Don" Knuth于1938年1月10日出生在威斯康星州的密尔沃基。他的父亲是路德教会高中的一名教师，也是一名教堂风琴师。唐-克努斯上过路德宗高中，在后来的生活中，也成为了一名教堂风琴师。

教育背景

在七、八年级时，Knuth对英语语法的结构非常感兴趣。在高中时，他对物理学感兴趣，并擅长数学。进入大学后，他想知道是主修物理学还是音乐，但他选择了前者，因为他得到了俄亥俄州克利夫兰市凯斯技术学院的奖学金。在大学二年级时，他把专业从物理学改为数学，部分原因是他在科学实验方面有困难。

在大一期间，Knuth在统计学实验室工作，画图、打钥匙、制表卡和使用卡片分拣机。1956年12月，他在大厅对面发现了新安装的IBM 650计算机。650让他很感兴趣，他花了1957年夏天的大部分时间去了解它的工作原理。他在大学期间写了各种有趣的程序，包括一个为他管理的篮球队成员的表现评分的程序。

Knuth回忆起他的第一次计算机编程，是为IBM 650编程。       
Knuth在凯斯大学的数学研究非常出色，当他完成学士学位后，学院授予他数学硕士学位。

计算机编程的艺术

在加州理工学院攻读数学博士期间，Knuth还做了私人咨询，并为各种计算机编写了编译器。

Knuth描述了他为Burroughs编写的Algol编译器，以及他决定不以开发商业软件为生。       
他知道很多关于编译器的消息，1962年1月，在他在加州理工学院的第二年，Addison-Wesley请他写一本关于编译器的书。他草拟了12个章节并签署了一份合同。1963年获得博士学位后，Knuth开始撰写关于排序的章节，这是一个与一些编译器有关的话题。他阅读了许多技术文章，并注意到在当时新的计算机科学领域中，文献的斑驳和有时不可靠的性质。他认为需要有人写一本书来组织和可靠地介绍当时该领域的知识。克努特是个好作家，而且有一种试图组织事物的本能，所以他决定去解决这个问题。 他采用了定量而非定性的方法，并强调美学--创造出漂亮的程序。这本书越写越长，到1965年6月他完成12章的初稿时，手写页数已达3000页（相当于2000页印刷页）。

爱迪生-韦斯利公司决定将这12个章节重新组织成7卷，每卷一到两章。前四卷[1]是关于基本概念和信息结构（第一卷，第一和第二章）、随机数和算术（第二卷，第三和第四章）、排序和搜索（第三卷，第五和第六章）以及组合算法（第四卷，现在计划至少分成两卷）。第5-7卷将是更多关于编译器的具体章节（词法扫描和解析、无语境语言和编译器技术）。

Knuth描述了《计算机编程的艺术》系列是如何成为他的终身项目的。       
计算机编程的艺术》第一卷于1968年出版。同年，Knuth从加州理工学院搬到了斯坦福大学，此举的部分原因是斯坦福大学也同意雇用他的同事Robert Floyd，即1978年的图灵奖得主。

Knuth关于斯坦福大学、计算机科学和罗伯特-弗洛伊德。       
到1973年，Knuth已经出版了《计算机编程的艺术》（"TAOCP"）的第1-3卷，该书完成了Knuth的工作，总结了当时关于前六章所涵盖的主题的知识。TAOCP强调了一种比较算法的数学方法，以发现一种方法有多好。Knuth说，当他决定采用这种方法时，他向他的出版商建议将这本书改名为《算法分析》，但他们说："我们不能这样做，它永远不会卖。" 可以说，这本书确立了算法分析作为一个计算机科学主题的地位。Knuth曾表示，将算法分析发展为一个学术课题是他最自豪的成就。


图灵奖

TAOCP的前三卷对该领域产生了巨大影响，并鼓励许多人在他的工作基础上继续努力。1974年，Knuth被授予ACM的Alan M. Turing奖，引文中特别提到了他的系列书籍。B. A. Galler评论说[7]。

1974年A.M.图灵奖被授予斯坦福大学的Donald E. Knuth教授，以表彰他对算法分析和编程语言设计的一些重大贡献，特别是通过他的一系列著名书籍对 "计算机编程艺术 "的最重大贡献。这些书中的技术、算法和相关理论的集合已经成为开发课程的焦点，并对计算机科学产生了组织性影响。

图灵引文还提到了 "编程语言的设计"，这是让Knuth第一次迷上计算机的话题，也是他在1957-1971年间活跃的领域[d]。


TeX和METAFONT：排版和字体设计

Knuth以他的完美主义而闻名，他愿意为在TAOCP书籍中发现的每个错误支付2.56美元。发现一个错误就会给发现者带来声望，许多人都会把亲笔签名的支票裱起来展示，而不是把它兑现。

随着第1-3卷所涵盖的主题的发展，Knuth对其进行了修订。1973年，当他看到Addison-Wesley公司对第二卷的排版时，他感到非常失望。那时，出版业已经用电脑排版取代了传统的机械排版技术，而电脑排版并没有再现第1-3卷原始印刷的高质量。

Knuth解释了TeX项目的起源和动机。       
因此，1977年Knuth开始开发一个新的排版系统，以实现高质量的计算机排版，特别是为TAOCP。这个系统在他1978年的美国数学会吉布斯讲座中公布，题为 "数学排版"，并发表在《美国数学会公报（新系列）》第1卷，1979年，第337-372页。Knuth对他的系统有两个目标。

(1) 实现最优质的印刷文件
(2) 创建一个可以存档的系统，即在最大程度上不受印刷技术变化的影响。

Knuth回顾了TeX的设计和实施。       
Knuth的系统是在斯坦福大学学生和同事的帮助下开发的，有三个主要组成部分：TeX排版引擎、METAFONT字体设计系统和计算机现代字体集[4]。 这些东西结合起来，彻底改变了数字排版。Knuth公开了他的代码，并被商业排版系统广泛采用。

Knuth解释了他为什么讨厌TeX的最初输出，以及他如何学会认真对待字体。       
Knuth在他的TeX引擎中设置了钩子，以便其他人可以进行补充，但条件是任何产生的系统都要有一个不同的名字。这为TeX和相关系统（如LaTeX、ConTeXt、LuaTeX）产生了一个充满活力的全球用户和开发者社区。Knuth的TeX是自由和开源软件运动的一个早期成功案例。

Knuth认为他的排版工作需要一两年的时间，但直到1990年，他才宣布，除了纠正严重的错误，他不会再对他的系统做任何改动。

结构化和文学化的编程

20世纪70年代初，Knuth学会了Dijkstra、Hoare、Dahl等人提倡的 "结构化编程 "方法。TeX和METAFONT是Knuth自1970年以来写的第一个大型程序，他用结构化编程写了这些程序。

TeX的第一个版本是用SAIL（斯坦福人工智能语言）编程语言写的。1978年夏天，除Knuth之外的人开始使用TeX。在努力制作TeX的更便携的Pascal语言版本时，Knuth对软件本身的排版进行了实验。这导致了一个他称之为DOC的系统，以支持结构化编程和程序的文档。1980年春天，DOC被用来创建一个高度便携的TeX版本。

TeX用户组也在1980年初成立。 一旦收集到足够的用户反馈，Knuth决定TeX和METAFONT需要重写。原来的程序被重新命名为TeX78，而新的程序被称为TeX82。在编写TeX82的过程中，Knuth决定DOC也需要重写，他创造了WEB，之所以叫WEB是因为它创造了一个程序和文档的网络，既是一个可编译的程序，又是一个漂亮的文档。METAFONT也是用WEB重写的。书目4的第二和第四卷说明了使用WEB记录的TeX和METAFONT--Knuth称之为识字编程。 后来的版本和对WEB的补充是基于C编程语言的。

Knuth描述了 "识字编程 "的概念。       
其他活动，TAOCP继续，以及Knuth的整体方法

在他的职业生涯中，Knuth在各种技术领域发表了大量的文章；书目项目[7]列出了他在八个不同主题领域的论文集卷。在斯坦福大学，他指导了30多名博士生。他创建了一些重要的课程，如算法分析[2]、具体数学[3]，以及传说中的编程和问题解决研讨会。

除了他自己的教学和研究之外，Knuth还在专业协会委员会中为计算机界服务，多次作为特邀讲师，并在30多个技术期刊的编辑委员会中任职。他是5项专利的持有人或共同持有人。

Knuth认为TAOCP是他的代表作，1993年他提前退休，以便花更多时间编写更多卷。他曾在1978-1979年制作了1-3卷的修订版。他设计了一台新的假想计算机，以取代1-3卷中的MIX计算机，用于分析算法；这台新的计算机在Knuth 1999年出版的专门讨论该主题的书中有描述[8] 。

Knuth开始发布关于组合算法的TAOCP第4A卷，分册发布，篇幅从128页到250页不等。2011年初，921页的第4A卷出版了，但第7章的后期部分被保留给未来的卷。

唐纳德-克努特是我们这个时代最杰出的计算机科学家之一。他在许多领域都做出了重大贡献，实际上是在追求多个同时和连续的事业，其中任何一个对其他人来说都是值得骄傲的终身成就。他将自己工作的成功大部分归功于理论与实践的结合。Knuth是少有的每天都要写很多行代码的理论家。编程是他经常练习的一种艺术。

Knuth于1961年与Nancy Jill Carter结婚。他们有两个孩子，约翰-马丁（1965年出生）和珍妮弗-塞拉（1966年出生）。

Knuth曾被广泛采访，包括印刷品和视频。TeX用户组有一份相当全面的他的采访清单。


论文来源

a. "Donald Knuth"，由Donald J. Albers和Lynn A. Steen采访，Mathematical People: Profiles and Interviews, Donald J. Albers and G. L. Alexanderson, editors, Birkhauser, Boston, 1985, pp.182-203.
b. Donald Knuth, "Robert W Floyd, In Memoriam," ACM SIGACT News, Volume 34 Issue 4, December 2003, pp.3-12。
c. "计算机编程的艺术"，2011年6月英国计算机协会编辑Justin Richards对Knuth的采访，http://www.bcs.org/content/conWebDoc/40462
d. Donald Knuth，《计算机语言论文选》，见2003年卷书目7。
e. 唐纳德-努斯，《数字排版》，见1999年书目第7卷。
f. 唐纳德-克努斯，《计算机科学论文选》，见1996年书目第7卷。
g. Donald Knuth, Literate Programming, 见1992年的书目第7卷。
h. Knuth的个人网站：http://www-cs-faculty.stanford.edu/~uno/
i. Knuth的简历（CV）：http://www-cs-faculty.stanford.edu/~uno/vita.pdf

作者。David Walden