Accueil🇫🇷Chercher

Philippe Flajolet

Philippe Flajolet, né le à Lyon et mort le [1] - [2] à Suresnes[3], est un chercheur français en informatique et en mathématiques.

Philippe Flajolet
Philippe Flajolet, en 2006, à la conférence Analysis of Algorithms.

Après une scolarité au lycée Ampère de Lyon, il entre en 1968 à l'École polytechnique[4], il obtient ensuite un doctorat de troisième cycle à l'université Paris 7 en 1972, puis un doctorat d'État à l'université Paris 11 en 1979. Il devient, par la suite, directeur de recherche à l'Institut national de recherche en informatique et en automatique et membre de l'Académie des sciences.

Ses principaux travaux en informatique sont en combinatoire et consacrés à l'algorithmique, notamment à l'analyse et la conception d'algorithmes, et plus généralement à l'étude des structures discrètes (dont les structures de données de base de l'informatique) via l'établissement de théorèmes en analyse complexe et en théorie des probabilités, améliorant ainsi en retour la performance de nombreux algorithmes.

Travaux

Inspiré principalement par la lecture des travaux de Leonhard Euler, de Srinivasa Ramanujan, de Louis Comtet et de Donald Knuth, et intéressé en parallèle par la linguistique, Philippe Flajolet est recruté au début des années 1970 par Maurice Nivat pour travailler en théorie des langages et en complexité. Très vite, au contact de Marcel-Paul Schützenberger et de Jean Vuillemin, ses travaux prennent une tournure dont il fera le programme de toute sa carrière de chercheur : un mariage heureux entre méthodes formelles (combinatoire symbolique) et méthodes analytiques (analyse complexe), le tout appliqué à l'informatique et aux mathématiques discrètes. Ces travaux culminent avec la création, avec Robert Sedgewick, d'un nouveau domaine : la combinatoire analytique.

Combinatoire analytique

La combinatoire analytique consiste à exprimer un problème en termes combinatoires puis à passer à une représentation analytique des objets combinatoires via des fonctions génératrices comptant certains paramètres de ces objets combinatoires (cette première étape est qualifiée par Flajolet de méthode symbolique). Les outils de l'analyse complexe (calcul de résidu, point col, localisation des singularités) permettent ensuite d'obtenir des résultats sur le comportement de la série génératrice (en particulier sur ses coefficients). Cette approche peut ainsi être vue comme une cousine de la théorie analytique des nombres, comme cela transparaît notamment dans les travaux précurseurs de mathématiciens tels Godfrey Harold Hardy, Srinivasa Ramanujan, Gaston Darboux, George Pólya, Paul Erdős…

La combinatoire analytique est le trait commun de tous les articles de Flajolet, dont le mérite est d'avoir su cerner la force de cette idée, de la généraliser au point d'en faire une méthode appliquée à des univers a priori fort différents.

Analyse d'algorithmes en moyenne

La combinatoire analytique trouve un terreau naturel d'applications dans l'analyse en moyenne d'algorithmes, car celle-ci repose souvent sur l'étude de quelques paramètres clefs des structures discrètes de l'informatique (arbres, graphes, tables de hachage, mots, permutations…).

Flajolet a ainsi étudié l'efficacité de nombreuses variantes d'algorithmes de tri, les apparitions de motifs dans du texte ou dans des arbres. Il a travaillé sur les caractéristiques typiques des arbres digitaux, des cartes planaires (application à la connexité), des graphes, des applications fonctionnelles (application à l'algorithme rho de Pollard pour la factorisation d'entiers), de la factorisation des polynômes sur un corps fini, des modèles d'urnes (dont celui d'Ehrenfest, domaine qui a connu un vif renouveau après un article de Flajolet en 2004 reposant et résolvant le problème via une reformulation en termes d'équations différentielles). Il s'est également intéressé au paradoxe des anniversaires (application au hachage), à la théorie des files d'attente, l'obtention d'identité de polylogarithmes et de fonctions polyzêtas, à la discrépance des suites, au coût d'algorithmes euclidiens (qui s'avère lié à l'hypothèse de Riemann !)…

Il a travaillĂ© sur le comptage probabiliste et efficace de grands ensembles de donnĂ©es, sur la gĂ©nĂ©ration alĂ©atoire d'objets combinatoires (par des mĂ©thodes rĂ©cursive et boltzmannienne) et sur des thĂ©matiques liĂ©es au calcul formel et aux probabilitĂ©s. Il a Ă©tabli des phĂ©nomènes de transition de phase sur les graphes alĂ©atoires (modèle d'ErdĹ‘s–RĂ©nyi), les cartes combinatoires, jetĂ© les bases des algorithmes en-ligne (comptage probabiliste via des algorithmes log counting), gĂ©nĂ©ralisĂ© l'utilisation de transformĂ©es intĂ©grales (transformĂ©e de Mellin) pour l'analyse d'algorithmes « diviser pour rĂ©gner Â», utilisĂ© des propriĂ©tĂ©s de clĂ´ture « analytique Â» pour montrer la non algĂ©bricitĂ© de certains langages, ou la non D-finitude de certaines structures, rĂ©alisĂ© une synthèse combinatoire du lien entre fractions continuĂ©es, polynĂ´mes orthogonaux et marches alĂ©atoires, dĂ©veloppĂ© l'analyse de singularitĂ©s avec Andrew Odlyzko.

