Edgar Gilbert
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png)
Pour les articles homonymes, voir Gilbert.
![une illustration sous licence libre serait bienvenue](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Defaut_2.svg/langfr-260px-Defaut_2.svg.png)
Naissance | ![]() Queens ![]() |
---|---|
Décès | ![]() Basking Ridge ![]() |
Nationalité | américaine ![]() |
Formation | Institut de technologie du Massachusetts Queens College ![]() |
Activités | Mathématicien, informaticien ![]() |
A travaillé pour | Laboratoires Bell (- MIT Radiation Laboratory (- Université de l'Illinois à Urbana-Champaign (- ![]() |
---|---|
Directeur de thèse | Norman Levinson ![]() |
modifier - modifier le code - modifier Wikidata
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.
Biographie
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
Théorie des codes
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
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
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
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
- ↑ (en) « Edgar Nelson Gilber Obituary »
- ↑ 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
- ↑ (en) « Edgar Nelson Gilbert », sur le site du Mathematics Genealogy Project.
- ↑ 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.
- ↑ 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.
- ↑ « 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.
- ↑ 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
- ↑ 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.
- ↑ 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).
- ↑ 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.
- ↑ 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.
- ↑ Edgar N. Gilbert, « Theory of Shuffling », Technical Memorandum, Bell Laboratories, , d'après la citation par (Bayer et Diaconis 1992).
- ↑ 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).
- ↑ Edgar N. Gilbert, « Random plane networks and needle-shaped crystals », dans B. Noble (éditeur), Applications of Undergraduate Mathematics in Engineering, New York, Macmillan, .
- ↑ 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.
- ↑ Edgar N. Gilbert, « Steiner minimal trees », SIAM Journal on Applied Mathematics, vol. 16, no 1, , p. 1–29 (JSTOR 2099400).
- ↑ (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.
- ↑ An independent discovery of Costas arrays, Aaron Sterling, 9 octobre 2011.
- ↑ 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.
- ↑ 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
Liens externes
- Ressources relatives à la recherche
:
- Digital Bibliography & Library Project
- Mathematics Genealogy Project
Portail des mathématiques
Portail des probabilités et de la statistique
Portail des États-Unis
Portail de l'informatique théorique