| Richard Karp |
Article Index for Richard |
Website Links For Richard |
Information AboutRichard Karp |
|
Richard Manning Karp (born 1935 ) is a Computer Scientist , notable for research in the Theory Of Algorithms , for which he received a Turing Award in 1985 . Karp was born in Boston, Massachusetts . He attended Harvard University , where he received his Bachelor's Degree in 1955 , his Master's Degree in 1956 , and his Ph.D. in Applied Mathematics in 1959 . He then worked at IBM 's Thomas J. Watson Research Center . In 1968 , he became Professor of Computer Science, Mathematics, and Operations Research at the University Of California, Berkeley . Apart from a 4-year period as a professor at the University Of Washington , he has remained at Berkeley. Karp was also the recipient of the 2004 Benjamin Franklin Medal in Computer and Cognitive Science for his insights into Computational Complexity . His citation for the Turing Award was as follows: For his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-complete ness. Karp introduced the now standard methodology for proving problems to be NP-complete which has led to the identification of many theoretical and practical problems as being computationally difficult. In 1971 he co-developed with Jack Edmonds the Edmonds-Karp Algorithm for solving the max-flow problem on networks. In 1987 he co-developed with Michael O. Rabin the Rabin-Karp String Search Algorithm . He has made many other important discoveries in computer science and Operations Research in the area of Combinatorial Algorithm s. His major current research interests include Bioinformatics . EXTERNAL LINKS |
|
|