Introduction à la génération aléatoire

Une structure combinatoire est un objet mathématique discret. Il en existe de très nombreuses sortes, des listes chaînées aux polynômes sur des corps finis, en passant par les arbres, les λ-termes et les polyominos. L’objet de la combinatoire est l’étude de ces structures. Parmi les problèmes les plus classiques en combinatoire, on trouve les problèmes d’énumération : combien y a-t-il de structures vérifiant certaines propriétés ? Comme l’on traite généralement des familles infinies d’objets, on va souvent utiliser une fonction taille qui associe un entier à chaque objet et la question précédemment énoncée devient : combien y a-t-il de structures de taille n vérifiant certaines propriétés ? Rien que sur ce type de questions, de nombreux types d’approches différentes existent.

On peut, selon les cas, trouver une formule close donnant explicitement le nombre de structures de taille n pour tout n, chercher à déterminer la croissance asymptotique du nombre d’objets en fonction de la taille, développer des outils de calcul formel pour pouvoir calculer efficacement les premières valeurs, étudier les propriétés algébriques de la série génératrice… Mais l’énumération n’est pas la seule question qui se pose en combinatoire. On peut par exemple s’intéresser aux propriétés moyennes de classes d’objets, à l’existence d’une structure vérifiant certaines contraintes, à la complexité d’algorithmes basés sur des structures discrètes ou à la génération exhaustive ou aléatoire. Les domaines d’applications de tels résultats sont très dépendants des structures étudiées et contiennent entre autres l’algorithmique, la bio-informatique, la physique statistique…

Pour cela on va souvent – et ce sera le cas dans cette thèse – chercher à décomposer des objets en objets plus simples ou plus petits. Ou, en raisonnant dans l’autre sens, à combiner des objets pour obtenir des objets plus gros ou plus complexes. Ce principe est celui que l’on retrouve à la base des processus récursifs. Mais toutes les décompositions ne se valent pas : certaines seront plus naturelles, d’autres permettront une analyse asymptotique, le calcul efficace des premiers termes ou la génération aléatoire efficace. Il faut donc choisir avec soin sa décomposition en fonction des résultats que l’on souhaite obtenir.

Cette thèse se situe dans le domaine de la combinatoire analytique, décrit par Philippe Flajolet et Robert Sedgewick dans [FS09a]. L’idée maîtresse est d’utiliser des spécifications pour décrire la manière dont on décompose les structures que l’on étudie. On en déduit des relations sur des séries génératrices, ce qui conduit, par des méthodes analytiques, à des propriétés asymptotiques. La génération aléatoire vient compléter l’étude de ces propriétés asymptotiques. On y cherche à tirer selon une distribution -souvent uniforme – une structure combinatoire vérifiant certaines propriétés, comme par exemple des arbres de taille donnée. La combinatoire analytique est un cadre agréable pour la génération aléatoire, car on peut également s’appuyer sur les spécifications pour définir des générateurs aléatoires, comme les générateurs de Boltzmann [DFLS04] par exemple, en utilisant la fonction analytique associée à la série génératrice des objets.

Dans cette thèse, nous rencontrerons différents types d’objets combinatoires pour lesquels nous donnerons de nouvelles décompositions. Nous allons notamment définir des opérateurs de greffes qui permettent d’obtenir un grand objet en ajoutant des appendices de tailles bornées à un endroit donné d’un objet plus petit, par opposition aux processus branchants qui combinent plusieurs objets de tailles arbitraires pour en former un plus gros. L’exploration de ces nouvelles spécifications apporte une nouvelle vision de ces objets, et de cette vision nous obtiendrons de nouveaux résultats d’analyse asymptotique ou de génération aléatoire, inaccessibles par des spécifications plus classiques.

La philosophie générale de cette thèse peut donc être résumée de la manière suivante : étant donnée une classe combinatoire, peut-on trouver des bijections permettant d’obtenir une vision différente et utile sur ces structures. Cette étape est loin d’être automatique en général, et nous chercherons à exploiter au mieux la structure des objets pour avoir des descriptions alternatives, afin de pouvoir y appliquer des méthodes différentes et ainsi obtenir des résultats nouveaux. A partir de ces décompositions originales, nous utiliserons des méthodes classiques pour l’énumération et on exploitera leurs non-ambiguïtés constructives pour obtenir des générateurs aléatoires efficaces.

