Algorithm 版 (精华区)

发信人: Lerry (坐壮:望苗:思汉@贵族 与猫族斗争到底), 信区: Algorithm
标  题: Richard M. Karp(1985) 
发信站: 哈工大紫丁香 (2002年04月26日08:02:41 星期五), 站内信件

Richard M. Karp
Also known as: Richard Manning Karp
Born: 1935
Nationality: American
Occupation: computer scientist
Source: Notable Twentieth-Century Scientists Supplement. Gale Research, 1998
.
Table of Contents
Biographical Essay
Further Readings
Works
BIOGRAPHICAL ESSAY
An intellectual force in the development of computer science, Richard M. Kar
p has pioneered linking theoretical advances in the field to real-world prob
lems. When he received the prestigious Turing Award, Karp gave a lecture in
which he likened his interest in combinatorial search problems to "jigsaw pu
zzles, where one has to assemble the parts of a structure in a particular wa
y..." from placing and interconnecting components on an integrated circuit c
hip to "scheduling of the National Football League, and the routing of a fle
et of school buses."
Known for his comprehensive understanding of the field, as well as his ferti
le creativity, Karp has gained worldwide recognition for his inspired work i
n complexity theory and determining the inherent difficulty in solving probl
ems with computers. Dedicated to his field, Karp considers himself fortunate
 to be among the first generation of scientists that came to maturity after
the digital computer's invention. "If I had been born at an earlier time, I
don't know what career I would have pursued," Karp told contributor David Pe
techuk in a 1997 interview. "However, if not for computer science, I do know
 I would have had a much less satisfying career."
Karp was born in Boston, Massachusetts, in 1935 to Abraham Lewis and Rose Ka
rp. Karp's father was a junior high school math teacher and school principal
. On rare occasions, Karp would attend his father's classes, which fostered
his interest in math and teaching. As evidence of this early influence on hi
s life, Karp dedicated his Turing Award Lecture to his father. Karp also cre
dits his high school math teacher, Jack Dobbyn, as instilling him with confi
dence in his talent.
Karp attended the Boston Latin School and, appropriately, Latin was his seco
nd favorite subject after mathematics. By the age of 10, Karp began to demon
strate his skill in mathematics, entertaining and astounding his friends wit
h his ability to multiply four-digit numbers in his head. He was so awed by
the "power and elegance" of the formal proofs involved in plane geometry, th
at he would pretend to be sick so he could stay home and solve geometry prob
lems.
Growing up at the height of the Cold War and the beginning of the "Space Rac
e" between the Soviet Union and the United States, Karp's school years coinc
ided with a time of significant breakthroughs in and enormous support for sc
ience education and research in the United States. Admittedly overconfident
after his success at Boston Latin School, Karp quickly discovered that he ha
d to work to succeed at Harvard University. He soon learned that he had no t
aste for laboratory science and that his written communication skills were "
workmanlike."
Karp, who had no desire to pursue a career in pure mathematics, recalls the
exact moment when he realized his true vocation. A fellow student, Bill East
man, revealed to him the Hungarian Algorithm for solving the Assignment Prob
lem. He was fascinated by the elegant simplicity with which the algorithm, u
sing only addition and subtraction, "converged inexorably upon the optimal s
olution." For his Ph.D. dissertation at Harvard, Karp probed the idea that a
 directed graph can represent the flow of control in a computer program.
A Brief Interlude in Industry
After graduating in 1959, Karp went to work for the Mathematical Sciences De
partment at the IBM Thomas J. Watson Research Center located on the Lamb Est
ate, which was previously a sanitarium for wealthy alcoholics. Karp enjoyed
the informal atmosphere and lunchtime frisbee games on the estate's enormous
 lawns. However, more importantly, IBM's research division had attracted som
e of the best minds in combinatorial mathematics. Assigned to work on algori
thms for logic circuit design, Karp began his lifelong study of combinatoria
l algorithms and parallel processing.
Karp, however, felt stifled by life in corporate suburbia. He decided on a c
areer that would allow him to pursue research and to follow in his father's
footsteps as a teacher. In 1968 he joined the University of California at Be
rkeley. He considered this move the end of his scientific apprenticeship, as
 he would become a mentor to students while increasing his professional visi
