Jon Louis Bentley
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.
Naissance | |
---|---|
Nationalité | |
Formation | |
Activités |
A travaillé pour | |
---|---|
Directeur de thĂšse |
Donald Ford Stanat (d) |
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 [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,â
- 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
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).
- Informations biographiques dâaprĂšs lâarticle Bentley et Ottmann 1979.
- (en) « Jon Louis Bentley », sur le site du Mathematics Genealogy Project.
- Bentley 1975.
- Bentley et Ottmann 1979.
- Victor Klee, « Can the measure of be computed in less than steps? », American Mathematical Monthly, vol. 84,â , p. 284â285 (DOI 10.2307/2318871, MR 0436661)
- Bentley 1977.
- Bentley, Algorithms for Klee's rectangle problems, Report Carnegie Mellon University 1977
- (en) Request for comments no 3284.
- Bentley et McIlroy 1999.
- 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
- 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.