Miklós Ajtai
| Miklós Ajtai | |
|---|---|
| Nascimento | 2 de julho de 1946 (77 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 |
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[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]
- 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[editar | editar código-fonte]
- «Página pessoal» (em inglês)
