DS10 - Défi de tous les savoirs

Méthodes analytiques non conventionnelles en Combinatoire – MétAConC

MetAConC

Méthodes Analytiques non-Conventionnelles en Combinatoire

Enjeux et objectif

Les principales lignes directrices de ce projet peuvent être résumées par la systématisation des méthodes pour résoudre les problématiques générales suivantes : <br />• comment modéliser les structures de l'on rencontre dans de nombreuses applications (systèmes concurrents, expressions logiques, modèles physiques, Réseaux, etc.) par des constructions combinatoires et des fonctions génératrices ? <br />• comment étudier les problèmes asymptotiques correspondant, c'est à dire quelles propriétés génériques ont ces structures quand la taille devient grande ? <br />• comment générer aléatoirement de telles structures ? Et comment en analyser la complexité ? <br /> <br />Contrairement aux études précédentes, l'une de nos priorités sera celle des structures dont les fonctions de génération ont un rayon de convergence nul. Les objectifs plus spécifiques de ce projet sont : <br />• construire une théorie algébrique des nouvelles constructions combinatoires utilisées dans les applications concrètes; <br />• établir une théorie asymptotique pour les récurrences dont les fonctions de génération ont un rayon de convergence nul; <br />• développer des outils asymptotiques généraux pour le calcul numérique et l'analyse des erreurs; <br />• produire et analyser finement des générateurs efficaces pour ces structures.

Nous avons developpé de nouveaux outils conceptuels pour l'analyse des séries divergentes et en particulier des series solutions d'équation différentielle non-linéaire.
Nous avons comparé finement les approches classiques de la poissonnisation/depoissonnisation avec la méthode de Rice, en utilisant également la transformée de Laplace. Les chercheurs du domaine utilisent l'une ou l'autre de ces méthodes sans jamais les comparer. C'est un travail qui fait intervenir un quintet de transformations « Poisson-Mellin- Rice-Newton- Laplace » 