bility.
The NP Solution
When Karp joined Berkeley, the university was poised to become an important
center for research in computer science. With a strong core faculty, the uni
versity began attracting outstanding graduate students. As a teacher, Karp l
ooked at each relationship with a student as unique and avoided "assigning"
thesis problems, opting instead to work with students in helping develop the
ir own interests and directions.
In 1971 Karp came across a paper by Steve Cook called "The Complexity of The
orem-Proving Procedures." Karp, who had worked in combinatorial optimization
 and was familiar with difficult combinatorial problems, like the classic "t
raveling-salesman problem," was impressed with Cook's theorem. Excited by th
e belief that he had discovered an area of work that could greatly influence
 computer science, he began developing a new class of computing problems. Pr
imarily, Karp was concerned with problems in computer science for efficientl
y routing and scheduling. These problems had many real-world applications, r
anging from the routing of electronic "traffic" over the countless wires nee
ded in microprocessing to scheduling classes and the traveling salesman prob
lem of finding the shortest route for a salesperson to use while touring cit
ies.
In 1972 Karp received international recognition for his work in demonstratin
g the existence of an entirely new class of difficult theoretical computing
problems called NP-completeness. Essentially, the NP-complete theory divides
 most problems in computer science into two groups, problems that can be sol
ved efficiently by a computer and problems that probably cannot. Karp and co
lleagues had discovered that many of the most commonly studied combinatorial
 problems are disguised versions of a single underlying problem and, thus, a
re all of essentially the same computational complexity. The theory revoluti
onized computer science and still serves as the fundamental basis of scienti
fic thought on computers' capabilities and limitations. Interesting, after h
is 1972 paper on the subject, Karp did little work on NP-completeness proofs
. He says he moved on to leave the problems in the hands of "virtuosi of the
 subject."
Turns to Computational Molecular Biology
After spending 27 years at Berkeley, Karp retired and then took a faculty po
sition at the University of Washington. The university had a rapidly growing
 research environment based on the human genome project, in which scientists
 from around the world are working on mapping the entire human genome. Karp
was an avid reader of general literature concerning molecular biology and ge
netics and believed that his expertise in algorithms could prove valuable he
lp in properly ordering the three billion symbols in the human genome.
Karp's work at the University of Washington has focused on strategies for se
quencing the human genome, the physical mapping of large DNA molecules, the
classification of tumors on the basis of gene expression data, and other com
binatorial problems arising in molecular biology. "We want to take the human
 out of the loop as much as possible," said Karp in a New York Times article
 on DNA sequencing efforts at the University of Washington. Pointing out tha
t running sequencing experiments is "deadly boring," Karp has set out to aut
omate the process (for example, designing robotic systems to do most of the
work) and developing algorithms so computers can analyze the data.
"Many biologists consider the acquisition of sequences to be boring," said K
arp in the Times article. "But from a computer science point of view, these
are first-rate and challenging algorithmic questions."
Karp, who is married and has a son, feels fortunate in having found a profes
sion that was just beginning to flourish and which suited his interests perf
ectly. Besides his work in computer science research, he is most proud of hi
s career as a teacher. Having supervised 35 Ph.D. candidates at Berkeley, Ka
rp developed a definitive philosophy on teaching. In addition to his emphasi
s on preparation and structuring material to provide students with a "road m
ap" of study, he developed an in-class code that included relaxing before th
e beginning of class, always making eye contact with his students, and being
 willing to share his own experiences and opinions with students while avoid
ing "ego trips."
For his groundbreaking efforts in computer science, Karp has received many a
wards, including the Turing Award, computer science's most prestigious honor
, and the National Medal of Science (1997). [Karp] "has the most respect of
any computer scientists I know," said Tandy Warnow, a computer scientist for
 the University of Pennsylvania, in the New York Times. "He's helping to cha
nge the ways we think about what we are doing as computer scientists."
WORKS
"Reducibility among Combinatorial Problems." Complexity of Computer Computat
ions. New York, Plenum Press, 1972.
"Combinatorics, Complexity and Randomness" (Turing Award Lecture). Communica
tions of the ACM 6 (1986): 35-48.
"Probablistic Analysis of Partitioning Algorithms for the Traveling-Salesman
 Problem in the Plane." Mathematics of Operations Research 2 (1977): 209-244
.
FURTHER READINGS
Kolata, G. "Biology's Big Project Turns Into Challenge for Computer Experts.
" The New York Times (June 11, 1996): B5, B10. 
--
当一个女孩儿觉得她不太容易了解那个男人的时候，她会爱他。

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