Ces travaux ont mis en exergue des phénomènes de comportement asymptotique universel, notamment pour la hauteur moyenne d'arbres aléatoires (question liée à la taille de la pile lors d'appels récursifs, et aussi à un problème voisin en informatique : la fonction registre, qui correspond aussi au nombre de Horton-Strahler en hydrographie).

Il avait un goût particulier pour les fonctions spéciales (telle la fonction d'Airy, les fonctions de Bessel, les fonctions elliptiques de Jacobi) et les constantes mathématiques, et a donné plusieurs algorithmes pour calculer ces dernières à une grande précision (jouant entre représentations série/intégrale, schémas d'accélération de convergence).

Calcul formel

Philippe Flajolet a contribué au développement de plusieurs algorithmes permettant l'automatisation, notamment via le calcul formel, des calculs mathématiques (énumération, asymptotique, loi limites, génération exhaustive, génération aléatoire).

Très tôt, avec son collègue Jean-Marc Steyaert avec lequel il a coécrit sa thèse de troisième cycle, Flajolet a eu la vision de logiciels qui devraient permettre d'automatiser nombre de leurs calculs ; ceci a débouché dans les années 1980, lors de l'éclosion des systèmes de calcul formel, sur le système Luo, et la bibliothèque « Combstruct » du logiciel Maple, développés par leurs doctorants Bruno Salvy et Paul Zimmermann.

Flajolet a contribué à promouvoir en combinatoire et en calcul formel la notion d'holonomie, dans sa reformulation en termes de D-finitude, c'est-à-dire de séries vérifiant des équations différentielles, un domaine essentiellement développé par Ira Gessel, Richard Peter Stanley, Doron Zeilberger. Il a donné divers critères de non-holonomie, et aussi établi l'holonomie de nombreux problèmes combinatoires.

On lui doit aussi l'algorithme de « Flajolet-Salvy » qui établit que le suivi de branche est décidable pour une fonction algébrique ou encore l'algorithme « ornithorynque » qui manipule des fonctions symétriques pour calculer le polynôme minimal de certaines fonctions algébriques. Plus généralement, Flajolet avait toujours à cœur de veiller à l'automatisation des méthodes symboliques et analytiques qu'il développait, et présentait donc souvent dans ses articles ses méthodes comme un algorithme.

Algorithme de fouille de flots de données

Flajolet est l'auteur d'un algorithme de fouille de flots de données : l'algorithme de Flajolet–Martin.

Génération aléatoire

Il a aussi développé le concept de machines de Buffon, qui repose sur un moyen simple et efficace de simuler diverses lois (y compris à paramètres transcendants) avec peu de bits.

Des terminologies imagées

On lui doit plusieurs terminologies, reprises depuis par la communauté, mettant ainsi en exergue des idées centrales à sa recherche, ou flirtant parfois avec humour avec des références culturelles variées : combinatoire analytique, analyse de singularités, méthode symbolique, méthode du noyau, comptage probabiliste, pompage des moments, théorème de Drmota-Lalley-Woods, théorème des quasi-puissances de Hwang, théorème de Borges, phases gazeuse/liquide/solide (pour les graphes), contour camembert, modèle d'urnes mabinogiennes ou d'OK Corral, méthode de Rice, dualité magique, méthode de Boltzmann, machines de Buffon…

Structuration de la recherche

Philippe Flajolet a joué un rôle de premier plan dans la structuration de la recherche nationale et internationale en informatique mathématique[5], réunissant autour de problématiques communes différents chercheurs issus notamment des mathématiques discrètes, de l'analyse complexe, des probabilités, de l'algorithmique, du calcul formel, de la physique statistique et de la bioinformatique.

