Philippe Flajolet

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.

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).

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.

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

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.

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…

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.