Jon Louis Bentley

Page d’aide sur l’homonymie

Pour les articles homonymes, voir Bentley.

Page d’aide sur l’homonymie

Ne pas confondre avec Jon Bentley (TV presenter) (en)

Jon Bentley
Biographie
Naissance
ou Voir et modifier les données sur Wikidata
Long BeachVoir et modifier les données sur Wikidata
Nationalité
américaineVoir et modifier les données sur Wikidata
Formation
Activités
Informaticien, mathématicien, professeur d'universitéVoir et modifier les données sur Wikidata
Autres informations
A travaillé pour
Laboratoires Bell
Université Carnegie-MellonVoir et modifier les données sur Wikidata
Directeur de thèse
Donald Ford Stanat (d)Voir et modifier les données sur Wikidata

modifier - modifier le code - modifier WikidataDocumentation du modèle

Jon Louis Bentley, né le à Long Beach en Californie[1] 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.

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 « Divide and Conquer Algorithms for Closest Point Problems in Multidimensional Space[2] ». 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, Catherine McGeoch (en) et James B. Saxe.

Travaux

Bentley invente, en 1975, les arbres kd[3], 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[4] ; 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 problème des rectangles de Klee (en) de Victor Klee[5], article qui est resté à l’état de rapport interne[6] (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 O ( n log ⁡ ( n ) ) {\displaystyle O(n\,\log(n))} [7]. 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 RFC 3284[8],[9],[10].

En 2004, Bentley obtient le prix Excellence in Programming du périodique Dr. Dobb's Journal (en).

Publications

Articles

  • Jon Louis Bentley, Dorothea Haken et James B. Saxe, « A general method for solving divide-and-conquer recurrences », ACM SIGACT News, vol. 12, no 3,‎ , p. 36–44 (DOI 10.1145/1008861.1008865)
  • Jon Louis Bentley, « Solution to Klee's rectangle problems », Computer Science Department, Carnegie Mellon University,‎ — article non publié
  • Jon Louis Bentley, « Multidimensional binary search trees used for associative searching », Communications of the ACM, vol. 18, no 9,‎ , p. 509-517 (ISSN 0001-0782, DOI 10.1145/361002.361007)
  • Jon Louis Bentley et Thomas Ottmann, « Algorithms for Reporting and Counting Geometric Intersections », IEEE Transactions on Computers, vol. C-28, no 9,‎ , p. 643–647 (DOI 10.1109/TC.1979.1675432)
  • Jon Louis Bentley et Douglas McIlroy, « Data Compression Using Long Common Strings », dans Proceeding DCC '99 Proceedings of the Conference on Data Compression, IEEE Computer Society Washington, DC, USA, 29–31 mars 1999 (ISBN 0-7695-0096-X, lire en ligne), p. 287–295

Livres

  • Programming Pearls, ACM Press, — 2e  éd. Addison-Wesley, 1999 (ISBN 0-201-65788-0).
  • More Programming Pearls: Confessions of a Coder, Addison-Wesley, (ISBN 0-201-11889-0).
  • Writing Efficient Programs, Prentice-Hall, (ISBN 0-13-970244-X).

Notes et références

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Jon Louis Bentley » (voir la liste des auteurs).
  1. ↑ Informations biographiques d’après l’article Bentley et Ottmann 1979.
  2. ↑ (en) « Jon Louis Bentley », sur le site du Mathematics Genealogy Project.
  3. ↑ Bentley 1975.
  4. ↑ Bentley et Ottmann 1979.
  5. ↑ Victor Klee, « Can the measure of ∪ [ a i , b i ] {\displaystyle \cup [a_{i},b_{i}]} be computed in less than O ( n log ⁡ n ) {\displaystyle O(n\log n)} steps? », American Mathematical Monthly, vol. 84,‎ , p. 284–285 (DOI 10.2307/2318871, MR 0436661)
  6. ↑ Bentley 1977.
  7. ↑ Bentley, Algorithms for Klee's rectangle problems, Report Carnegie Mellon University 1977
  8. ↑ (en) Request for comments no 3284
  9. ↑ Bentley et McIlroy 1999.
  10. ↑ 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.

Liens externes

  • Notices d'autoritéVoir et modifier les données sur Wikidata :
    • VIAF
    • ISNI
    • BnF (données)
    • IdRef
    • LCCN
    • GND
    • Pays-Bas
    • Pologne
    • Israël
    • NUKAT
    • Tchéquie
    • Lettonie
    • Corée du Sud
    • WorldCat
  • Joshua Bloch (en), « Extra, extra — Read all about it : nearly all binary searches and mergesorts are broken », Google Research Blog — Bloch est un élève de Bentley.
  • icône décorative Portail de l’informatique
  • icône décorative Portail de l'informatique théorique