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