Wikipédia

Edgar Gilbert

mathématicien américain
Page d’aide sur l’homonymie

Pour les articles homonymes, voir Gilbert.

Edgar Nelson Gilbert, né le à Woodhaven dans l'État de New York et mort le (à 89 ans) à Basking Ridge (New Jersey)[1], est un mathématicien américain, spécialiste en théorie des codes, pendant longtemps chercheur aux Laboratoires Bell. On lui doit notamment la borne de Gilbert-Varshamov en théorie des codes, le modèle de Gilbert–Elliott (en) pour les erreurs en rafale en transmission de données, et le modèle d'Erdős-Rényi (en) des graphes aléatoires.

Edgar Gilbert
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Décès
Voir et modifier les données sur Wikidata (à 89 ans)
Basking RidgeVoir et modifier les données sur Wikidata
Nationalité
Formation
Activités
Autres informations
A travaillé pour
Directeur de thèse

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

Biographie

modifier

Edgar N. Gilbert fait des études de undergraduate en physique au Queens College de l'université de la Ville de New York, il obtient le diplôme de graduate en 1943. Il enseigne brièvement les mathématiques à l'université de l'Illinois à Urbana-Champaign et ensuite rejoint le Radiation Laboratory au Massachusetts Institute of Technology, où il participe à la conception d'antennes radar de 1944 à 1946.

Il achève un doctorat Ph. D. en physique au MIT en 1948, sous la supervision de Norman Levinson, avec une thèse intitulée Asymptotic Solution of Relaxation Oscillation Problems et entre aux Laboratoires Bell où il reste pour le restant de sa carrière. Il prend sa retraite en 1996[2],[3].

Recherche

modifier

Théorie des codes

modifier

