Algorithm 版 (精华区)

发信人: Lerry (坐壮:望苗:思汉@贵族 与猫族斗争到底), 信区: Algorithm
标  题: Donald E. Knuth(1974) 
发信站: 哈工大紫丁香 (2002年04月26日08:00:14 星期五), 站内信件

Donald E. Knuth
Born: 1938
Nationality: American
Occupation: computer scientist and mathematician
Source: Notable Mathematicians. Gale Research, 1998.
Table of Contents
Biographical Essay
Works
BIOGRAPHICAL ESSAY
It is not often in the world of scientific discovery where one man has contr
ibuted a body of knowledge to a topic so far in excess of others in the fiel
d. Donald Knuth has done for computer science as Albert Einstein did for phy
sics with his theories of relativity. Knuth was born January 10, 1938 in Mil
waukee, Wisconsin, to Ervin Henry Knuth and Louise Marie Bohning. His father
 had the distinction of being the first college graduate in the Knuth family
 and started his professional career as a gradeschool teacher. Later he was
employed as a bookkeeping teacher in a private Lutheran high school. Knuth's
 father also instilled an appreciation for music, playing the church organ f
or Sunday services. His talent for mathematics, education and music left a l
egacy for his son. Today, Knuth's talent and accomplishments have inspired a
nd improved the entire world.
Knuth Learns Music, English and Math
Early on, Knuth realized that most of the schoolwork required of him from mi
ddle school to college consisted mostly of writing and mathematics. Understa
nding this, he mastered both disciplines. Since his father was an educator i
n a Lutheran high school, Knuth attended Lutheran schools. These schools wer
e very strong in English education, particularly in sentence structure and g
rammar. Knuth remembers that in the 7th and 8th grades, one of his favorite
activities was diagraming sentences with classmates. Although they could dia
gram all the sentences in their English books, they always had trouble with
sentences that were seen in everyday life--on billboards, posters, advertise
ments--but most particularly those found in the church hymnals. The students
 worked very hard on these problems, and although Knuth never says if they f
igured them out, he does say those same students breezed through English cla
ss when they moved on into high school.
One of Knuth's fond memories is the Ziegler's Candies contest. The manufactu
rers of the Ziegler's candy bar sponsored a contest where contestants had to
 see how many words they could find in the letters in "Ziegler's Giant Bar."
 In the 8th grade, Knuth knew he had a knack for problems like this, so he e
ntered. He told his parents he had a stomachache and for two weeks he stayed
 home "'sick'--all the while poring over an unabridged dictionary finding as
 many words as possible. Without using the apostrophe, Knuth's list containe
d about 4,500 words; there were only 2,500 words on Ziegler's master list. T
he grand prize was a television set for the school and enough Ziegler candy
bars to feed the entire student body."
In high school, Knuth entered the Westinghouse Science Talent Search with hi
s proposal "The Potrzebie System of Weights and Measures." This was an imagi
nary, but very clearly defined, system that would replace our units of ounce
s, pounds, inches, and feet. In a style that is typical of Knuth, he defined
 his units, including the "potrzebie" (the thickness of MAD Magazine issue 2
6) and the "whatmeworry" (the basic unit of power). Not only did this propos
al win an honorable mention in the Westinghouse contest, he also earned $25
from MAD Magazine when they published the paper.
Knuth also did considerable work in high school learning about graphs. He wo
uld take a function of several variables, fix all but one, then vary the las
t one to see the changes in the shape of the graph. Of course, this was befo
re the advent of graphing calculators so each of his graphs were computed an
d plotted by hand.
Knuth graduated with the alltime record for grades at his high school. By th
e time he left high school Knuth was an accomplished mathematician, writer,
and musician but was undecided about what he wanted to study in college. He
said that his choice was determined by the school he chose. Due to scholarsh
ip considerations, he chose to attend the Case Institute of Technology, majo
ring in physics.
Knuth Meets the Computer
It was in college that Knuth was first introduced to an IBM 650 computer. Th
is was one of the first mainframe computers made by the computer system pion
eer. He obtained a copy of the manual and studied it cover to cover. In an i
nterview with Donald Albers, Knuth said, "the manual we got from IBM would s
how examples of programs and I knew I could do . . . better than that. So I
thought I might have some talent." Little did he realize how prophetic that
statement was. He wrote programs on the old IBM machine that would teach it
how to play tictactoe and performing prime number factorization.
In 1958, Knuth developed a basketball player analysis for the college team,
so impressing the coach that he used it, claiming that it helped the team wi
n a league championship. Newsweekwrote an article about the program and IBM
used a publicity photo of Knuth standing next to the machine.
In college, Knuth always had a fear that he was not good enough to succeed,
so he took on a tremendous amount of unassigned, ungraded work to solidify h
is knowledge of the subject. Although he started at Case as a physics major,
 Knuth's interests turned toward mathematics as a sophomore. While taking a