Les arbres, sous différentes formes, apparaissent dans presque tous les chapitres de cette thèse. Aussi, nous avons choisi de consacrer un chapitre de ces préliminaires à leurs définitions et à exposer des faits simples qui nous seront utiles dans la suite. De plus, c’est une première occasion de rencontrer un objet combinatoire et d’en décrire différentes propriétés.

Dans le cas général, on ne peut pas se contenter de compter uniquement les nœuds internes ou uniquement les feuilles : il existerait alors un nombre infini d’objets de taille donnée. En effet, dans le cas où l’on ne compte que les nœuds internes on peut définir, pour tout n, un arbre ayant une racine d’arité n et dont tous les fils sont des feuilles, qui auraient tous taille 1. Dans le cas où l’on ne compte que les feuilles on peut définir, pour tout n, un arbre constitué d’une chaine de n nœuds unaires suivis d’une feuille et on obtient également un nombre infini d’objets de taille 1. Il faut donc être prudent lors de la définition de la taille d’une structure combinatoire.

Un générateur aléatoire de structures combinatoires est un algorithme qui tire aléatoirement un objet a d’une classe combinatoire A selon une distribution donnée. Le cas le plus classique est la génération uniforme en taille exacte : l’algorithme prend un entier n en entrée et renvoie un objet de A de taille n de telle manière que tous les objets de taille n de A aient la même probabilité d’être tirés.

Un intéret de la génération uniforme est de savoir à quoi ressemble un objet typique de grande taille de la classe qui nous intéresse. Pour les petites tailles, on pourra préférer la génération exhaustive, rapidement impossible pour toutes les classes dont le nombre d’objet croît rapidement (de très nombreuses classes combinatoires croissent exponentiellement vites) par rapport à la taille. Pour nous, un objet de grande taille est en général un objet ayant de quelques centaines à quelques millions d’atomes, en fonction de la complexité de la structure (et de la capacité à le dessiner et d’y voir quelque chose).

Selon les classes regardées, les applications peuvent être variées. Tout d’abord, pouvoir échantillonner des grands objets combinatoires permet d’obtenir des conjectures sur la distribution moyenne de certains paramètres ou sur des propriétés limites. La génération aléatoire procure également un moyen de tester empiriquement la complexité moyenne d’algorithmes prenant en entrée des données structurées. Un autre type d’application est le raffinement de modèles : on connaît un ensemble de règles (physiques par exemple) qui donne de la structure à un objet. Si on génère un objet selon ces règles, ressemble-t-il aux objets observés dans la réalité ? Si non, c’est que les système de règles est incomplet (ou faux).

Table des matières

Introduction
I Préliminaires
1 Classes combinatoires et spécifications
1.1 Classe combinatoire non-étiquetée
1.2 Séries génératrices ordinaires
1.3 Constructeurs
1.4 Classes étiquetées et séries exponentielles
1.5 Classes Multivariées
1.6 Dérivée combinatoire
1.7 Analogie avec la théorie des espèces
2 Arbres
2.1 Arbres enracinés planaires
2.2 Arbres de Catalan
2.3 Arbres de Motzkin
2.4 Autres types d’arbres enracinés
3 Génération aléatoire
3.1 Introduction à la génération aléatoire
3.2 Méthodes ad-hoc et méthode récursive
3.3 Générateur de Boltzmann
3.4 Applications de la génération aléatoire
II Algorithmes de Rémy
4 L’algorithme original de Rémy
4.1 Introduction
4.2 L’algorithme de Rémy
4.3 Spécification holonome
5 Amélioration de l’algorithme de Rémy
5.1 Spécification des arbres de Catalan
5.2 Génération aléatoire
6 Extension aux arbres de Motzkin
6.1 Spécification holonome des arbres de Motzkin
6.2 Génération aléatoire
6.3 Conclusion et perspectives
Conclusion

Télécharger le rapport complet