|
|
http://www-history.mcs.st-and.ac.uk/Biographies/Knuth.html
Donald Knuth's parents were Ervin Henry Knuth and Louise Marie Bohning. Donald's father Ervin was a school teacher who taught in a Lutheran school. He played a very important role in determining Donald's interests, and it was through his father that that Donald gained his love for education, music, and mathematics. Ervin played the church organ at the Sunday church services and Donald soon became a passionate lover of the organ.
Donald attended Lutheran schools and from the special emphasis that was placed on English grammar in these schools came Knuth's love of investigating sentence structure. His fascination with this in his first couple of years of secondary school would lead naturally towards writing computer code when he eventually encountered computers, but this did not happen until after his school education was complete. During these first years at secondary school there were other signs of where Knuth's interests would eventually lead. One episode, repeated in most biographies of Knuth but still worth repeating in this one, concerns "Ziegler's Giant Bar."
He entered a competition set up by the confectionary manufacturer Ziegler. The aim was to see how many words could be made with the letters of "Ziegler's Giant Bar" and for the schoolboy Knuth this was exactly the sort of challenge that he loved. He spent two weeks during which he pretended to be ill and, using a dictionary, he came up with 4500 words. The judges for the competition had only found 2500 and Knuth was an easy winner. He commented afterwards that had he thought to use the apostrophe he could have found many more! His school benefited by receiving a television set as a prize.
At high school Knuth's interests were more directed towards music than they were to mathematics. His musical interests involved both playing and composing music and he decided at that stage that he would study music after graduating from high school. Knuth played the saxophone, and later the tuba, in his school band. Although he spent much time with his musical interests, Knuth most certainly did not neglect his other school subjects. He graduated from High School in 1956 with the highest grade point average that anyone had ever achieved at his school.
At school he had begun to show an interest in mathematics and he amused himself by trying to visualise surfaces in several dimensions by plotting the graphs obtained by keeping all but one of the variables fixed. This is an excellent way to understand mathematical functions and today with the aid of computers this, and more sophisticated techniques, can quickly give students a deep understanding. However Knuth had to plot his graphs by doing hand calculations for every value which he plotted, showing the same sort of dedication to putting hours of work into problems that he had shown with the "Ziegler's Giant Bar" competition. One might have thought that his teachers would have believed that he could succeed at college in almost any subject he chose given his outstanding school performance, but this was not really so. The problem was that Knuth did not believe in himself at this stage in his life and so his teachers doubted whether he had the personality, in particular the confidence, to succeed.
It shows how undecided Knuth was about the direction his studies might take that when offered a scholarship to Case Institute of Technology in Cleveland, Ohio, to study physics he accepted despite his previous intentions to study music. He entered the physics course at the Case Institute in September 1956. There were really two reasons why, from his second year on, Knuth started to move towards mathematics and away from physics. One day when Knuth was meant to be performing with the College band he missed the bus taking the band to the performance so, finding himself with free time, he tried to solve a challenge problem that one of his mathematics professors had set. Solving it earned Knuth an automatic "A" in that class and also the right sort of boost he needed to think that perhaps mathematics rather than physics was for him. Secondly he found that physics practicals did not suit him, so in the end the move towards mathematics became a natural one to make.
In fact Knuth already had his first encounter with computers in his first year at Case before he made the move towards mathematics. He had to use the IBM 650 and consulted the manual to find out how to write programs [1]:-
... the manual we got from IBM would show examples of programs and I knew I could do ... better than that. So I thought I might have some talent.
Knuth used his growing expertise at writing computer programs to produce one in 1958 to analyse the performance of the College basketball team. It led to some publicity and IBM used a photograph of Knuth in their advertising. One might have expected that events would begin to help him overcome his inferiority complex but he still felt that he was not up to standard. This had the effect of making him put in large amounts of extra work at his academic studies. The result was that when he graduated with his B.S. in June 1960 he was awarded a distinction and, in a quite unique move, the College awarded him a Master's Degree at the same time, such was the brilliance of his performance. Knuth was awarded two Fellowships, a Woodrow Wilson Fellowship and a National Foundation Fellowship in the year of his graduation.
It is a real achievement to publish a mathematics paper while still a doctoral student, but Knuth managed to publish two papers in the year he completed his undergraduate degree. These were An imaginary number system and On methods of constructing sets of mutually orthogonal Latin squares using a computer I the latter paper being written jointly with R C Bose and I M Chakravarti. In the first Knuth describes an imaginary number system using the imaginary number 2i as its base, giving methods for the addition, subtraction and multiplication of the numbers. In the second paper Knuth and his co-authors give two sets of five mutually orthogonal Latin squares of order 12.
In the autumn of 1960 Knuth entered the California Institute of Technology and, in June 1963, he was awarded a Ph.D. in mathematics for his thesis Finite semifields and projective planes. In fact in addition to the work for his doctorate in mathematics, Knuth had from 1960 begun to put his very considerable computing expertise to uses other than writing papers becoming a software development consultant to the Burroughs Corporation in Pasadena, California. Knowledge of his computing expertise was so well established by 1962 that, although he was still a doctoral student at the time, Addison-Wesley approached him and asked him to write a text on compilers. He began that project in the summer of 1962.
His publications from this time show that he was applying computing to combinatorial mathematical problems which were not connected to the work he was undertaking for his thesis. For example he computed Euler's constant to 1271 decimal places and published the result in 1962. In the same year he published work on the evaluation of polynomials by computer. Despite Knuth's remarkable mathematical productivity he did find time for other things. During his years as a graduate student Knuth married Nancy Jill Carter on 24 June 1961. Their two children John Martin Knuth and Jennifer Sierra Knuth were born in 1965 and 1966 respectively.
We noted above that the title of Knuth's Ph.D. thesis was Finite semifields and projective planes. A semifield is an algebraic structure satisfying all the usual axioms for a division ring except associativity of multiplication. The thesis contains a wealth of information on finite semifields and their connections to certain types of projective planes. After completion of his doctorate in 1963 Knuth became an Assistant Professor of Mathematics at the California Institute of Technology, being promoted to Associate Professor in 1966. From 1964 to 1967 he worked as an Editor of Programming Languages for the Association for Computing Machinery. He continued to apply computing to algebraic and combinatorial mathematics problems. For example in 1964 he published tables of data for finite fields which enabled rapid computer calculations to be carried out. His great love of music, which he had almost devoted his life to, continued and in 1965 he joined the American Guild of Organists. He would continue to play music, compose music and has even designed of his own pipe organ.
By 1966 his book on compilers had grown to 3000 handwritten pages and Addison-Wesley realised that here was a much more major work than they had originally envisaged. Discussions led to a decision that Knuth should produce a seven volume work covering much more than compilers. The work became The Art of Computer Programming and publication began in 1968 when Volume 1: Fundamental Algorithms appeared. Volume 2: Seminumerical algorithms came out in the following year, and Volume 3: Sorting and searching in 1973. In the Preface Knuth writes that these are:-
... books that have been designed to train the reader in the various skills which go into a programmer's craft... [They are] not meant to serve as an introduction to computer programming; the reader is supposed to have some previous experience. [I aim to provide] (a) reference books which summarize the knowledge which has been acquired in several important fields, and (b) textbooks for self-study or for college courses in the computer and information sciences.
Knuth's aim was to:-
... organize and summarize what is known about the fast subject of computer methods and to give it firm mathematical and historical foundations.
... show that the connection between computers and mathematics is far deeper and more intimate than these traditional relationships would imply.
M Muller, reviewing these wonderful books, writes that:-
Knuth has already made a timely and great contribution. He has managed to provide organization of ideas where little existed before; he has provided many ideas which in essence are new and helpful in obtaining a basis of abstraction, integration, or unification of efforts of earlier workers in the various fields covered.
In 1968 Knuth was appointed as Professor of Computer Science at Stanford University. At the same time as he left the California Institute of Technology he also resigned his consultancy position with the Burroughs Corporation. Knuth remained at Stanford University for the remainder of his career. He was appointed Fletcher Jones Professor of Computer Science in 1977 and in 1990 he was named Professor of The Art of Computer Programming. In 1993 he became Professor Emeritus at Stanford University and continued to live on the University Campus.
Knuth has made many contributions to mathematics and computing. One particular contribution we should mention is the Knuth-Bendix algorithm, one of the fundamental algorithms for computing with algebraic structures, particularly with groups and semigroups. This important contribution, published jointly with his student Peter B Bendix in 1970, attempts to solve solve the word problem in algebraic systems by deriving consequences of given relations to give, in some sense, a complete set. Another contribution, which has totally changed the whole way that mathematics is printed and communicated is Knuth's invention of TeX, a language for typesetting mathematical and scientific articles. Starting in 1976 Knuth took ten years off his other projects to work on the development of TeX and METAFONT, a computer software system for alphabet design.
TeX has changed the technology of mathematics and science publishing since it enables mathematicians and scientists to produce the highest quality of printing of mathematical articles yet this can be achieved simply using a home computer. However, it has not only changed the way that mathematical and scientific articles are published but also in the way that they are communicated. In the 17th century a mathematician would have written a letter to another mathematician and they would discuss their everyday lives in English, French or German, say, but whenever they came to explain a piece of mathematics they would use Latin. Nowadays mathematicians communicate by e-mail and whenever they want to explain a piece of mathematics they require mathematical symbols which almost always they communicate using TeX. Nobody, to our knowledge, has tried to measure the impact of TeX on the level of mathematical production, and indeed this would be a very difficult thing to measure, but nevertheless I [EFR] am certain that the added ease of production and communication of mathematics using TeX has had a major impact on the subject over the last ten years, say.
We should mention a few of the many further contributions by Knuth: semantics of programming languages; attribution grammar; the development of LR(k) parsing; the Knuth-Morris-Pratt algorithm which searches for a string of characters; and structured documentation and literate programming. The work on LR(k) parsing appeared in a 1965 paper On the translation of languages from left to right. In this paper Knuth writes:-
There has been much recent interest in languages whose grammar is sufficiently simple that an efficient left-to-right parsing algorithm can be mechanically produced from the grammar. In this paper, we define LR(k) grammars, which are perhaps the most general ones of this type, and they provide the basis for understanding all of the special tricks which have been used in the construction of parsing algorithms for languages with simple structure, e.g., algebraic languages.
The Knuth-Morris-Pratt pattern matching algorithm was published in the 1977 paper Fast pattern matching in strings. Knuth continues to publish important contributions to computer science, combinatorics and algebra, the topic of his doctoral thesis. For example in the latter area he published Efficient representation of perm groups in 1991. He writes in the introduction:-
This note presents an elementary version of C C Sims's algorithm for computing strong generators of a given perm group, together with a proof of correctness and some notes about appropriate low-level data structures.
For his quite remarkable contributions Knuth has received many honours - far too many to be mentioned in an article of this length. Let us just list a small selection. He was the first recipient of the Grace Murray Hopper Award from the Association for Computing Machinery in 1971; he was elected a Fellow of the American Academy of Arts and Science in 1973; in 1974 he won the Alan M Turing Award from the Association for Computing Machinery; he was elected to the National Academy of Sciences in 1975; in the same year he won the Lester R Ford Award from the Mathematical Association of America; he was awarded the National Science Medal in 1979 (presented to him by President Carter); he was elected to the National Academy of Engineering in 1981; he was elected an honorary member of the IEEE in 1982 and awarded their Computer Pioneer Award in the same year; he was awarded the Steele Prize for Expository Writing from the American Mathematical Society in 1986; he was awarded the Franklin Medal in 1988; he was elected to the Académie des Sciences in 1992; he was awarded the Adelskold Medal from the Swedish Academy of Sciences in 1994; he was awarded the John von Neumann Medal from the IEEE in 1995; and the Kyoto Prize from the Inamori Foundation in 1996.
Let us mention a few of the honours that Knuth has received since 2000. He has received honorary degrees from a large number of universities world-wide: Waterloo University, Canada (2000), Tübingen University (2001), the University of Oslo (2002), Antwerp University (2003), Harvard University (2003), the University of Macedonia (2003), Montreal University (2004), ETH Zurich (2005), Concordia University (2006), Wisconsin University (2006), the University of Bordeau (2007). In 2003 he was elected to the Royal Society of London, and in 2008 to the Russian Academy of Sciences. He was awarded the Gold Medal from the State Engineering University of Armenia in 2006, and in the same year the gold medal from Yerevan State University. In 2001 the minor planet "(21656) Knuth" was named after him.
Finally let us quote from the Stanford Magazine about Knuth's daily life following retirement:-
In retirement, he still writes several programs a week. He no longer advises students, but he hosts free public Computer Musings talks several times a year, drops in on graduate-level courses occasionally, and bikes to campus most days of the week to use the libraries or swim at the aquatic centre. |
|
发表于 2013-9-24 12:13:17
