Miklós Ajtai

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant une personnalité image illustrant hongrois
Cet article est une ébauche concernant une personnalité hongroise.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Miklós Ajtai (2 juillet 1946, Budapest, Hongrie - ) est un chercheur en informatique au centre de recherches IBM d'Almaden. En 2003, il reçoit le prix Knuth pour ses nombreuses contributions au domaine, notamment un algorithme de tri par réseau, développé avec János Komlós (en) et Endre Szemerédi.

Biographie[modifier | modifier le code]

Miklós Ajtai a reçu son PhD en 1976, à l'université Loránd Eötvös, sous la direction de Andras Hajnal (en)[1].

Travaux[modifier | modifier le code]

Miklós Ajtai a surtout travaillé selon une approche combinatoire, notamment par théorie de Ramsey. En théorie de la complexité, il a prouvé, par la logique, que la fonction parité (en) ne pouvait pas être calculée dans AC0[2].


Il a aussi copublié avec Paul Erdős (donc son nombre d'Erdős est 1).

Quelques publications[modifier | modifier le code]

Prix[modifier | modifier le code]

Miklós Ajtai a gagné le prix Donald E. Knuth en 2003[3].

Notes et références[modifier | modifier le code]

  1. (en) Miklós Ajtai sur le site du Mathematics Genealogy Project
  2. Miklós Ajtai, « ∑ 1 1-formulae on finite structures », Annals of pure and applied logic, vol. 24, no 1,‎ , p. 1-48
  3. (en) « Knuth Prize », sur SIGACT (consulté le 2 juillet 2014)

Liens externes[modifier | modifier le code]

(en) Page personnelle