Miklós Ajtai

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Miklós Ajtai
Nascimento 2 de julho de 1946 (70 anos)
Budapeste
Nacionalidade Hungria Húngaro
Alma mater Academia de Ciências da Hungria

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.