Philippe Flajolet

Page d’aide sur l’homonymie

Pour les articles homonymes, voir André Flajolet et Flajolet.

Philippe Flajolet
Philippe Flajolet, en 2006, à la conférence Analysis of Algorithms.
Biographie
Naissance
Décès
Nom de naissance
Philippe Patrick Michel FlajoletVoir et modifier les données sur Wikidata
Nationalité
Formation
Activités
Autres informations
A travaillé pour
Domaine
Membre de
Directeurs de thèse
Maurice Nivat, Jean Vuillemin (en)Voir et modifier les données sur Wikidata
Distinctions

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

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

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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.

Transition de phases : entre analyse et théorie des probabilités

[modifier | modifier le code]
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Algorithme de fouille de flots de données

[modifier | modifier le code]

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

Génération aléatoire

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

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

[modifier | modifier le code]

Notes et références

[modifier | modifier le code]
  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

[modifier | modifier le code]