Miklós Ajtai

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Miklós Ajtai
Ciência da computação, teoria da complexidade
Nacionalidade Hungria Húngaro
Residência  Estados Unidos
Nascimento 2 de julho de 1946 (67 anos)
Local Budapeste
Atividade
Campo(s) Ciência da computação, teoria da complexidade
Instituições IBM Almaden Research Center
Alma mater Academia de Ciências da Hungria
Prêmio(s) Prêmio Knuth (2003)

Miklós Ajtai (Budapeste, 2 de julho de 1946) é um cientista da computação húngaro.

Trabalha no IBM Almaden Research Center, Estados Unidos.

Em 2003 recebeu o Prêmio Knuth, por seus diversos trabalhos em ciência da computação, incluindo um algorítmo clássico de classificação de rede (desenvolvido juntamente com János Komlós e Endre Szemerédi), ínfimo exponencial, implicações tempo-espaço superlineares para ramificação de programas, o outros resultados.

Vida[editar | editar código-fonte]

Ajtai graduou-se em 1976 na Academia de Ciências da Hungria,[1] da qual é desde 1995 um membro externo.

Resultados selecionados[editar | editar código-fonte]

Um dos resultados de Ajtai estabelece que o comprimento das provas em lógica proposicional do princípio da casa dos pombos para n itens cresce mais rápido que qualquer polinômio em n. Também provou a afirmação que "quaisquer duas estruturas de interpretação contáveis que são equivalentes de segunda ordem são também isomórficas" é consistente com e independente dos axiomas de Zermelo-Fraenkel. Ajtai e Endre Szemerédi provaram o teorema dos vértices (corners theorem), um passo fundamental para generalizações dimensionais superiores do teorema de Szemerédi. Juntamente com János Komlós e Endre Szemerédi provou o limite superior ct2/log t do número de Ramsey R(3,t). O correspondente limite inferior foi provado por Jeong Han Kim somente em 1995, o que lhe valeu um Prêmio Fulkerson. Com Václav Chvátal, M. M. Newborn e Endre Szemerédi, Ajtai provou que um grafo planar com n vértices e m arestas, sendo m > 4n, tem no mínimo m3 / 100n2 crossings.

Publicações selecionadas[editar | editar código-fonte]

  1. Ajtai, M. (1979), "Isomorphism and higher order equivalence", Annals of Mathematical Logic 16 (3): 181–203, doi:10.1016/0003-4843(79)90001-9 .
  2. Ajtai, M.; Komlós, J.; Szemerédi, E. (1982), "Largest random component of a k-cube", Combinatorica 2 (1): 1–7, doi:10.1007/BF02579276 .

Referências

  1. Magyar Tudományos Akadémia, Almanach, 1986, Budapest.

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


Ícone de esboço Este artigo sobre um(a) cientista da computação é um esboço. Você pode ajudar a Wikipédia expandindo-o.