Méthodes Algorithmiques de Génération aléatoire Non Uniforme, Modèles et applications. – MAGNUM

Les méthodes sophistiquées développées au cours des dernières décennies permettent la quantification des paramètres de nombreux modèles combinatoires, arbres, graphes, mots et langages, permutations... Cependant ces méthodes sont principalement prévues pour l'analyse de modèles uniformes, où, typiquement, tous les mots (graphes ou arbres) sont tirés avec la même probabilité. Les analyses d'algorithmes existantes sont, en conséquence, limitées par l'hypothèse d'uniformité, qui est souvent loin d'être représentative de la structure des données rencontrées dans les applications du «monde réel«. Le projet MAGNUM propose de s'affranchir de cette hypothèse d'uniformité et de développer de nouvelles classes de modèles qui soient clairement pertinents pour représenter les données de la vie réelle, tout en étant encore mathématiquement traitables.

Le projet repose sur de solides méthodologies mathématiques existantes, qui ont été encore développées et interconnectées; le coeur en est la génération aléatoire des structures combinatoires complexes et la simulation de système dynamiques discrets aléatoires. En préalable nous avons réalisé l'étude de modèles combinatoires complexes. Une conséquence est la possibilité d'analyser des algorithmes ayant comme entrées des données complexes.

Le travail se poursuit sur l'analyse et la génération de modèles avec une pertinence pratique, et que l'on arrive à traiter mathématiquement.

Publications multipartenaires :
9 Revues Internationales
9 Conférences Internationales

Publications monopartenaires :
16 Revues Internationales
8 Chapitres de livres internationaux
40 Conférences Internationales

Une huitaine de prototypes logiciels

Le thème central du projet MAGNUM est l'élaboration de modèles
discrets complexes, ayant des applications dans plusieurs
branches de l'informatique. Une des principales motivations du
développement de tels modèles est la conception et l'analyse
d'algorithmes efficaces dédiés à la simulation de grands systèmes
discrets et à la génération aléatoire de grandes structures
combinatoires. Une autre motivation importante est de revisiter la
théorie de l'analyse de complexité en moyenne sous l'angle de modèles
de données réalistes.

Les méthodes sophistiquées développées au cours des dernières
décennies permettent la quantification des
paramètres de nombreux modèles combinatoires,
arbres, graphes, mots et langages, permutations... Cependant ces
méthodes sont principalement prévues pour l'analyse de modèles
uniformes, où, typiquement, tous les mots (graphes ou arbres) sont
tirés avec la même probabilité. Les analyses
d'algorithmes existantes sont, en conséquence,
limitées par l'hypothèse d'uniformité, qui est souvent
loin d'être représentative de la structure des données rencontrées
dans les applications du "monde réel".

Le projet MAGNUM propose de s'affranchir de cette hypothèse
d'uniformité et de développer de nouvelles classes de modèles qui
soient clairement pertinents pour représenter les données de la vie
réelle, tout en étant encore mathématiquement
traitables. Ce sont ces modèles qui ont le plus de chance
d'être liés à des algorithmes et structures de données efficaces.

Le projet est divisé en quatre tâches, reposant sur de
solides méthodologies mathématiques existantes, que l'on souhaite
développer et interconnecter. Le coeur en
est la génération aléatoire des structures combinatoires complexes et
la simulation de système dynamiques discrets aléatoires. Un préalable
à ces tâches est l'étude des modèles combinatoires complexes ; une
conséquence possible réside dans la possibilité d'analyser des
algorithmes ayant comme entrées des données complexes.

Ces quatre tâches portent sur les modèles et leurs applications. La
Tâche 1 s'organise autour de l'étude des modèles complexes :
l'objectif est ici d'élucider la structure des objets (permutations ou graphes) obéissant à diverses formes de
contraintes locales ou globales, et de quantifier leurs propriétés.
Ceci sert de "connaissance de base" pour les trois tâches suivantes,
c'est-à-dire la génération aléatoire et la simulation, ainsi que
l'analyse d'algorithmes sur des données réalistes. La
Tâche 2 est consacrée à la génération aléatoire selon le modèle de
Boltzmann ; un des objectifs est de développer et d'adapter ce modèle aux cadres non uniformes, un autre but important étant de
concevoir des algorithmes de génération efficaces et certifiés. La
Tâche 3 concerne les systèmes dynamiques discrets (automates
cellulaires, modèles de tas de sable) où la dynamique elle-même est
aléatoire -- ces modèles peuvent être décrits comme des processus de
Markov particuliers ; dans ce cas, le développement d'algorithmes de
simulation haute performance est conditionné par une étude profonde
des dynamiques mises en jeu. Le but de la Tâche 4 est de revisiter
l'analyse de certains algorithmes fondamentaux, en
particulier les méthodes diviser pour régner, les algorithmes de tri
et de recherche, la determinisation et la minimisation
d'automates. Jusqu'à présent, les analyses existantes sont restées
cantonnées à des modèles simples, qui ne sont pas réalistes ; notre
propos dans le projet MAGNUM est précisément d'étendre cette analyse à
des modèles de données réalistes.

L'objectif du projet MAGNUM, et les méthodes utilisées, en font une
fusion et une suite naturelle des deux précédents projets ANR GAMMA et
MASED.