Nous avons étendu la méthode d'analyse dynamique à des algorithmes d'Euclide multi-dimensionnels (l'algorithme de Brun, et celui de Knuth). Une telle analyse fait donc intervenir des systèmes dynamiques eux-mêmes multi-dimensionnels, et mène à la comparaison précise entre ces deux algorithmes. Cette extension est aussi utile dans les modélisations et les analyses d'algorithmes de réduction de réseaux.

Nous avons continué à « revisiter » les algorithmes de recherche classiques quand les mots à rechercher sont émis par une source dynamique et le coût unitaire est la comparaison de symboles

Concernant l'analyse de structures :
Les arbres en combinatoire admettent deux sous-familles importantes : Les arbres simples et les arbres croissants simples. Nous avons mis en lumière une troisième classe appelé les arbres diamants qui rentre de manière naturelle dans l'étude des processus concurrents. Nous avons commencé une étude fine des paramètres de ces arbres qui a fait émerger des comportements non classiques.

Concernant la physique combinatoire :
Des travaux autour de la récurrence topologique ont été menés, montrant que cette dernière peut s'appliquer à des modèles généraux de tenseurs.
Nous avons travaillé sur le problème de la détermination de la courbe arctique dans le modèle à six sommets avec des conditions aux limites de la frontière du domaine. Nous avons développé une méthode alternative, par laquelle nous récupérons l'expression analytique précédemment conjecturée dans le domaine carré.

Concernant la génération aléatoire :
Un premier résultat marquant a été l'étude fine de la génération aléatoire uniforme de permutations. Depuis plusieurs années, il était admis que la procédure appelé « Knuth shuffle » ou encore algorithme de Fisher-Yates était optimale pour la génération uniforme de permutations aléatoires. Cet algorithme a néanmoins quelques faiblesses (il est intrinsèquement séquentiel et exécute un nombre important de swaps éloignés en mémoire). Nous avons étudié très finement un autre générateur aléatoire (dont une version initiale avait été proposé par Rao et Sandelius dans les années 60) et montré que cet algorithme a des performances supérieures à celles de Fisher-Yates (à la fois d'un point de vue théorique qu'au niveau des benchmarks). Ce résultat est un parfait exemple d’intérêt de l'analyse d'algorithme pour obtenir des algorithmes plus efficaces.

Nous souhaitons prolonger notre analyse des structures à séries génératrices divergentes. Notre objectif ultime est de fournir une palette d'outils nouveaux pour l'analyse asymptotique fine de ces objets. Actuellement, nous nous sommes attaqués à l'étude des paramètres dans les équations divergentes de type Riccati que l'on rencontre en combinatoire dans de nombreuses situations (théorie des permutations, lambda-calcul, théorie des graphes, diagrammes, cartes combinatoires,...). Nos premiers résultats ont exhibé de nouveaux phénomènes (distributions non classiques,...).

Liste des principales publications :
Revues internationales :
1. A. Bacher, O. Bodini, H.K. Hwang, T.H. Tsai : Transactions on Algorithms (TALG), Volume 13 Issue 2, February 2017
2. O. Bodini, A. Genitrini, F. Peschanski : A quantitative

Depuis de nombreuses années, nous maintenons une collaboration intense et fructueuse entre la France et Taïwan dans le domaine
de l'analyse d'algorithmes et la combinatoire analytique. Cette collaboration a été récompensée l'an dernier par un prix de
l'Académie des Sciences décerné conjointement à C. Banderier, O. Bodini et H.-K. Hwang. Le projet MétaConc vise à renforcer et
rendre pérenne ce partenariat. Notre projet s'articule autour de la combinatoire analytique. Cette discipline s’intéresse au
développement d'outils d'analyse complexe pour rendre compte finement du comportement asymptotique de suites combinatoires.
De nombreuses avancées majeures ont été faites par l'école française fondée par Ph. Flajolet (théorèmes de transfert, méthode de
Rice,...). Nous souhaitons étendre et perfectionner ces outils (méthodes pour traiter les séries non analytiques en 0, ou des
équations fonctionnelles non élémentaires ou encore des équations différentielles non-linéaires,...). De manière plus détaillée, notre recherche d'oriente autour de trois axes :

- Structures Combinatoires et méthode symbolique : dans cet axe nous désirons enrichir la méthode symbolique de nouveaux opérateurs (opérateurs de Polya issu des groupes de Coxeter, Opérateur inverse des opérateurs de Polya, Opérateurs d'ordonnancement du type opérateur boite généralisé, algèbre des opérateurs. Opérateurs de type greffes et mutations. Mais aussi, spécifications à substitution et itérée infinie, fractions continués, radicaux continués... Etude des isomorphismes de structures : passage des classes algébriques aux classes holonomes, changement de représentations... Les structures complexes mélangeant additivité et multiplicativité.

- L'analyse asymptotique : Méthode de Rice, poissonisation-dépoissonisation-Mellin, analyse des séries non analytiques en 0, analyse des equations différentielles non-linéaires, équations de Ricatti et Painlevé, fonctions spéciales, psi-series et développement non conventionnel (DL en factoriel descendant, DL de type fonction de Lambert avec bootstrapping, analyse perturbative, étude des opérateurs décrits dans l'axe 1...

-Analyse d'algo et de structures (les applications) : Les lambda-termes, les processus concurrents, la physique combinatoire ( cartes, pavage,...), les graphes et hypergraphes (graphes cacti, modèle d'hypergraphes pour les bases de données,...), la génération aléatoire mulparamétrée sous modèle de Boltzmann.

Coordinateur du projet

Laboratoire d'informatique de l'université paris nord LIPN (Laboratoire public)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

Laboratoire d'informatique de l'université paris nord LIPN

Aide de l'ANR 293 194 euros
Début et durée du projet scientifique : septembre 2015 - 48 Mois

Liens utiles