Projet ANR-07-BLAN-0330 – GAMMA : Génération Aléatoire : Modèles, Méthodes et Algorithmes
Programme : Blanc (BLANC) 2007
Année de financement : 2007
Coordinateur du projet : UNIVERSITE DE PARIS XIII (UNIVERSITE DE PARIS XIII)
Partenaires : Université Paris Diderot; Université Paris 13 - Paris Nord; Université Pierre et Marie Curie
Montant : 232000.0 euros
Date de début : 2007
Durée : 36 mois
Résumé : Ce projet, Génération aléatoire : Modèles, Méthodes et -  Algorithmes, propose des objectifs de recherche fondamentale. Notre but -  est de développer un ensemble de méthodes et d'algorithmes pour la -  génération aléatoire de structures combinatoires complexes. De -  tels objets apparaissent dans de multiples applications en particulier -  informatiques. -  -  La génération aléatoire joue un rôle important dans des -  domaines manipulant d'énormes volumes de données, par exemple, dans -  les réseaux d'interactions (réseaux sociaux, biologique ou -  informatique); dans ce cas, la génération aléatoire permet de -  comparer des modèles, d'évaluer leur adéquation avec les -  données réelles. Le test logiciel et la vérification de -  programmes sont deux autres champs d'application de la génération -  aléatoire: l'un des principaux problèmes consiste alors à choisir -  des données appropriée au test et à les engendrer automatiquement -  et rapidement. -  -  Les modèles combinatoires que nous considérons incluent les graphes, -  les cartes, les automates, les mots, les permutations et des -  généralisations des partitions. -  -  Notre but est d'étudier l'ensemble des étapes conduisant à la -  réalisation de générateurs efficaces.  -  -  Plus précisément, il s'agit dans un premier temps d'étudier et de -  comprendre la structure d'objets combinatoires complexes tels que les -  graphes, les cartes, les automates ou encore les partitions -  généralisées. Cette analyse permet dans un second temps -  l'obtention d'algorithmes de reconnaissance de ces objets, utilisés par -  exemple pour la génération aléatoire par rejet, et -  éventuellement des transformations vers des objets plus simples à -  l'aide d'algorithmes efficaces, dans un but de génération exhaustive -  ou aléatoire. -  -  -  Un autre objectif de notre projet est le développement de -  l'algorithmique de la génération aléatoire et plus précisément du -  modèle de Boltzmann. Nous voulons étendre les algorithmes -  génériques de manière : -   - à pouvoir faire de la génération multicritères, -   - à pouvoir traiter de nouvelles spécifications, -   - à contrôler les problèmes d'approximation numérique ainsi que -   les défauts d'uniformité induits, -   - et à pouvoir utiliser éventuellement des versions discrète -   plutôt qu'en arithmétique flottante de ces algorithmes. -  -  Enfin, nous validerons cette démarche par la conception d'algorithmes -  dédiés aux principaux modèles considérés. -  -  Notre projet est essentiellement fondé sur la complémentarité des -  approches combinatoire et algorithmique nécessaires pour réaliser nos -  objectifs. -                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              ...