O diploma em Engenharia Elétrica que Mihalis Yannakakis recebeu da Universidade Técnica Nacional de Atenas em 1975 marcou o início de uma longa carreira na teoria da complexidade computacional. Nascido em 1953 em Atenas, ele posteriormente obteve um doutorado em Ciência da Computação na Universidade de Princeton, influenciando posteriormente a teoria de bancos de dados, verificação e teoria dos grafos algorítmica.
Fundamentos na complexidade
Yannakakis passou mais de duas décadas em pesquisa industrial, iniciando seu mandato nos Laboratórios Bell em 1978. Ele atuou como Diretor do Departamento de Pesquisa de Princípios de Computação lá de 1991 a 2001. Durante esse período, colaborou com Christos Papadimitriou em 1988 para definir as classes de complexidade Max-NP e Max-SNP, fornecendo uma explicação rigorosa para as limitações observadas na aproximação de problemas NP-difíceis, como o problema do caixeiro-viajante e 3SAT. Seu trabalho de 1993 com Carsten Lund esclareceu ainda mais a dificuldade inerente de calcular soluções aproximadas para problemas de minimização, como a coloração de grafos.
Inovações em bancos de dados
Suas contribuições para a teoria de bancos de dados focaram na otimização do processamento de consultas por meio do estudo de esquemas acíclicos. Ele introduziu o algoritmo de Yannakakis para consultas conjuntivas acíclicas, demonstrando que essas estruturas poderiam ser resolvidas em tempo polinomial. Além da otimização de consultas, ele investigou políticas de bloqueio, provando que a segurança do banco de dados poderia ser mantida fora das restrições rígidas do bloqueio de duas fases, utilizando a estrutura de hipergrafos dos dados e restrições de consistência de transações para evitar impasses.
Verificação e liderança acadêmica
Transicionando para a academia, Yannakakis ocupou um cargo de professor na Universidade Stanford em 2002 antes de se juntar à Universidade Columbia em 2004. Atualmente, ele atua como Professor de Ciência da Computação Percy K. e Vida L. W. Hudson. Sua pesquisa em verificação auxiliada por computador estabeleceu bases algorítmicas para testar lógica temporal de tempo linear e Diagramas de Sequência de Mensagens. Ele também desenvolveu a Verificação de Modelos Adaptativos ao lado de Alex Groce e Doron Peled, um método que refina modelos de sistemas com base nos resultados de verificação.
Vinte perguntas, oito minutos no relógio e um percentil medido contra todos os que já fizeram. Sem cadastro.
Fazer o teste de QI →Reconhecimento profissional
Yannakakis manteve uma presença editorial significativa, tendo atuado como editor-chefe do SIAM Journal on Computing entre 1998 e 2003. Sua posição acadêmica é refletida em suas associações na Academia Nacional de Ciências, na Academia Nacional de Engenharia, na Academia Americana de Artes e Ciências e na Academia Europaea. Seus prêmios incluem o Prêmio Knuth de 2005 e o Prêmio de Teoria John von Neumann de 2023.
Resumo de fatos
- Nascimento: 1953, Atenas, Grécia - Doutorado: Universidade de Princeton, 1979 - Prêmio Knuth: 2005 - Prémio de Teoria John von Neumann: 2023 - Fellow da ACM: 1998 - Cidadania: Estados Unidos; Grécia - Idiomas: Grego moderno
Perguntas dos leitores
### O que é o algoritmo de Yannakakis?
É um método usado para executar consultas conjuntivas acíclicas em sistemas de banco de dados, permitindo que sejam resolvidas em tempo polinomial.
### Com quais instituições Yannakakis esteve afiliado?
Ele trabalhou nos Laboratórios Bell, Laboratórios Avaya, Universidade Stanford e Universidade Columbia.
.jpg)
