Projet GAMMA nov2007-10

Génération Aléatoire: Modèles, Méthodes, Algorithmes

The goal of this project, "random generation: models, methods and algorithms", is to develop a set of fundamental methods and algorithms for the random generation of complex combinatorial structures. such objects appear in a variety of applications, especially in computer science.

Random generation plays an important role in domains dealing with enormous volumes of data, for example in interaction networks (computer, sociological, biological networks); in this case, random generation allows the comparison of models and the evaluation of their adequacy for real data. random testing and model checking are two additional fields of application for random generation. one of the main issues there arises when choosing appropriate data for testing, and designing efficient methods for fast generation of this data. in many cases the problem can be described in terms of graphs or automata, so that the data are specified as paths, or words. in these cases where intensive generation is required, the samplers have to be very efficient.

Our objective is to study all the steps leading to the realization of efficient generators for complex combinatorial structures.

One of the methods to study the properties of combinatorial objects consists of finding bijections with simpler objects like, for example, decomposable structures. Decomposable structures can be recursively specified using combinatorial constructions such as union, product, sequence, cycle, set. These operations are then directly translated into operations between the corresponding generating functions. A convenient formalization of the approach of decomposable structures is the concept of object grammars (Dutour, Fedou), that allows the description of objects using very general kinds of operations.

An alternative approach for enumerating combinatorial objects is Eco method (Barcucci, Del Lungo, Pergola, and Pinzani) that provides a recursive construction of the objects according to their size. Each object is obtained from a smaller one by making some local expansions. If the recursive construction presents a certain regularity, then it can be encoded in a formal system called succession rule, from which one can often obtain the generating function of the objects themselves. When two ECO constructions lead to the same succession rule, they can be used to determine bijections between classes of different combinatorial objects.

This analysis of combinatorial properties of the objects enables us to give recognition algorithms for our objects, useful for generation with rejection for instance, and perhaps efficient transformation algorithms between our complex objects and simpler ones, in order to exhaustively or randomly generate them.

To generate the objects themselves one can use an ad hoc method or generic approaches like Markov chains, the recursive method and Boltzmann samplers.

The recursive method due to Nijenhuis and Wilf allows both exhaustive and random generation. It was systematized by Flajolet, Zimmermann and Van Custem to treat decomposable structures. It is implemented in the packages Combstruct of Maple and CS of MuPad.

A new methodology, Boltzamnn samplers, was introduced by Duchon, Flajolet, Louchard and Schaeffer. It is based on the idea that an object receives a probability essentially proportional to an exponential of its size. A Boltzmann generator is a program randomly generating objects according to this probability distribution. It has been shown, that operations on decomposable structures are associated to operations on the generators. Theoretical as well as practical results show that the complexity of generation is linear as soon as small variations in size are allowed.

• 22/10/2009 LIAFA
  • Dominique Rossin :
    Théorème de Stanley Wilf Marcus Tardos et questions ouvertes
  • Cyril Nicaud :
    Familles d'ensembles et de partitions avec petites traces
• 06/11/2009 LIAFA

Réunions passées

• 15/01/2009
  • Olivier Bodini :
    Génération de Boltzmann pour les structures colorées
  • Lucas Gerin :
    Automates cellulaires : quelques problèmes de simulation
• 11/12/2008
  • Carine Pivoteau :
    Itération de Newton combinatoire pour le calcul de l'oracle de Boltzmann
• 12-13/11/2008
  Journées permutations, combinatoire et génération aléatoire
• 28/03/2008
  • Frédérique Bassino :
    Génération aléatoire de sous-groupes finiment engendrés d'un groupe libre
  • Cyril Nicaud :
    Génération aléatoire d'automates déterministes et accessibles
• 22/02/2008
  • Alessandra Carbone :
    Quelques exemples de génération aléatoire de structures en bioinformatique
  • Alain Denise :
    Quelques algorithmes de génération aléatoire de structures en bioinformatique
• 22/10/2007
  • Jean Mairesse :
    Méthode à la Propp et Wilson pour la génération aléatoire
  • Enrica Duchi :
    La méthode ECO
• 03/10/2007
  • Dominique Poulalhon :
    Méthode à la Propp et Wilson pour la génération aléatoire
  • Carine Pivoteau :
    Générateurs de Boltzmann
• 14/09/2007

• Workshop on Analytic Algorithmics and Combinatorics - ANALCO'09
  January 3, 2009, New York
  (co-located with the ACM-SIAM Symposium on Discrete Algorithms - SODA'09)
• ALEA 2009
• 20th International Conference on Analytical, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms - AofA'09
  June 14-19, 2009, Frejus (France).
• FPSAC 2009
• PP 2009