La borne de Gilbert-Varshamov démontrée indépendamment en 1952 par Gilbert et en 1957 par Rom Varshamov[4] est un théorème qui garantit l'existence d'un code correcteur d'erreurs qui a un taux de transmission élevé en fonction de la longueur du code, de la taille de l'alphabet, et de la distance de Hamming entre mots du code (un paramètre qui détermine le nombre d'erreurs qui peuvent être corrigées). L'idée principale est que dans un code maximal (un code auquel on ne peut ajouter de mot supplémentaire), les boules de Hamming de rayon donné doivent couvrir l'espace de codage tout entier, et donc que le nombre de mots de code doit être au moins égal au volume total divisé par le volume d'une boule[5]. Pendant 30 ans, et jusqu'à la découverte des codes de Goppa en 1982, les codes construits de cette manière étaient les meilleurs code connus[6].

Le modèle de Gilbert–Elliott (en) développé par Gilbert en 1960 et E. O. Elliott en 1963[7] est un modèle pour l'analyse des canaux de transmission où les erreurs se produisent en rafale. Il suppose que le canal eut être dans l'un de deux états, avec des taux d'erreurs différents, et que dans chaque état les erreurs se produisent indépendamment les uns des autres, et que le passage entre les états est régi par une chaîne de Markov. Ce modèle est « très utile et fréquemment employé » dans l'analyse de systèmes de communication modernes comme les liaisons aux téléphones portables[8].

Théorie des probabilités

modifier

Le modèle d'Erdős-Rényi (en) est un concept central de la théorie des graphes aléatoires. Dans ce modèle, les arcs sont choisis au hasard pour un ensemble fixe de   sommets. Il a été introduit sous deux formes, en 1959, par Gilbert, Paul Erdős et Alfréd Rényi[9]. Dans la forme   de Gilbert, chaque arc est choisi de figure ou non dans le graphe avec une probabilité  , indépendamment des autres arcs. Ainsi, le nombre moyen d'arcs est  , et le nombre effectif d'arcs peut varier, et tout graphe a une probabilité non nulle d'être choisis. Dans le modèle   introduit par Erdős et Rényi au contraire, le graphe est choisi uniformément au hasard parmi tous les graphes à   arcs ; le nombre d'arcs est donc fixe, mais les arcs ne sont pas indépendants les uns des autres puisque la présence d'un arc dans une position est corrélée négativement à la présence d'un autre arc dans une position différente. Même si ces deux modèles révèlent des propriétés similaires, le modèle   est souvent plus facile à employer à cause de l'indépendance de ses arcs[10]. L'algorithme le plus rapide pour engendrer un graphe selon le modèle   est dû à Nobari et al.[11].

Le modèle de Gilbert–Shannon–Reeds (en) de mélange de cartes à jouer est un modèle mathématique développé en 1955 par Gilbert et Claude Shannon[12] et indépendamment, dans un travail inédit, par Jim Reeds en 1981. C'est une distribution de probabilité sur un ensemble de   objets qui, d'après des expériences menés par Persi Diaconis, modélise précisément les mélanges de cartes produits par un humain[13]. Dans ce modèle, un paquet de cartes est séparé en deux en un point choisi au hasard selon une loi binomiale, et les deux parts sont fusionnées selon un ordre choisi aléatoirement et uniformément parmi les fusions possibles. De manière équivalent, c'est l'inverse de la permutation obtenue en choisissant indépendamment et au hasard, pour chaque carte, dans lequel de deux paquets elle doit être mise, tout en conservant l'ordre original des cartes dans chaque paquet, et en empilant l'un des paquets sur l'autre à la fin.

Les pavages de Gilbert (en) sont un modèle mathématique de rupture introduit par Gilbert en 1967[14]. Dans ce modèle, la rupture commence en un ensemble de points au hasard, avec des orientations au hasard, choisis selon un processus de Poisson, puis grandissent à vitesse constante jusqu'à rencontrer une rupture précédente[15].

Autres contributions

modifier

Gilbert a publié un travail important sur les arbres de Steiner en 1968. Il formule le problème de façon à l'unifier avec le problème de flot maximum[16]. Dans le modèle de Gilbert, on se donne un graphe de flot dans lequel chaque arc est doté d'un coût et d'une capacité, et une matrice qui contient les valeurs de flot entre couples de sommets terminaux; le but est de trouver un sous-graphe du réseau dont les capacités sont suffisantes pour admettre un flot avec les mêmes valeurs de flot entre sommets terminaux. Dans le cas où toutes les valeurs de flot sont égales, ceci se réduit au problème classique des arbres de Steiner[17].

Gilbert a découvert les tableaux de Costas indépendamment et la même année que John P. Costas (en)[18], et est aussi connu pour son travail avec John Riordan sur le dénombrement des necklaces en combinatoire[19].

Nombre d'Erdős

modifier

Le nombre d'Erdős de Gilbert est 2 grâce à un travail commun avec Fan Chung (coauteur d'Erdős), Ron Graham (en), et Jacobus van Lint sur les partitions d'un rectangle en rectangles plus petits[20].

Notes et références

