Miklós Ajtai
Miklós Ajtai | |
---|---|
Nascimento | 2 de julho de 1946 (78 anos) Budapeste |
Residência | San José |
Nacionalidade | húngaro |
Cidadania | Hungria |
Progenitores |
|
Alma mater | Academia de Ciências da Hungria |
Ocupação | matemático, cientista de computação, engenheiro |
Prêmios | Prêmio Knuth (2003) |
Empregador(a) | IBM, Universidade McGill, Universidade da Califórnia em San Diego, Instituto de Tecnologia de Massachusetts |
Instituições | IBM Almaden Research Center |
Campo(s) | ciência da computação, teoria da complexidade |
[edite no Wikidata] |
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 algoritmo 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
Ajtai graduou-se em 1976 na Academia de Ciências da Hungria,[1] da qual é desde 1995 um membro externo.
Resultados selecionados
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
- Ajtai, M. (1979), «Isomorphism and higher order equivalence», Annals of Mathematical Logic, 16 (3): 181–203, doi:10.1016/0003-4843(79)90001-9 .
- 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
- ↑ Magyar Tudományos Akadémia, Almanach, 1986, Budapest.
Ligações externas
- «Página pessoal» (em inglês)
![]() | Este artigo sobre um(a) cientista da computação é um esboço. Você pode ajudar a Wikipédia expandindo-o.
|