Philippe Flajolet

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

Philippe Flajolet (né le 1^er décembre 1948 à Lyon et décédé le 22 mars 2011^[1],[2],[3]) était un chercheur français en informatique.

Après une scolarité au lycée Ampère de Lyon, il entre en 1968 à l'École polytechnique^[4], et devient docteur en informatique de l'université Paris 7 et docteur ès sciences. Philippe Flajolet était 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 consacrés à l'algorithmique, notamment à l'analyse et la conception d'algorithmes, et plus généralement à l'étude des structures discrètes (structure des 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 Léonard Euler, de Srivanasa Ramanujan, de Louis Comtet et de Don Knuth, et intéressé en parallèle par la linguistique, Philippe Flajolet est recruté au début des années 70 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. Cette approche 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. Les résultats 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 les coefficients). Cette approche donne de très bons résultats pour l'analyse en moyenne de paramètres des structures discrètes de l'informatique (arbres, graphes, tables de hachage, mots).

Il a étudié l'efficacité de nombreuses variantes d'algorithmes de tri, les apparitions de motifs dans du texte, des arbres, des arbres digitaux, les cartes planaires (application à la connexité), des graphes (transition de phase dans les graphes d'Erdős–Rényi), des applications fonctionnelles (application à l'algorithme rho de Pollard pour la factorisation d'entiers), le modèle des urnes d'Ehrenfest, le paradoxe des anniversaires (application au hachage), la théorie des files d'attente, la discrépance des suites. 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, 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 divide and conquer, 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é (avec Andrew Odlyzko (en)) l'analyse de singularités. 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 efficace avec peu de bits [machines de Buffon]). Il 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).

On lui doit plusieurs terminologies, reprises depuis par la communauté, mettant ainsi en exergue des idées centrales à sa recherche : combinatoire analytique, analyse de singularités, 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…

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

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'European Academy of Sciences^[6]. 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.

Philippe Flajolet est fait chevalier de Légion d'honneur^[7] en juillet 2010.

De façon plus anecdotique, son nom est pris comme exemple de recherche par le Google Scholar français^[8].

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 ("Philippe Flajolet's research in Combinatorics and Analysis of Algorithms" par H. Prodinger et W. Szpankowski). 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^[9] et un volume de la revue Discrete Mathematics and Theoretical Computer Science a été consacré à cet événement^[10]. En juin 2011, les conférences "Formal Power Series and Algebraic Combinatorics" et "Analysis of Algorithms" ont été dédiées à sa mémoire. Un séminaire francilien de combinatoire porte maintenant son nom^[11]. Un colloque est organisé en son honneur à Paris en décembre 2011.

Hobbies

Philippe Flajolet s'intéressait beaucoup au sanskrit, en liaison avec Gérard Huet, son collègue de l'INRIA et de l'Académie des sciences. Une bourse de recherches doctorales sur le sanskrit a été créée, en son honneur, après son décès.

Ouvrages

• An Introduction to the Analysis of Algorithms, (avec Robert Sedgewick), Addison-Wesley, 1995
• Analytic Combinatorics, (avec Robert Sedgewick), Cambridge University Press, 2009

Notes et références

Liens externes

• Page professionnelle
• (en) Publications de Philippe Flajolet sur DBLP
• (en) Publications de Philippe Flajolet sur ScientificCommons

• Portail de l’informatique