Richard Karp

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Richard Karp
Ciência da computação
Nacionalidade Estados Unidos Estadunidense
Nascimento 3 de janeiro de 1935 (79 anos)
Local Boston
Atividade
Campo(s) Ciência da computação
Instituições Universidade da Califórnia em Berkeley, IBM
Alma mater Universidade Harvard
Orientador(es) Anthony Oettinger[1]
Orientado(s) Narendra Karmarkar, Michael Luby, Rajeev Motwani, Noam Nisan, Barbara Simons
Conhecido(a) por Algoritmo de Edmonds-Karp
Prêmio(s) Prêmio Fulkerson (1979), Prêmio Turing (1985), John von Neumann Lecture (1987), Medalha Nacional de Ciências (1996), Prêmio Harvey (1998), Medalha Benjamin Franklin (2004), Prêmio Kyoto (2008), Prêmio Dickson de Ciências (2008)

Richard Manning Karp (Boston, 3 de janeiro de 1935) é um cientista da computação e teórico computacional da Universidade da California, Berkeley, reconhecido pela sua pesquisa sobre teoria dos algoritmos, pelo qual recebeu um Prêmio Turing em 1985, Medalha Benjamin Franklin em Computação e Ciência Cognitiva em 2004, e o Prêmio Kyoto em 2008.[2]

Biografia[editar | editar código-fonte]

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.

Trabalho[editar | editar código-fonte]

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 Turing[editar | editar código-fonte]

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 Mathematics Genealogy Project.
  2. http://www.inamori-f.or.jp/laureates/k24_a_richard/prs_e.html
  3. Richard M. Karp. In: R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. [S.l.]: New York: Plenum, 1972. 85–103 pp.
  4. Association for Computing Machinery. ACM Award Citation/Richard M. Karp. Visitado em 2010-01-17.

Ligações externas[editar | editar código-fonte]

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