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.
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.
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.
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.
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 .
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.
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.
Génération aléatoire uniforme de mots de langages rationnels.
Alain Denise.
Génération aléatoire et uniforme de mots.
Alain Denise.
Enumération et génération aléatoire de chemins.
Alain Denise.
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.
Génération aléatoire d'animaux dirigés.
Alain Denise et Jean-Guy Penaud.
Génération de structures arborescentes.
Alain Denise et Nadine Rouillon.