Richard Karp
| Richard Karp | |
|---|---|
 | |
| Algoritmo de Edmonds-Karp | |
| Nascimento | 3 de janeiro de 1935 (89 anos) Boston |
| Nacionalidade | estadunidense |
| Cidadania | Estados Unidos |
| Alma mater | Universidade Harvard |
| Ocupação | matemático, cientista de computação, professor universitário |
| Distinções | Prêmio Fulkerson (1979), Prêmio Turing (1985), John von Neumann Lecture (1987), Medalha Nacional de Ciências (1996), Prêmio Harvey (1998), Prêmio EATCS (2000), Medalha Benjamin Franklin (2004), Prêmio Kyoto (2008), Prêmio Dickson de Ciências (2008) |
| Empregador(a) | Universidade da Califórnia em Berkeley, Universidade de Washington |
| Orientador(a)(es/s) | Anthony Oettinger[1] |
| Orientado(a)(s) | Narendra Karmarkar, Michael Luby, Rajeev Motwani, Noam Nisan, Barbara Simons |
| Instituições | Universidade da Califórnia em Berkeley, IBM |
| Campo(s) | ciência da computação |
| Obras destacadas | A simple algorithm for finding frequent elements in streams and bags |
| Página oficial | |
| http://www.eecs.berkeley.edu/Faculty/Homepages/karp.html | |
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
- ↑ Richard Karp (em inglês) no Mathematics Genealogy Project.
- ↑ «Cópia arquivada». Consultado em 20 de abril de 2013. Arquivado do original em 14 de março de 2010
- ↑ 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
- ↑ 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 externas
[editar | editar código-fonte]
- Nascidos em 1935
- Prêmio Turing
- Medalha Nacional de Ciências
- Pioneiros da computação
- Membros da Academia Nacional de Ciências dos Estados Unidos
- Membros da Academia Nacional de Engenharia dos Estados Unidos
- Membros da Academia de Ciências da França
- Fellows da ACM
- Membros da SIAM
- Professores da Universidade da Califórnia em Berkeley
- Matemáticos dos Estados Unidos
- Cientistas da computação dos Estados Unidos
- Alunos da Universidade Harvard
- Naturais de Boston