Il a occupé diverses tâches administratives (direction d'équipe, de projets), comités scientifiques, rédaction d'un plan stratégique de l'INRIA, expert AERES… toutefois son aversion pour la langue de bois et les discours administratifs[6], contrebalancée par un spectre scientifique unanimement respecté et d'indéniables qualités humaines[7], en ont fait un personnage à part, auprès duquel on venait parfois demander d'être médiateur dans telle ou telle querelle de clocher, ou tout simplement, le plus souvent, prendre conseil.

Distinctions

Philippe Flajolet est élu membre correspondant de l'Académie des sciences en 1993, puis membre le (dans la section des Sciences mécaniques et informatiques). Il est aussi élu membre de l'Academia Europaea en 1995, puis membre de l'Académie européenne des sciences[8]. Il a reçu le grand prix scientifique de l'Union des assurances de Paris en 1986, le prix Michel-Monpetit de l'Académie des sciences en 1994. La même année, il est fait docteur honoris causa de l'université libre de Bruxelles. En 2004, il obtient la médaille d'argent du CNRS[9]. Il est fait chevalier de Légion d'honneur[10] en .

Philippe Flajolet a été orateur invité au Congrès international des mathématiciens en 2002, à Pékin.

En 1998, un numĂ©ro spĂ©cial de la revue Algorithmica lui a Ă©tĂ© dĂ©diĂ© Ă  l'occasion de son cinquantième anniversaire, ce numĂ©ro contient notamment un rĂ©sumĂ© de ses recherches[11]. La revue Discrete Mathematics, dans son volume 306 de 2006 consacrĂ© aux articles les plus influents depuis sa crĂ©ation en 1971, a notamment rĂ©Ă©ditĂ© l'article de Philippe Flajolet « Combinatorial Aspects of Continued Fractions Â», initialement paru en 1980.

Un colloque a été organisé pour ses 60 ans en [12] et un volume de la revue Discrete Mathematics & Theoretical Computer Science a été consacré à cet événement[13]. De nombreuses revues ont diffusé une notice nécrologique en sa mémoire, dont la Gazette des mathématiciens de la Société mathématique de France, qui a dans son numéro 129 donné divers témoignages de proches relatant à cette occasion le parcours de Philippe Flajolet[14]. En , les conférences Formal Power Series and Algebraic Combinatorics et Analysis of Algorithms lui ont été dédiées. Un séminaire francilien de combinatoire porte maintenant son nom[15]. Un colloque retraçant son parcours scientifique a eu lieu à Paris en [16].

Sa collection de livres de linguistique et de mathĂ©matiques (2 000 ouvrages) a fait l'objet d'une donation Ă  la bibliothèque de linguistique de Paris 7, Ă  la nouvelle bibliothèque universitaire de l'universitĂ© de Versailles (qui lui est dĂ©diĂ©e[17]), et Ă  la bibliothèque du Centre international de rencontres mathĂ©matiques.

Philippe Flajolet (à titre posthume) et Robert Sedgewick sont les lauréats 2019 du Prix Leroy P. Steele, dans la section « vulgarisation mathématique », pour leur livre Analytic Combinatorics[18].

Ouvrages

  • An Introduction to the Analysis of Algorithms, Philippe Flajolet et Robert Sedgewick, Addison-Wesley, 1995. En version française : Introduction Ă  l'analyse des algorithmes, Thomson Publishing France, 1996.
  • (en) Philippe Flajolet et Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, (ISBN 0-521-89806-4, lire en ligne)
  • Ĺ’uvres complètes de Philippe Flajolet, (7 volumes en prĂ©paration), devrait sortir en 2022 chez CSLI
  • Les quelque 300 publications (dont 208 articles) de Philippe Flajolet sont accessibles en ligne

Notes et références

  1. « Philippe Flajolet : Algorithmix nous a quittés », INRIA Alumni, .
  2. « Philippe Flajolet 1948–2011, by Dick Lipton ».
  3. État civil sur le fichier des personnes décédées en France depuis 1970
  4. Voir la photo de Philippe Flajolet Ă  Polytechnique
  5. Philippe Flajolet (1948 - 2011). Obituary by Bruno Salvy, Bob Sedgewick, Michèle Soria, Wojciech Szpankowski, Brigitte Vallée. Revue du Séminaire Lotharingien de Combinatoire. Juin 2011.
  6. « Quelques opinions de Philippe Flajolet sur l'administration de la recherche »
  7. « Disparition brutale d'une figure scientifique. Livre d'hommages »
  8. https://www.eurasc.org/user/238/philippe-flajolet Liste des membres de l'Académie européenne des sciences
  9. CNRS, « Médailles d'argent - Les lauréats 2004 » (consulté le )
  10. Décret du 13 juillet 2010 publié au JORF du 14 juillet 2010.
  11. « Philippe Flajolet's research in Combinatorics and Analysis of Algorithms Â», H. Prodinger & W. Szpankowski, Algorithmica, 1998
  12. Colloquium for Philippe Flajolet’s 60th Birthday
  13. Special issue of DMTCS in the honor of Philippe Flajolet
  14. « Présentation Gazette de la Société Mathématique de France », sur emath.fr (consulté le ).
  15. Page du "SĂ©minaire de combinatoire Philippe Flajolet"
  16. Colloque "Philippe Flajolet and Analytic Combinatorics", Paris, décembre 2011.
  17. « L’UFR des sciences souhaite honorer Philippe Flajolet », sur Bibliothèque universitaire des Sciences de Versailles,
  18. 2019 Steele Prize for Mathematical Exposition Goes to Philippe Flajolet and Robert Sedgewick.

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.