Oratrice

Michèle SORIA (Sorbonne Université, LIP6)

Titre

« Combinatoire Analytique : énumération, statistiques et génération aléatoire »

Résumé

La Combinatoire Analytique, développée par Philippe Flajolet et son école à partir des années 1980, est une théorie dont l’objectif est de quantifier les propriétés de structures discrètes variées, telles que mots, permutations, arbres, graphes… L’approche est celle d’un calcul sur les structures, fondé sur les propriétés algébriques et analytiques des séries génératrices de dénombrement.

On étudie des structures qui peuvent être spécifiées récursivement en fonction d’opérations combinatoires telles que Union, Produit, Séquence, Ensemble, Cycle. La phrase-clé de la Combinatoire  Analytique est « If you can specify, you can analyse » : à partir des spécifications, on développe une chaîne de traitement systématique, voire automatique, qui donne les lois asymptotiques générales gouvernant les séquences de dénombrement et le comportement des paramètres.

La première étape consiste à transcrire les spécifications en termes d’opérations algébriques sur les séries génératrices de  dénombrement des structures. Dans l’étape suivante, les séries génératrices sont interprétées comme des fonctions analytiques, dont les singularités sont déterminantes pour les estimations asymptotiques. Cette vision par l’analyse complexe permet d’étudier les propriétés statistiques des structures de grande taille, et de montrer des phénomène d’universalité : de nombreuses propriétés des structures combinatoires dépendent de traits globaux de leur définition, et non de détails.

Cet exposé présente un panorama de résultats de Combinatoire Analytique, ainsi que quelques algorithmes efficaces pour l’énumération et la génération aléatoire. Il est illustré de nombreux exemples et accompagné de traitements automatiques avec les  modules COMBSTRUCT et GFUN de MAPLE.

Informations

Mercredi 4 mars 2020, 14h-16h

Salle 24-25/405 du LIP6 (rotonde 25, 4e étage)
4 place Jussieu, 75005 Paris
métro Jussieu (lignes 7 et 10)