Projet  SADA

Structures aléatoires discrètes et algorithmes



Responsables 

CNRS

LIX

CNRS

greyc

CNRS

LAMA
Versailles
LIX
 École Polytechnique
Projet RAP
INRIA Rocquencourt
GREYC
 Caen
LaBRI
 Bordeaux
Brigitte Chauvin Gilles Schaeffer   Philippe Robert Brigitte Vallée
Mireille Bousquet-Mélou
(Coordinatrice)

Présentation détaillée


Publications

Membres

Rencontres




Résumé du projet


Ce projet fédérateur, Structures Discrètes Aléatoires et Algorithmes (SADA), propose des objectifs de recherche fondamentale ambitieux. Il s'agit de quantifier les principales propriétés de structures fondamentales qui apparaissent de manière récurrente aux travers d'applications informatiques extrêmement diverses. Les grands chapitres de notre programme de travail sont relatifs aux mots, aux structures arithmétiques, aux arbres, aux graphes, ainsi qu'à la génération aléatoire. Nous visons à développer un corpus cohérent de méthodes permettant de déterminer de manière très précise les ``profils'' des objets aléatoires : bien au delà des propriétés en moyenne, on s'attachera aux analyses en distribution, à la quantification des risques de grandes déviations, ainsi qu'à l'évolution dynamique des structures. Le projet est fondé sur la confrontation de points de vue complémentaires, incluant méthodes combinatoires, probabilistes, analytiques, et dynamiques. Plusieurs de nos approches sont assez fortement mathématisées, tandis que nos objectifs finals sont de nature algorithmique concrète.

Abstract

This federative programme, Random Discrete Structures and Algorithms, presents ambitious goals of fundamental research. The aim is to quantify the main properties of certain basic structures that occur recurrently in a variety of algorithms. The main chapters of our research programme deal with words, arithmetic structures, trees, graphs, as well as random generation. We plan to develop a consistent toolbox of methods that will allow us to determine very precisely the “profiles” of random objects: far beyond the study of average properties, we will provide complete distributions, quantify the risk of large deviations, and study the transient behaviour of the structures. This project is built on the combination of complementary view points, including combinatorial, probabilistic, analytic and dynamic approaches. Several of these approaches have a strong mathematical flavour, while our final goals deal with concrete algorithmic questions.





Page ouèbe: JF Marckert.