Philippe Flajolet

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

Philippe Flajolet (né le 1er 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.

Sommaire

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

  1. Philippe Flajolet : Algorithmix nous a quittés, INRIA Alumni, 23 mars 2011
  2. Disparition brutale d'une figure scientifique. Livre d'hommages
  3. Philippe Flajolet 1948–2011, by Dick Lipton
  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. http://www.eurasc.org/members/members.asp?Cognome=f Liste des membres de l'European Academy of Sciences
  7. Décret du 13 juillet 2010 publié au JORF du 14 juillet 2010.
  8. recherche avancée sous Google Scholar
  9. Colloquium for Philippe Flajolet’s 60th Birthday
  10. Special issue of DMTCS in the honor of Philippe Flajolet
  11. Page du séminaire Philippe Flajolet

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Philippe Flajolet de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Philippe Flajolet — Philippe (Patrick, Michel) Flajolet (1 December 1948) is a French computer scientist.A former student of École Polytechnique , Philippe Flajolet got a Ph.D. in computer science from University Paris VII in 1977 and a doctorate of state in 1979.… …   Wikipedia

  • Philippe Flajolet — (* 1. Dezember 1948; † 22. März 2011)[1][2] war ein französischer Informatiker. Er wirkte als Forschungsleiter am Institut national de recherche en informatique et en automatique und war Mitglied der Académie des sciences. Als ehemaliger Schüler… …   Deutsch Wikipedia

  • Flajolet — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Flajolet est un nom propre qui peut désigner : Homonymes André Flajolet, né en 1946, député français du Pas de Calais Philippe Flajolet (1948 2011),… …   Wikipédia en Français

  • Discrete Mathematics (journal) — For the area of mathematics, see Discrete mathematics. Discrete Mathematics   Abbreviated title ( …   Wikipedia

  • Gauss–Kuzmin–Wirsing operator — GKW redirects here. For the Indian engineering firm see Guest Keen Williams.In mathematics, the Gauss–Kuzmin–Wirsing operator occurs in the study of continued fractions; it is also related to the Riemann zeta function. IntroductionThe… …   Wikipedia

  • Nörlund-Rice integral — In mathematics, the Nörlund Rice integral, sometimes called Rice s method, relates the n th forward difference of a function to a line integral on the complex plane. As such, it commonly appears in the theory of finite differences, and also has… …   Wikipedia

  • Mellin transform — In mathematics, the Mellin transform is an integral transform that may be regarded as the multiplicative version of the two sided Laplace transform. This integral transform is closely connected to the theory of Dirichlet series, and is often used …   Wikipedia

  • Mellin inversion theorem — In mathematics, the Mellin inversion formula (named after Hjalmar Mellin) tells us conditions under which the inverse Mellin transform, or equivalently the inverse two sided Laplace transform, are defined and recover the transformed function. If… …   Wikipedia

  • List of World War II topics (P) — # P 15 Termit # P 59 Airacomet # P 61 Black Widow # P 80 Shooting Star # P 4 class torpedo boat # P. G. Wodehouse # P. O. Box 1142 # P. Y. Saeki # P107 # Paavo Berg # Paavo Nurmi # Paavo Yrjölä # Pablo de Escandón y Barrón # Pacific Fighters #… …   Wikipedia

  • Liste de polytechniciens par promotion — Cet article est une liste de polytechniciens célèbres classés par promotion. Contrairement à la plupart des écoles d ingénieurs, mais comme aux Écoles normales supérieures (ÉNS), la promotion est l année d’entrée, et non de sortie. Ceci est… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”