Abrir menu principal

BiografiaEditar

Filho de Abraham e Rose Karp, nasceu em Boston, Massachusetts, Richard tem três irmãos mais novos: Robert, David, e Carolyn. Ele estudou na Universidade de Harvard, onde recebeu o seu diploma de Bacharel em 1955, o seu diploma de Mestre em 1956, e o seu Ph.D. em matemática aplicada em 1959.

Ele começou a trabalhar no Thomas J. Watson Research Center da IBM. Em 1968, se tornou Professor de Ciência da Computação, Matemática, e Pesquisa de Operações na Universidade da California, Berkeley. Além dos 4 anos como professor na Universidade de Washington, ele permaneceu em Berkeley. De 1988 a 1995 e de 1999 até os dias de hoje ele também tem sido Pesquisador no International Computer Science Institute em Berkeley, onde ele atualmente lidera o Algorithms Group.

Richard Karp foi premiado com a Medalha Nacional de Ciências, e foi o beneficiário do Prêmio Harvey da Technion e da Medalha Benjamin Franklin em Computação e Ciência Cognitiva em 2004 por suas percepções na complexidade computacional. Em 1994, ele foi introduzido como um fellow da Association for Computing Machinery. Ele é o beneficiário de vários títulos honoríficos.

TrabalhoEditar

Ele fez várias outras descobertas importantes em ciências da computação e em pesquisa operacional na área de otimização combinatória. Seu maior interesse atual de pesquisa envolve bioinformática.

Em 1971, ele desenvolveu com Jack Edmonds o Edmonds–Karp algorithm para resolver problemas de máximo-fluxo nas redes, e em 1972, ele publicou um artigo que envolvia a teoria da complexidade, "Reducibility Among Combinatorial Problems", no qual ele provou 21 Problems to be NP-complete.[3]

Em 1973, ele e John Hopcroft publicaram o Hopcroft–Karp algorithm, que ainda é o método mais rápido para encontrar as correspondências de cardinalidade máxima em grafos bipartidos.

Em 1980, junto com Richard Lipton, Karp provou o teorema de Karp-Lipton (o qual 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 desmorona ao seu segundo nível).

Em 1987, ele desenvolveu com Michael Rabin o Rabin-Karp string search algorithm.

Prêmio TuringEditar

A citação dele[4] para o Turing Award foi como se segue:

Por suas contribuições contínuas para a teoria dos algoritmos incluindo o desenvolvimento de algoritmos eficientes para problemas de fluxo de rede e outros problemas de otimização combinatória, a identificação da computabilidade em tempo-polinomial com a noção intuitiva da eficiência do algoritmo, e, mais notável, contribuições para a teoria da NP-completude. Karp introduziu a metodologia padrão atual para provar que problemas são NP-completos o que levou à identificação de muitos outros problemas práticos e teóricos como sendo de dificuldade computacional.

Referências

  1. Richard Karp (em inglês) no Mathematics Genealogy Project.
  2. «Cópia arquivada». Consultado em 20 de abril de 2013. Arquivado do original em 14 de março de 2010 
  3. Richard M. Karp (1972). «Reducibility Among Combinatorial Problems» (PDF). In: R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. [S.l.]: New York: Plenum. pp. 85–103 
  4. Association for Computing Machinery. «ACM Award Citation/Richard M. Karp». Consultado em 17 de janeiro de 2010. Arquivado do original em 3 de julho de 2012 

Ligações externasEditar

 
O Commons possui uma categoria contendo imagens e outros ficheiros sobre Richard Karp
  Este artigo sobre um(a) cientista da computação é um esboço. Você pode ajudar a Wikipédia expandindo-o.