course in abstract mathematics, the professor assigned a problem--finding th
e correct solution would earn the solver an automatic "A" in the class. Knut
h found himself having some extra time, and by what he calls "a stroke of lu
ck" was able to solve it. He turned it in, the professor gave him the "A" an
d he cut the rest of the class for the semester. Knuth's conscience caught u
p with him, so when the class was offered the following year, he worked as t
he class grader. His difficulty with the physics lab classes that were requi
red for his major finally caused him to switch to mathematics. Knuth's work
at the university was so distinguished, that upon receiving his Bachelor of
Science degree in 1960, the faculty made the unprecedented move of awarding
him a concurrent Master's degree in mathematics.
After graduation, Knuth moved to California and enrolled at the California I
nstitute of Technology. He was awarded in doctorate in mathematics from CalT
ech in 1963 and joined the faculty as an assistant professor of math. Comput
er science was in his blood though, and he continued his study through his c
onsulting work with the Burroughs Corporation while working on his doctorate
. In the early 1960s, language compiler theory was not well developed. In fa
ct, most computer scientists had programmed computers using a very primitive
 assembly language. Language compilers are programs that convert a written p
rogram using words and structured syntax into the instruction codes that are
 understood by the computer hardware.
The Art of Computer Programming
Knuth had a fascination with compilers and compiler theory and in early 1962
, while still in graduate school, the publisher AddisonWesley asked him to w
rite a book about compilers. His project began that summer and after four ye
ars of writing and expanding the book's focus, his manuscript had grown to o
ver 3,000 pages. His finest work, The Art of Computer Programming was the pr
emier textbook through the 1970s and remains an invaluable reference and tea
ching tool for computer programmers. As of 1995, three of the seven volumes
have been published and his fourth volume, about combinatorial algorithms, i
s in progress.
Knuth's development of computer science has resulted in the discovery and es
tablishment of many fundamental rules and ideas. Included in this list is th
e concept of "lookahead," where a compiler will look ahead a few words to de
cide on a grammatical context for the prior words. He also expanded the conc
ept of the "attribute grammar" first proposed by Backus and Naur. The idea o
f inherited attributes forms the basis for the objectoriented programming te
chniques that are so prevalent in the computer programming industry in the 1
990s. But some of Knuth's most useful work has been his extensive exploratio
n of different computer algorithms and their efficiency. He dedicated an ent
ire volume of The Art of Computer Programming just to the study of algorithm
s.
Another interest of Knuth's has been typography. He wrote a paper called "Th
e Letter S" in which he studied the mathematical shape of the letter through
out history and what equations lead to the most aesthetically pleasing lette
r. Always one to do things one thing at a time, Knuth put his other projects
 on hold to develop two computer languages dealing with typography. His firs
t, called TEX, is a typesetting program; the second, METAFONT develops the s
hapes of the letters.
Knuth held a position as professor at Caltech until 1968, then he was offere
d a position at Stanford University. He continues as a professor emeritus at
 Stanford. In addition, Knuth has received numerous honorary degrees from ma
ny universities, including the University of Pennsylvania, State University
at Stony Brook, Grinnell College, Concordia University in Montreal, the Univ
ersity of Paris, the Royal Institute of Technology in Stockholm, and at St.
Petersburg's University in Russia.
Knuth won the Steele Prize, a high honor for computer scientists, for The Ar
t of Computer Programming in 1987. He is a fellow of the Guggenheim Foundati
on and recipient of the National Medal of Science, presented by President Ji
mmy Carter in 1979. Knuth was presented with the Alan M. Turing award in 197
4 and the Computer Pioneer award in 1982. Knuth was married Jill Carter in 1
961 and have two children, John and Jennifer. He lives near Stanford Univers
ity and continues to enjoy another of his loves: playing the pipe organ (whi
ch he designed).
Knuth's approach to the problems he has tackled in mathematics and computer
science are summed up in a quotation from Shasha and Lazere, "It's not true
that necessity is the only mother of invention. The other part is that a per
son has to have the right background for the problem . . . The ones I solve,
 I say, 'Oh, man, I have a unique background that might let me solve it--it'
s my destiny, my responsibility'."
WORKS
The Art of Computer Programming, 1968
Surreal Numbers: How Two ExStudents Turned on to Pure Mathematics and Found
Happiness, A Mathenmatical Novelette, 1974
Computer Modern Typefaces, 1986
Computers and Typesetting, 1986
METAFONTbook, 1986
The TEXbook, 1986
Axioms and Hulls, 1992
Literate Programming, 1992
Stable Marriage and Its Relation to Other Combinatorial Problems: An Introdu
ction to the Mathematical Analysis of Algorithms, 1997
Albers, Donald J. and Lynn A. Steen. Mathematical People. Boston: Birkhauser
, 1985, pp. 183203.
Shasha, Dennis E. and Cathy A. Lazere. Out of Their Minds: The Lives and Dis
coveries of 15 Great Computer Scientists. New York: SpringerVerlag, 1995, pp
 89101. 
--
当一个女孩儿觉得她不太容易了解那个男人的时候，她会爱他。

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 218.7.32.75]