modifier
  1. ↑ (en) « Edgar Nelson Gilber Obituary »
  2. ↑ Biographie des auteurs dans S. C. Borst, Edward. G. Coffman, Edgar N. Gilbert, P. A. Whiting et Peter M. Winkler, « Time-slot allocation in wireless TDMA », dans E. Gelenbe (éditeur), System Performance Evaluation: Methodologies and Applications, Boca Raton (Floride), CRC Press, (ISBN 978-0-8493-2357-7, présentation en ligne), p. 203–214
  3. ↑ (en) « Edgar Nelson Gilbert », sur le site du Mathematics Genealogy Project.
  4. ↑ Edgar N. Gilbert, « A comparison of signalling alphabets », Bell System Technical Journal, vol. 31,‎ , p. 504–522; R. R. Varshamov, « Estimate of the number of signals in error correcting codes », Dokl. Acad. Nauk SSSR, vol. 117,‎ , p. 739–741.
  5. ↑ Todd K. Moon, « The Gilbert–Varshamov Bound », dans Error correction Coding: Mathematical Methods and Algorithms, John Wiley and Sons, (ISBN 978-0-471-64800-0), p. 409–410.
  6. ↑ « The Gilbert–Varshamov Bound revisited », dans William C. Huffman et Vera Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, , 646 p. (ISBN 978-0-521-78280-7, lire en ligne), p. 541.
  7. ↑ Edgar N. Gilbert, « Capacity of a burst-noise channel », Bell System Technical Journal, vol. 39,‎ , p. 1253–1265 (lire en ligne) et E. O. Elliott, « Estimates of error rates for codes on burst-noise channels », Bell System Technical Journal, vol. 42,‎ , p. 1977–1997
  8. ↑ Stefan Petrausch, Wolfgang Sörgel et André Kaup, « Serially connected channels: Capacity and video streaming application scenario for separate and joint channel coding », dans Margret Schneider (éditrice), 5th International ITG Conference on Source and Channel Coding (SCC): January 14–16, 2004, Erlangen : Conference Record, (ISBN 978-3-8007-2802-2), p. 271–278.
  9. ↑ Edgar N. Gilbert, « Random graphs », Annals of Mathematical Statistics, vol. 30,‎ , p. 1141–1144 (DOI 10.1214/aoms/1177706098) et Paul Erdős et Alfréd Rényi, « On random graphs I », Publicationes Mathematicae, vol. 6,‎ , p. 290–297 (lire en ligne).
  10. ↑ Duncan J. Watts, Small Worlds : The Dynamics of Networks Between Order and Randomness, Princeton University Press, coll. « Princeton Studies in Complexity », , 262 p. (ISBN 978-0-691-11704-1, lire en ligne), p. 36–37.
  11. ↑ Sadegh Nobari, Xuesong Lu, Panagiotis Karras et Stéphane Bressan, « Fast random graph generation », dans Proceedings 14th International Conference on Extending Database Technology, Uppsala, Suède, ACM, (ISBN 978-1-4503-0528-0, DOI 10.1145/1951365.1951406, lire en ligne), p. 331-342.
  12. ↑ Edgar N. Gilbert, « Theory of Shuffling », Technical Memorandum, Bell Laboratories,‎ , d'après la citation par (Bayer et Diaconis 1992).
  13. ↑ Dave Bayer et Persi Diaconis, « Tracking the dovetail shuffle to its lair », Annals of Applied Probability, vol. 2, no 2,‎ , p. 294–313 (JSTOR 2959752).
  14. ↑ Edgar N. Gilbert, « Random plane networks and needle-shaped crystals », dans B. Noble (éditeur), Applications of Undergraduate Mathematics in Engineering, New York, Macmillan, .
  15. ↑ N. H. Gray, J. B. Anderson, J. D. Devine et J. M. Kwasnik, « Topological properties of random crack networks », Mathematical Geology, vol. 8, no 6,‎ , p. 617–628; et (en) Tomasz Schreiber et Natalia Soja, « Limit theory for planar Gilbert tessellations », . sur Arxiv.
  16. ↑ Edgar N. Gilbert, « Steiner minimal trees », SIAM Journal on Applied Mathematics, vol. 16, no 1,‎ , p. 1–29 (JSTOR 2099400).
  17. ↑ (en) Frank Hwang, Dana Richards et Pawel Winter, The Steiner Tree Problem, vol. 53, Brunswick, Elsevier, coll. « Annals of Discrete Mathematics (North-Holland Mathematics Studies) », , 339 p. (ISBN 978-0-444-89098-6), p. 80–83.
  18. ↑ An independent discovery of Costas arrays, Aaron Sterling, 9 octobre 2011.
  19. ↑ Martin Gardner, The Colossal Book of Mathematics : Classic puzzles, paradoxes, and problems : number theory, algebra, geometry, probability, topology, game theory, infinity, and other topics of recreational mathematics, W. W. Norton & Company, , 724 p. (ISBN 978-0-393-02023-6), p. 18.
  20. ↑ Fan R. K. Chung, Edward N. Gilbert, Ron L. Graham, J. B. Shearer et Jack H. van Lint, « Tiling rectangles with rectangles », Mathematics Magazine, vol. 55, no 5,‎ , p. 286–291
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Edgar N. Gilbert » (voir la liste des auteurs).

Liens externes

modifier

Ce document provient de « https://fr.wiki.x.io/w/index.php?title=Edgar_Gilbert&oldid=203197478 ».