Séminaire de Théorie Analytique des Nombres et Problèmes Diophantiens

Le 9 novembre 2000

Cyril Banderier (INRIA Rocquencourt)


Combinatoire analytique et informatique théorique.


 
 Résumé : La combinatoire analytique, mélange de combinatoire et d'analyse complexe (le mariage se faisant grâce aux séries génératrices), a pour but d'étudier le comportement asymptotique de paramètres de structures combinatoires. Or l'informatique théorique (tout comme la physique statistique, la biologie, ou la théorie des nombres) regorge de modèles qui rendent pertinente l'analyse de telles structures combinatoires.

L'analyse d'algorithmes créée par D.E. Knuth [1] en 1963 a depuis trouvé ses prosélytes. Depuis 1980, Ph. Flajolet a ainsi developpé la combinatoire analytique avec des outils tels que l'analyse de singularités [2], les méthodes de points cols [3], la transformée de Mellin [4]. L'exposé a pour but un bref survol de ces techniques, j'évoquerai donc leur utilisation (aussi bien en énumération qu'en asymptotique) sur

  • des propriétés structurelles des permutations (= algorithmes de tri),
  • la hauteur d'une fraction continuée (= calcul de pgcd, du symbole de Jacobi),
  • la hauteur des arbres binaires (= complexité de nombreux algorithmes récursifs),
  • des propriétés de connexité dans les graphes (= tolérance de panne dans les réseaux),
  • les lois limite gaussienne pour les expressions régulières (= apparition de motifs dans du texte),
  • le nombre et taille des facteurs dans des factorisations de polynômes,
  • des modèles de marches aléatoires (= génération aléatoire [5]).

    Pour finir, notons qu'une grande partie des méthodes susmentionnées sont automatisables. Zeilberger [6], Salvy et Chyzak [7] ont notamment réalisé des implantations en Maple (avec un recours à l'algèbre : D-finitude, bases de Gröbner et holonomie multivariée).

    Nous sommes donc à un carrefour de disciplines, à cheval entre mathématiques pures et informatique.


    Références :

    [1] D.E. Knuth, The Art of Computer Programming. Addison-Wesley, 3 vol. 1968-1973.
    [2] Philippe Flajolet & Andrew Odlyzko, Singularity analysis of generating functions. SIAM J. Discrete Math. 3 (1990), no. 2, 216--240.
    [3] Cyril Banderier & Philippe Flajolet & Gilles Schaeffer & Michèle Soria, Planar maps and Airy phenomena. In ICALP'00. Lecture Notes in Computer Science, vol. 1853, Springer-Verlag, January 2000.
    [4] Philippe Flajolet & Robert Sedgewick, Analytic combinatorics. Research reports, INRIA. 1993-1997.
    [5] C. Banderier & M. Bousquet-Mélou & A. Denise & Ph. Flajolet & D. Gardy & D. Gouyou-Beauchamps, Generating functions for generating trees. Discrete Mathematics. To appear.
    [6] Pierre Cartier, Démonstration ``automatique'' d'identités et fonctions hypergéométriques (d'après D. Zeilberger). Séminaire Bourbaki, Astérisque 206, 1992
    [7] Frédéric Chyzak & Bruno Salvy, Non-commutative Elimination in Ore Algebras Proves Multivariate Identities. Journal of Symbolic Computation, vol. 26, no. 2, p. 187-227.
     
     


    Retour à la page d'accueil.
    stan@math.u-bordeaux.fr