Philippe Flajolet

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir André Flajolet et Flajolet.

Philippe Flajolet

alt=Description de cette image, également commentée ci-après

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

Naissance 1er décembre 1948
Lyon (France)
Décès 22 mars 2011 (à 62 ans)
Nationalité Drapeau de France Français
Champs Mathématique, Informatique
Institutions INRIA
Diplôme Université Paris 7
Université Paris 11
Directeur de thèse Maurice Nivat, Jean Vuillemin
Renommé pour Combinatoire analytique
Analyse d'algorithme
Distinctions Grand prix scientifique de l'Union des assurances de Paris en 1986
prix Michel Monpetit de l'Académie des sciences en 1994
médaille d'argent du CNRS en 2004

Philippe Flajolet (1er décembre 1948 à Lyon - 22 mars 2011[1],[2]) 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[3], 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. 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 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 de 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 nombres 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 librairie "Combstruct" du logiciel Maple, développés par leurs doctorants Bruno Salvy et Paul Zimmermann (en).

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]

Génération aléatoire[modifier | modifier le code]

Il a aussi développé le concept de machines de Buffon, qui repose sur une 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[4], 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[5], contrebalancée par un spectre scientifique unanimement respecté et d'indéniables qualités humaines[6], 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 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[7]. 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[8].

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

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

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 décembre 2008[12] et un volume de la revue Discrete Mathematics and 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 ainsi le parcours de Philippe Flajolet[14]. 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[15]. Un colloque retraçant son parcours scientifique a eu lieu à Paris en décembre 2011[16].

Philippe Flajolet s'intéressait beaucoup à la linguistique, notamment 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 sa mémoire par sa femme.

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 "Philippe Flajolet" de l'université de Versailles[17], et à la bibliothèque du Centre international de rencontres mathématiques.

Ouvrages[modifier | modifier le code]

  • 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 2013 chez Cambridge University Press
  • Les quelques 300 publications (dont 208 articles) de Philippe Flajolet sont accessibles en ligne

Notes et références[modifier | modifier le code]

  1. « Philippe Flajolet : Algorithmix nous a quittés », INRIA Alumni,‎ 23 mars 2011
  2. « Philippe Flajolet 1948–2011, by Dick Lipton »
  3. Voir la photo de Philippe Flajolet à Polytechnique
  4. 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.
  5. « Quelques opinions de Philippe Flajolet sur l'administration de la recherche »
  6. « Disparition brutale d'une figure scientifique. Livre d'hommages »
  7. http://www.eurasc.org/members/members.asp?Cognome=f Liste des membres de l'European Academy of Sciences
  8. CNRS, « Médailles d'argent - Les lauréats 2004 », sur http://www.cnrs.fr (consulté le 21 février 2014)
  9. Décret du 13 juillet 2010 publié au JORF du 14 juillet 2010.
  10. recherche avancée sous Google Scholar
  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. http://smf4.emath.fr/Publications/Gazette/2011/129/
  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,‎ 5 décembre 2011

Liens externes[modifier | modifier le code]