Lester Randolph Ford junior

Un article de Wikipédia, l'encyclopédie libre.
Ceci est une version archivée de cette page, en date du 15 février 2020 à 19:47 et modifiée en dernier par Bot de pluie (discuter | contributions). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.
L. R. Ford, Jr.
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Décès
Voir et modifier les données sur Wikidata (à 89 ans)
Nationalité
Formation
Activité
Père
Mère
Marguerite Eleanor John (d)Voir et modifier les données sur Wikidata
Autres informations
Directeur de thèse
David Gordon Bourgin (d)Voir et modifier les données sur Wikidata

Lester Randolph Ford junior (né le à Houston et mort le ) est un mathématicien americain spécialiste des problèmes des réseaux de transport. Il est le fils du mathématicien Lester R. Ford senior[1].

Il est connu pour sa contribution au problème de flot maximum : le théorème flot-max/coupe-min sur le problème de flot maximum et l'algorithme de Ford-Fulkerson pour le résoudre paraissent dans des rapports techniques en 1954 resp. 1955 et dans un périodique public en 1956 resp. 1957[2] ,[3] ,[4].

Ford a également conçu, avec Richard Bellman et Samuel End, un algorithme pour déterminer les plus courts chemins dans un graphe dont les arcs peuvent avoir des poids négatifs. Cet algorithme s'appelle maintenant l'algorithme de Bellman-Ford.

En 1959, il publie avec Selmer M. Johnson (en) un algorithme de tri par comparaisons appelé algorithme de Ford-Johnson[5]. Vingt ans plus tard seulement, il a été prouvé que cet algorithme n'est pas optimal en ce qui concerne le nombre minimum de comparaisons à effectuer[6],[7], même s'il est le meilleur pour de petites valeurs[8].

Lester Ford et Selmer Johnson ont tous deux travaillé à la RAND Corporation[1].

Notes et références

Notes
  1. a et b (en) John J. O'Connor et Edmund F. Robertson, « Lester Randolph Ford », dans MacTutor History of Mathematics archive, université de St Andrews (lire en ligne)..
  2. Lester R. Ford Jr. et Delbert R. Fulkerson, « Maximal flow through a network », Canadian Journal of Mathematics, vol. 8,‎ , p. 399–404 (DOI 10.4153/cjm-1956-045-5, Math Reviews 0079251, lire en ligne).
  3. Lester R. Ford Jr. et Delbert R. Fulkerson, « A simple algorithm for finding maximal network flows and an application to the Hitchcock problem », Canadian Journal of Mathematics, vol. 9,‎ , p. 210-218 (DOI 10.4153/CJM-1957-024-0, Math Reviews 0093427, lire en ligne).
  4. Saul I. Gass et Arjang A. Assad, An annotated timeline of operations research: an informal history, Kluwer Academic Publishers (Springer-Verlag), coll. « International series in operations research & management science », (ISBN 978-1-4020-8112-5), « 1954 Max-flow min-cut theorem », p. 96-97.
  5. Lester R. Ford et S. M. Johnson, « A tournament problem », Am. Math. Monthly, vol. 66, no 5,‎ , p. 387-389.
  6. Donald Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, , 2e éd. (ISBN 0-201-89685-0), Section 5.3.1: « Minimum-Comparison Sorting », p. 180-197.
  7. Glenn K. Manacher, « The Ford-Johnson algorithm is not optimal », Journal of the ACM, vol. 26, no 3,‎ , p. 441-456.
  8. Marcin Peczarski, « The Ford-Johnson algorithm is still unbeaten for less than 47 elements », Information Processing Letters, vol. 101, no 3,‎ , p. 126-128 (DOI 10.1016/j.ipl.2006.09.001).
Sources de la traduction