Séminaire SPACE Tours

Une petite excursion dans l'univers dans la combinatoire analytique
Cyril Banderier (CNRS & Univ. Paris 13)
Friday 29 April 2016 11:00 -  Tours -  Salle 1180 (Bât E2)

Résumé :
L'informatique et la combinatoire fourmillent de structures récursives (tels les arbres, graphes, permutations, marches aléatoires, mots, pavages, cartes, partitions...) dont les propriétés typiques sont bien capturées via des méthodes de combinatoire analytique : si a_n est le nombre d'objet de taille n, la nature récursive de ces objets permet d'obtenir une récurrence sur les a_n, et donc une équation fonctionnelle sur F(z)=sum a_n z^n. Une étude fine des singularités de F(z) donne alors l'asymptotique et les lois limites des objets de base. Cette approche fut développée avec brio par Don Knuth dans "The Art of Computer Programming", ce qui optimisait en passant de nombreux algorithmes ! Le domaine a ensuite connu un profond essor, magnifiquement présenté dans le livre "Analytic Combinatorics" de Philippe Flajolet et Robert Sedgewick, paru en 2009 chez Cambridge University Press, et accessible gratuitement en ligne : http://algo.inria.fr/flajolet/Publications/book.pdf Dans cet exposé, j'illustrerai cette approche sur les grandes classes d'équations fonctionnelles (algébriques, différentielles...) à travers de nombreux exemples venant de l'informatique, de la théorie des nombres, de la théorie des probabilités, de la combinatoire... L'exposé se veut accessible à tous.

Liens :

• Auteur