| 词条 | Richard M. Karp |
| 释义 |
| name = Richard Manning Karp | image = Karp mg 7725-b.cr2.jpg | image_size = | caption = Richard Karp at the EPFL on 13th of July 2009 | birth_date = {{Birth date and age|1935|1|3|mf=yes}} | birth_place = Boston, Massachusetts | death_date = | death_place = | residence = | citizenship = | nationality = American | ethnicity = | field = Computer Science | work_institution = University of California, Berkeley IBM | alma_mater = Harvard University | doctoral_advisor = Anthony Oettinger[1] | doctoral_students = {{plainlist|1=
}} | known_for = Edmonds–Karp algorithm Karp's 21 NP-complete problems Hopcroft–Karp algorithm Karp–Lipton theorem Rabin–Karp string search algorithm | thesis_title = Some Applications of Logical Syntax to Digital Computer Programming | thesis_year = 1959 | author_abbreviation_bot = | author_abbreviation_zoo = | prizes = Turing Award (1985) John von Neumann Theory Prize (1990) National Medal of Science (1996) Harvey Prize Benjamin Franklin Medal Kyoto Prize IEEE Computer Society Charles Babbage Award | religion = | footnotes = }}Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.[2] BiographyBorn to parents Abraham and Rose Karp in Boston, Massachusetts, Karp has three younger siblings: Robert, David, and Carolyn. His family was Jewish,[3] and he grew up in a small apartment, in a then mostly Jewish neighborhood of Dorchester in Boston. Both his parents were Harvard graduates (his mother eventually obtaining her Harvard degree at age 57 after taking evening courses), while his father had had ambitions to go to medical school after Harvard, but became a mathematics teacher as he could not afford the medical school fees.[4] 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 started working 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. From 1988 to 1995 and 1999 to the present he has also been a Research Scientist at the International Computer Science Institute in Berkeley, where he currently leads the Algorithms Group. Richard Karp was awarded the National Medal of Science, and was the recipient of the Harvey Prize of the Technion and the 2004 Benjamin Franklin Medal in Computer and Cognitive Science for his insights into computational complexity. In 1994 he was inducted as a Fellow of the Association for Computing Machinery. He is the recipient of several honorary degrees. In 2012, Karp became the founding director of the Simons Institute for the Theory of Computing at the University of California, Berkeley.[5] WorkKarp has made many important discoveries in computer science, combinatorial algorithms, and operations research. His major current research interests include bioinformatics. In 1971 he co-developed with Jack Edmonds the Edmonds–Karp algorithm for solving the maximum flow problem on networks, and in 1972 he published a landmark paper in complexity theory, "Reducibility Among Combinatorial Problems", in which he proved 21 problems to be NP-complete.[6] In 1973 he and John Hopcroft published the Hopcroft–Karp algorithm, the fastest known method for finding maximum cardinality matchings in bipartite graphs. In 1980, along with Richard J. Lipton, Karp proved the Karp-Lipton theorem (which proves that if SAT can be solved by Boolean circuits with a polynomial number of logic gates, then the polynomial hierarchy collapses to its second level). In 1987 he co-developed with Michael O. Rabin the Rabin-Karp string search algorithm. Turing AwardHis citation[7] for the (1985) 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-completeness. 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. References1. ^1 {{MathGenealogy|id=25275}}. 2. ^[https://web.archive.org/web/20100314142146/http://www.inamori-f.or.jp/laureates/k24_a_richard/prs_e.html Richard Manning Karp - THE 2008 KYOTO PRIZE - Advanced Technology] 3. ^[https://www.kyotoprize.org/wp/wp-content/uploads/2016/02/24kA_lct_EN.pdf The Power and Limits of Algorithms] Richard Manning Karp, Kyoto Prize Address, 2008 4. ^[https://www.kyotoprize.org/wp/wp-content/uploads/2016/02/24kA_lct_EN.pdf The Power and Limits of Algorithms] Richard Manning Karp, Kyoto Prize Address, 2008 5. ^{{cite web|url=https://www.nytimes.com/2012/05/01/science/simons-foundation-chooses-uc-berkeley-for-computing-center.html?_r=0|title=California Chosen as Home for Computing Institute|date=30 April 2012|publisher=The New York Times|accessdate=23 October 2016}} 6. ^{{cite book | author = Richard M. Karp | chapter = Reducibility Among Combinatorial Problems | chapter-url = http://www.cs.berkeley.edu/~luca/cs172/karp.pdf | title = Complexity of Computer Computations | editor = R. E. Miller and J. W. Thatcher (editors) | publisher = New York: Plenum | pages = 85–103 | year = 1972}} 7. ^{{cite web |url=http://awards.acm.org/citation.cfm?id=3256708&srt=all&aw=140&ao=AMTURING&yr=1985 |title=ACM Award Citation/Richard M. Karp |author=Association for Computing Machinery |publisher= |accessdate=2010-01-17 |archive-url=https://wayback.archive-it.org/all/20120703015825/http://amturing.acm.org/award_winners/karp_3256708.cfm |archive-date=2012-07-03 |dead-url=yes |df= }} External links{{Commons category|Richard Karp}}
before=John McCarthy | title=Benjamin Franklin Medal in Computer and Cognitive Science | after=Aravind Joshi | years=2004}}{{s-end}}{{EATCS Award laureates}}{{Turing award}}{{Winners of the National Medal of Science|math-stat-comp}}{{John von Neumann Lecturers}}{{John von Neumann Theory Prize recipients}}{{Authority control}}{{DEFAULTSORT:Karp, Richard}} 26 : American computer scientists|American operations researchers|1935 births|Living people|Theoretical computer scientists|Fellows of the Association for Computing Machinery|Fellows of the Society for Industrial and Applied Mathematics|Kyoto laureates in Advanced Technology|Members of the United States National Academy of Engineering|Members of the United States National Academy of Sciences|John von Neumann Theory Prize winners|Jewish scientists|Jewish American scientists|National Medal of Science laureates|Turing Award laureates|University of California, Berkeley College of Engineering faculty|Members of the French Academy of Sciences|Harvard University alumni|People from Boston|20th-century American engineers|21st-century American engineers|20th-century American mathematicians|21st-century American mathematicians|20th-century American scientists|21st-century American scientists|Harvard School of Engineering and Applied Sciences alumni |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。