Richard M. Karp - Richard M. Karp

Richard Manning Karp
Karp mg 7725-b.cr2.jpg
Richard Karp no EPFL em 13 de julho de 2009
Nascer ( 1935-01-03 )3 de janeiro de 1935 (86 anos)
Boston, Massachusetts , EUA
Nacionalidade americano
Alma mater Universidade de Harvard
Conhecido por Algoritmo de Edmonds-Karp
Os 21 problemas NP-completos
de Karp Algoritmo de Hopcroft-Karp
Teorema de Karp-Lipton Teorema de
Rabin-Karp string search algoritmo
Prêmios Prêmio Turing (1985)
Prêmio de Teoria John von Neumann (1990)
Medalha Nacional de Ciência (1996)
Prêmio Harvey
Medalha Benjamin Franklin
Prêmio Kyoto
IEEE Computer Society Prêmio Charles Babbage
Carreira científica
Campos Ciência da Computação
Instituições Universidade da Califórnia, Berkeley
IBM
Tese Algumas aplicações da sintaxe lógica para programação digital de computadores  (1959)
Orientador de doutorado Anthony Oettinger
Alunos de doutorado

Richard Manning Karp (nascido em 3 de janeiro de 1935) é um cientista da computação e teórico da computação americano na Universidade da Califórnia, Berkeley . Ele é mais notável por sua pesquisa na teoria dos algoritmos , pela qual recebeu o Prêmio Turing em 1985, a Medalha Benjamin Franklin em Ciência da Computação e Cognitiva em 2004 e o Prêmio Kyoto em 2008.

Karp foi eleito membro da National Academy of Engineering (1992) por suas principais contribuições à teoria e aplicação de NP-completude, construção de algoritmos combinatórios eficientes e aplicação de métodos probabilísticos em ciência da computação.

Biografia

Nascido dos pais Abraham e Rose Karp em Boston, Massachusetts , Karp tem três irmãos mais novos: Robert, David e Carolyn. Sua família era judia e ele cresceu em um pequeno apartamento, em um bairro majoritariamente judeu de Dorchester, em Boston. Seus pais eram graduados em Harvard (sua mãe acabou obtendo seu diploma em Harvard aos 57 anos após fazer cursos noturnos), enquanto seu pai tinha ambições de ir para a faculdade de medicina depois de Harvard, mas se tornou professor de matemática porque não tinha dinheiro para pagar a faculdade de medicina. tarifas.

Ele frequentou a Harvard University , onde recebeu seu bacharelado em 1955, seu mestrado em 1956 e seu doutorado. em matemática aplicada em 1959. Ele começou a trabalhar na IBM 's Thomas J. Watson Research Center . Em 1968, ele se tornou Professor de Ciência da Computação, Matemática e Pesquisa Operacional na Universidade da Califórnia, Berkeley . Além de um período de 4 anos como professor na Universidade de Washington , ele permaneceu em Berkeley. De 1988 a 1995 e 1999 até o presente, ele também foi Cientista Pesquisador no International Computer Science Institute em Berkeley, onde atualmente lidera o Grupo de Algoritmos.

Richard Karp foi premiado com a Medalha Nacional de Ciência e recebeu o Prêmio Harvey do Technion e a Medalha Benjamin Franklin em Ciência da Computação e Cognitiva de 2004 por seus insights sobre a complexidade computacional . Em 1994, ele foi nomeado Fellow da Association for Computing Machinery . Ele foi eleito para a classe de 2002 de Fellows do Institute for Operations Research and the Management Sciences . Ele é o destinatário de vários graus honorários.

Em 2012, Karp se tornou o diretor fundador do Instituto Simons de Teoria da Computação da Universidade da Califórnia, Berkeley .

Trabalhos

Karp fez muitas descobertas importantes em ciência da computação, algoritmos combinatórios e pesquisa operacional . Seus principais interesses de pesquisa atuais incluem bioinformática .

Em 1971 ele co-desenvolveu com Jack Edmonds o algoritmo Edmonds-Karp para resolver o problema de fluxo máximo em redes, e em 1972 ele publicou um artigo marcante na teoria da complexidade, "Reducibility Between Combinatorial Problems", no qual ele provou que 21 problemas eram NP-completo .

Em 1973, ele e John Hopcroft publicaram o algoritmo Hopcroft-Karp , o método mais rápido conhecido para encontrar correspondências de cardinalidade máxima em gráficos bipartidos .

Em 1980, junto com Richard J. Lipton , Karp provou o teorema de Karp-Lipton (que prova que se o SAT pode ser resolvido por circuitos booleanos com um número polinomial de portas lógicas , então a hierarquia polinomial entra em colapso para seu segundo nível).

Em 1987, ele co-desenvolveu com Michael O. Rabin o algoritmo de pesquisa de string Rabin-Karp .

Prêmio Turing

Sua citação para o Prêmio Turing (1985) foi a seguinte:

Por suas contribuições contínuas para a teoria de algoritmos, incluindo o desenvolvimento de algoritmos eficientes para fluxo de rede e outros problemas de otimização combinatória, a identificação de computabilidade em tempo polinomial com a noção intuitiva de eficiência algorítmica e, mais notavelmente, contribuições para a teoria de NP -completude . Karp introduziu a metodologia agora padrão para provar que os problemas são NP-completos, o que levou à identificação de muitos problemas teóricos e práticos como sendo computacionalmente difíceis.

Referências

  1. ^ a b Richard M. Karp no projeto da árvore genealógica da matemática .
  2. ^ Richard Manning Karp - O PRÊMIO DE KYOTO 2008 - Tecnologia Avançada
  3. ^ a b O poder e os limites dos algoritmos Richard Manning Karp, endereço do prêmio de Kyoto, 2008
  4. ^ Fellows: Alphabetical List , Institute for Operations Research and the Management Sciences , recuperado 2019-10-09
  5. ^ "Califórnia escolhida como sede do Instituto de Computação" . The New York Times . 30 de abril de 2012 . Retirado em 23 de outubro de 2016 .
  6. ^ Richard M. Karp (1972). "Redutibility Between Combinatorial Problems" (PDF) . Em RE Miller; JW Thatcher (eds.). Complexidade de Computações Computacionais . Nova York: Plenum. pp. 85–103.
  7. ^ Associação para a maquinaria de computação. "Citação do Prêmio ACM / Richard M. Karp" . Arquivado do original em 03/07/2012 . Obtido em 2010-01-17 .

links externos

Precedido por
John McCarthy 		Benjamin Franklin Medal in Computer and Cognitive Science
2004 		Sucesso por
Aravind Joshi