Projet SADA
Structures aléatoires discrètes et algorithmes |
Responsables |
|
|
|||
LAMA Versailles |
LIX École Polytechnique |
Projet
RAP INRIA Rocquencourt |
GREYC Caen |
LaBRI Bordeaux |
Brigitte Chauvin | Gilles Schaeffer | Philippe Robert | Brigitte Vallée |
(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. |