Projet ANR-10-BLAN-0204 – MAGNUM : Méthodes Algorithmiques de Génération aléatoire Non Uniforme, Modèles et applications.
Programme : Sciences de l'information, de la matière et de l'ingénierie : Sciences de l’information, simulation (Blanc SIMI 2) 2010
Année de financement : 2010
Coordinateur du projet : Madame SORIA Michele (UNIVERSITE PARIS VI [PIERRE ET MARIE CURIE])
Partenaires : Institut de Recherche en Informatique Fondamentale; Laboratoire d'Informatique de Paris-Nord; Laboratoire d'Informatique de Paris 6
Montant : 557218.0 euros
Durée : 48 mois
Résumé : 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.