Jon Louis Bentley
Modèle:Voir homonymes Modèle:Confusion Modèle:Infobox Biographie2
Jon Louis Bentley, né le Modèle:Date de naissance à Long Beach en CalifornieModèle:Note est un informaticien américain. Il est connu pour ses contributions au développement d’algorithmes et pour ses livres d’algorithmique, issus de sa rubrique Programming Pearls du périodique [[Communications of the ACM|Communications of the Modèle:Abréviation]].
Carrière
Bentley étudie les mathématiques à l’université Stanford et obtient un B.Sc. en 1974, puis en 1976 un M.Sc. et la même année un Ph.D. à l’université de Caroline du Nord à Chapel Hill, sous la direction de Donald Stanat avec une thèse intitulée Modèle:Citation étrangère. Il travaille comme research intern au Palo Alto Research Center en 1973–1974 ; il est visiting scholar au Stanford Linear Accelerator Center durant l'été 1975. De 1975 à 1976 il est boursier gradué de la National Science Foundation.
En 1974, il obtient le deuxième prix du concours d'essais étudiants organisé par l'ACM. En 1977, il est professeur assistant à l’université Carnegie-Mellon ; ensuite il travaille aux Laboratoires Bell. Il supervise les thèses de Charles E. Leiserson, Modèle:Lien et James B. Saxe.
Travaux
Bentley invente, en 1975, les arbres kd[1], une structure de données pour des arbres de recherche multidimensionnels. Avec Thomas Ottmann il publie en 1979 l’algorithme qui porte leurs noms et qui détermine les points d’intersection d’un ensemble de segments de droite[2] ; c'est un des premiers algorithmes en géométrie algorithmique. En 1977, il donne un algorithme pour la généralisation, à deux dimensions, du Modèle:Lien de Victor Klee[3], article qui est resté à l’état de rapport interne[4] (il s’agit de trouver l’aire d’un ensemble de n rectangles ; Klee pose la question pour un ensemble de n segments de droite, et les deux donnent des algorithmes en temps [5]. En 1999, Bentley publie, avec Douglas McIlroy, l’algorithme VCDIFF, un format et un algorithme pour le codage différentiel, décrit dans la norme Modèle:RFCModèle:,[6]Modèle:,[7].
En 2004, Bentley obtient le prix Excellence in Programming du périodique Modèle:Lien.
Publications
Articles
- Modèle:Article
- Modèle:Article — article non publié
- Modèle:Article
- Modèle:Article
- Modèle:Chapitre
Livres
Notes et références
Modèle:Traduction/Référence Modèle:Références
Liens externes
- Modèle:Autorité
- Modèle:Lien, « Extra, extra — Read all about it : nearly all binary searches and mergesorts are broken », Google Research Blog — Bloch est un élève de Bentley.
- ↑ Modèle:Harvsp.
- ↑ Modèle:Harvsp.
- ↑ Modèle:Article
- ↑ Modèle:Harvsp.
- ↑ Bentley, Algorithms for Klee's rectangle problems, Report Carnegie Mellon University 1977
- ↑ Modèle:Harvsp.
- ↑ Le codage VCDIFF est utilisé dans les algorithmes de codage différentiel en HTTP et employé par exemple pour la compression de données HTTP partagées de Google dans les navigateurs Chrome.