# Philippe Flajolet

Philippe Flajolet, né le 1er décembre 1948 à Lyon et mort le 22 mars 2011$^,$ à Suresnes, 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, 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, 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, contrebalancée par un spectre scientifique unanimement respecté et d'indéniables qualités humaines, 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 18 novembre 2003 (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. 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. Il est fait chevalier de Légion d'honneur en juillet 2010.
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. 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 décembre 2008 et un volume de la revue Discrete Mathematics & Theoretical Computer Science a été consacré à cet événement. 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. En juin 2011, 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. Un colloque retraçant son parcours scientifique a eu lieu à Paris en décembre 2011.
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), 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.

## 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, 2008 (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