Enumération et génération aléatoire de polyominos en réseau hexagonal.
Alain Denise, Christoph Dürr et Fouad Ibn-Majdoub-Hassani.

Un polyomino est un ensemble connexe de cellules sur une grille. Nous définissons sept classes de convexité des polyominos en réseau hexagonal, selon les six axes principaux ou diagonaux du réseau. En utilisant la technique de ``décomposition par strates'', nous donnons les séries génératrices de quelques-unes de ces classes selon plusieurs paramètres. Enfin, nous présentons des algorithmes à rejet efficaces pour la génération aléatoire uniforme de polyominos de périmètre donné de certaines classes.


Génération aléatoire uniforme de mots de langages rationnels.
Alain Denise.

Nous donnons deux algorithmes de génération aléatoire et uniforme de mots, qui s'appliquent à des classes particulières de langages rationnels. Leur efficacité est mesurée en termes de complexité logarithmique, en fonction de la longueur n des mots engendrés. Le premier algorithme est dédié aux langages dont les séries génératrices possèdent un unique pôle, éventuellement multiple ; sa complexité en temps est de l'ordre de n log n, et l'espace mémoire occupé est en log n. Le second algorithme est réservé aux langages dont les séries génératrices possèdent la propriété suivante : il existe un unique pôle de plus petit module, et ce pôle est simple. Après un pré-traitement en temps polynomial en n, le tirage aléatoire de tout mot s'effectue en temps moyen et espace linéaires.


Génération aléatoire et uniforme de mots.
Alain Denise.

Le but de cet article est d'étudier une généralisation de la méthode employée par Barcucci, Pinzani et Sprugnoli pour tirer aléatoirement des mots facteurs gauches de Motzkin en temps et espace linéaires en moyenne. Nous donnons un encadrement de sa complexité moyenne lorsqu'elle est appliquée à un langage quelconque, puis définissons la classe des fg-langages, langages pour lesquels elle peut être calculée exactement. Il apparaît un lien entre les propriétés des fg-langages et des notions issues de la Théorie des Codes. Nous terminons par l'étude de la méthode appliquée à quelques fg-langages particuliers.


Enumération et génération aléatoire de chemins.
Alain Denise.

Nous donnons une nouvelle preuve bijective pour l'énumération de certains chemins dans le plan et dans l'espace à trois dimensions. On déduit de ce travail des algorithmes linéaires de génération aléatoire et uniforme des chemins étudiés.


Méthodes de génération aléatoire d'objets combinatoires de grande taille et problèmes d'énumération.
Alain Denise.
Thèse de l'Université Bordeaux I.

La majeure partie de ce travail est consacrée à l'étude et la mise en oeuvre d'algorithmes efficaces de génération aléatoire uniforme d'objets combinatoires de grande taille. Nous nous intéressons notamment à la génération de mots, de chemins, de cartes planaires.

Le premier chapitre concerne la génération aléatoire en temps et place linéaires de certains chemins en deux ou trois dimensions. Une étape de combinatoire bijective permet de réduire ce problème à la génération de mots de langages que l'on maîtrise.

Dans le chapitre 2, nous considérons le problème de la génération aléatoire de mots d'un langage rationnel. Nous étudions les algorithmes connus, puis nous en donnons deux variantes qui, appliquées à certaines classes de rationnels, permettent d'améliorer la complexité du tirage.

Nous étudions dans le chapitre 3 une méthode de rejet améliorée pour la génération de mots. Nous introduisons les fg-langages , langages liés aux codes préfixes maximaux, pour lesquels la complexité moyenne de l'algorithme peut être calculée précisément. Le méthode est notamment appliquée à la génération de codes de cartes planaires.

Le chapitre 4 décrit une méthode de génération de mots dans le mélange de deux langages.

Le dernier chapitre est consacré à un problème d'énumération : il s'agit de donner des formules explicites pour l'énumération des chemins de Dyck selon deux paramètres : le poids en pyramides et le nombre de paires extérieures .


Génération aléatoire d'animaux dirigés.
Alain Denise et Jean-Guy Penaud.

Les animaux dirigés sont des objets combinatoires qui apparaissent dans la modélisation des phénomènes physiques tels que les transitions de phase. La génération aléatoire d'animaux dirigés de grande taille est un moyen d'étudier statistiquement certains paramètres utiles à la compréhension de ces modèles. Nous présentons une synthèse des travaux réalisés dans ce domaine, travaux fondés sur le codage d'objets combinatoires et l'algorithmique sur les mots.


Génération de structures arborescentes.
Alain Denise et Nadine Rouillon.

Les animaux dirigés sont des objets combinatoires qui, de par leur structure ramifiée et leur caractère fractal, constituent un sujet d'étude intéressant. Il existe une méthode permettant de générer aléatoirement en temps et espace linéaires de tels animaux, faisant appel à des techniques de codage d'objets combinatoires et d'algorithmique sur les mots. En modifiant certains paramètres lors de l'application de cette méthode, on obtient des animaux ``pseudo-aléatoires'' de grande taille, dont l'aspect est semblable à celui de certains végétaux. Ce travail est réalisé à l'aide du logiciel CalICo qui, du fait de son fonctionnement interactif et de ses interfaces graphique, s'adapte bien à la visualisation et la manipulation de tels objets.