On étudie en combinatoire les objets munis d’une taille (la taille dans le cadre informatique peut se traduire par exemple par la mémoire occupée par l’objet). On appelle classe combinatoire un ensemble d’objets qui pour toute taille possède un nombre fini d’éléments. On peut par exemple considérer les textes régis par une certaine grammaire, dans ce cas la taille est le nombre de caractères, ou des arbres avec comme taille le nombre de noeuds. Une méthode naturelle pour décrire les classes, la méthode symbolique, consiste à décomposer les objets en sous-objets plus élémentaires à l’aide d’opérateurs (tels que l’union disjointe, le produit cartésien,...). On peut ensuite traduire ces décompositions sur des séries formelles. Le premier volet de résultats présentés dans cette thèse traite de la méthode symbolique et de son utilisation. On y présente des résultats asymptotiques sur des modèles d’arbres croissants issus de la théorie de la concurrence, puis une discussion sur comment décomposer certains opérateurs en réplications élémentaires. Le deuxième volet de résultats s’intéresse au sujet de la génération aléatoire uniforme d’objets dans une classe donnée. On montre tout d’abord comment générer des structures croissantes en adaptant les méthodes de génération récursive classiques aux opérateurs de produit croissant. On présente ensuite des résultats sur la génération de Boltzmann, avec une comparaison quantitative de deux méthodes, puis une extension permettant de conserver les propriétés d’uniformité de la génération en utilisant des approximations. / We study in combinatorics objects with a size (size in informatics setting can be the memory space used to represent an object). We call a combinatorial class a set of objects who for a given size have only a finite number of elements. We can for example look at text generated by a given grammar, with the number of characters as size, or trees with the number of nodes as size. A natural way of describing classes, the symbolic method, consists in decomposing objects in more elementary sub-objects with operators (disjoint union, cartesian product,...). Then we can translate theses decompositions to formal power series.The first batch of results in this thesis deals with the symbolic method and its usage. We present asymptotic results on models of increasing trees coming from concurrency theory, then we discuss on how to decompose some operators in elementary replications. The second batch of results deals with uniform random generation of objects in a given class. We first show how to generate increasing structures by adapting the recursive generation techniques to increasing product operators. Then we present two results on Boltzmann generation, with a quantitative comparison of two methods and with an extension allowing us to use approximatives values while retaining the uniformity of the generation.

La combinatoire analytique est un domaine qui consiste à appliquer des méthodes issues de l’analyse complexe à des classes combinatoires afin d’obtenir des résultats sur leurs propriétés asymptotiques. On utilise pour cela des spécifications, qui sont une manière de formaliser la structure (souvent récursive) des objets. Dans cette thèse, nous nous attachons principalement à trouver des nouvelles spécifications pour certaines classes combinatoires, afin de pouvoir ensuite y appliquer des méthodes efficaces d’énumération ou de génération aléatoire. En effet, pour une même classe combinatoire il peut exister différentes spécifications, basées sur des décompositions différentes, rendant les méthodes classiques d’énumération asymptotique et de génération aléatoire plus ou moins adaptées. Le premier volet de résultats présentés concerne l’algorithme de Rémy et la spécification holonome qui y est sous-jacente, basée sur un opérateur de greffe. On y développe un nouvel algorithme, plus efficace, de génération aléatoire d’arbres binaires et un générateur aléatoire d’arbres de Motzkin basé sur le même principe. Nous abordons ensuite des questions relatives à l’étude de sous-classes de λ-termes. Enfin, nous présentons deux autres ensembles de résultats, sur la spécification automatique d’arbres où les occurrences d’un motif donné sont marquées et sur le comportement asymptotique et la génération aléatoire de polyominos digitalement convexes. Dans tous les cas, les nouvelles spécifications obtenues donnent accès à des méthodes qui ne pouvaient pas être utilisées jusque là et nous permettent d’obtenir de nombreux nouveaux résultats. / Analytic combinatorics is a field which consist in applying methods from complex ana- lysis to combinatorial classes in order to obtain results on their asymptotic properties. We use for that specifications, which are a way to formalise the (often recursive) structure of the objects. In this thesis, we mainly devote ourselves to find new specifications for some combinatorial classes, in order to then apply more effective enumerative or random sampling methods. Indeed, for one combinatorial class several different specifications, based on different decompositions, may exist, making the classical methods - of asymptotic enu- meration or random sampling - more or less adapted. The first set of presented results focuses on Rémy’s algorithm and its underlying holonomic specification, based on a grafting operator. We develop a new and more efficient random sampler of binary trees and a random sampler of Motzkin trees based on the same principle. We then address some question relative to the study of subclasses of λ-terms. Finally, we present two other sets of results, on automatic specification of trees where occurrences of a given pattern are marked and on the asymptotic behaviour and the random sampling of digitally convex polyominoes. In every case, the new specifications give access to methods which could not be applied previously and lead to numerous new results.

L'objet de cette thèse est la réalisation d'algorithmes et d'outils d'aide à l'étude des propriétés de structures combinatoires particulières, les structures décomposables. Nous nous intéressons pour cela à la génération aléatoire et systématique de structures décomposables, puis à leur représentation graphique automatique. Ce travail se situe à la frontière entre calcul mathématique et visualisation. Les structures décomposables sont les structures combinatoires qu'il est possible de former récursivement en utilisant des constructeurs aux propriétés particulières. Le point de vue est similaire à celui adopté dans la théorie des espèces de structures, où l'on privilégie la description d'ensembles de structures à partir de transformations d'ensembles existants. Il est alors possible, grâce à des spécifications, de décrire une infinité d'ensembles de structures combinatoires parmi lesquels les permutations, les graphes fonctionnels, les arbres enracinés ou encore les hiérarchies. L'intérêt de cette démarche tient au fait que l'on sait résoudre des problèmes de dénombrement et de comportement asymptotique sur ces ensembles et générer aléatoirement de façon uniforme des structures de ces ensembles. Les applications concernent le calcul de complexité en moyenne d'algorithmes, et la génération de jeux de tests pour la validation expérimentale ou l'étalonnage d'algorithmes. Nous présentons dans cette thèse deux types de résultats. Les premiers concernent la génération de structures décomposables, les seconds leur représentation graphique. Nous présentons une implantation d'un algorithme classique de génération aléatoire de structures décomposables, et nous proposons des techniques permettant de générer tous les éléments d'un ensemble à partir de sa spécification. Nous proposons également un algorithme de tracé de graphes particuliers, pour lesquels il existe à la fois des relations d'adjacence et d'inclusion entre les nœœœœœoeuds. Ces graphes, que nous appelons les graphes composés, sont en effet bien adaptés à la représentation de la nature générique des structures décomposables. Ce travail est concrétisé par la réalisation de deux logiciels de tracé de structures combinatoires. Leur utilisation n'est cependant pas limitée à ce seule domaine et les apsects liés à leur application à la visualisation de graphes en général sont abordés.

On s'intéresse dans ce mémoire à la riche combinatoire des configurations de boucles compacte (ou FPL, ou matrices à signes alternants, ou orientations eulériennes d'une grille). Sont en particulier abordées les questions d'énumération et les liens avec l'énumération de partitions planes, les conjectures à la Razumov et Stroganov, et la génération aléatoire exactement uniforme de configurations satisfaisant des conditions arbitraires de symétrie.

Cette thèse propose une nouvelle approche pour le test statistique de<br />logiciel à partir d'une description graphique des comportements du<br />système à tester (graphe de contrôle, statecharts). Son originalité<br />repose sur la combinaison de résultats et d'outils de combinatoire<br />(génération aléatoire de structures combinatoires) et d'un solveur de<br />contraintes, pour obtenir une méthode de test complètement automatisée.<br />Contrairement aux approches classiques qui tirent des entrées, la <br />génération aléatoire uniforme est utilisée pour tirer des chemins parmi<br />un ensemble de chemins d'exécution ou de traces du système à tester. <br />Puis, une étape de résolution de contraintes est utilisée pour <br />déterminer les entrées qui permettront d'exécuter ces chemins.<br />De plus, nous montrons comment les techniques de programmation <br />linéaire peuvent améliorer la qualité d'un ensemble de tests.<br /><br />Une première application a été effectuée pour le test statistique<br />structurel défini par Thévenod-Fosse et Waeselynck (LAAS) et un <br />prototype a été développé.<br />Des expériences (plus de 10000 réalisées sur quatre fonctions issues <br />d'un logiciel industriel) ont été effectuées pour évaluer notre approche <br />et sa stabilité.<br /><br />Ces expériences montrent que notre approche est comparable à celle <br />du LAAS, est stable et a l'avantage d'être complètement automatisée. <br />Ces premières expériences nous permettent également d'envisager un <br />passage à l'échelle de notre approche. Plus généralement, ces travaux <br />pourraient servir de base pour une nouvelle classe d'outils dans le <br />domaine du test de logiciel, combinant génération aléatoire de <br />structures combinatoires, techniques de programmation linéaire et <br />résolution de contraintes.

La première partie de ce mémoire est consacrée à l'énumération de diverses familles de structures arborescentes, en général selon le nombre de sommets. Les trois premiers chapitres sont consacrés à l'étude des arborescences de Cayley telles que la racine est inférieure à ses fils et des arborescences alternantes. La plupart de nos résultats sont prouvés bijectivement. Nous nous intéressons ensuite aux arborescences coloriées, et plus particulièrement à la formule d'inversion de séries formelles multivariées de Good-Lagrange. Nous donnons une nouvelle preuve bijective d'une variante de cette formule et utilisons cette preuve pour prouver combinatoirement diverses formules d'énumération de structures arborescentes et en déduire des algorithmes de génération aléatoire pour ces structures (notamment les cactus planaires). Nous concluons cette première partie par un chapitre consacré aux constellations : en combinant notre preuve de la formule de Good-Lagrange et la conjugaison d'arborescences (due à Bousquet-Mélou et Schaeffer), nous prouvons bijectivement une formule (nouvelle) pour l'énumération de constellations selon le nombre de sommets et de faces. Dans la seconde partie, nous étudions le problème de la recherche de motifs dans une arborescence, en utilisant une structure de données classique pour les mots : l'arborescence des suffixes. Nous proposons notamment un algorithme de recherche de motifs dans une arborescence, basé sur un codage d'une arborescence par des mots et sur l'utilisation de l'arborescence des suffixes d'un de ces mots, qui semble avoir de bonnes propriétés expérimentales. Nous concluons en étendant la notion d'arborescence des suffixes des mots aux arborescences et en décrivant un algorithme de construction pour cette structure.

Cette thèse porte sur la génération aléatoire uniforme des automates finis et l'analyse des algorithmes de minimisation qui s'y appliquent. La génération aléatoire permet de conduire une étude expérimentale sur les propriétésde l'objet engendré et sur les méthodes algorithmiques qui s'y appliquent. Il s'agit également d'un outil de recherche, qui permet de faciliter l'étude théorique du comportement moyen des algorithmes. L'analyse en moyenne des algorithmes s'inscrit dans la suite des travaux précurseurs de Donald Knuth. Le schéma classique en analyse d'algorithmes consiste à étudier le pire des cas, qui n'est souvent pas représentatif du comportement de l'algorithme en pratique. D'un point de vue théorique, on définit ce qui se produit "souvent'' en fixant une loi de probabilitésur les entrées de l'algorithme. L'analyse en moyenne consiste alors à estimer des ressources utiliséespour cette distribution de probabilité. Dans ce cadre, j'ai travaillé sur des algorithmes de génération aléatoire d'automatesdéterministes accessibles (complets ou non). Ces algorithmes sont basés sur de la combinatoirebijective, qui permet d'utiliser un procédé générique : les générateurs de Boltzmann. J'ai ensuite implanté ces méthodes dans deux logiciels : REGAL et PREGA. Je me suis intéressé à l'analyse en moyenne des algorithmes de minimisation d'automateset j'ai obtenu des résultats qui montrent le cas moyen des algorithmes de Moore et Hopcroft est bien meilleur que le pire des cas

Cette thèse porte sur la génération aléatoire uniforme des automates finis et l'analyse des algorithmes de minimisation qui s'y appliquent. La génération aléatoire permet de conduire une étude expérimentale sur les propriétésde l'objet engendré et sur les méthodes algorithmiques qui s'y appliquent. Il s'agit également d'un outil de recherche, qui permet de faciliter l'étude théorique du comportement moyen des algorithmes. L'analyse en moyenne des algorithmes s'inscrit dans la suite des travaux précurseurs de Donald Knuth. Le schéma classique en analyse d'algorithmes consiste à étudier le pire des cas, qui n'est souvent pas représentatif du comportement de l'algorithme en pratique. D'un point de vue théorique, on définit ce qui se produit "souvent'' en fixant une loi de probabilitésur les entrées de l'algorithme. L'analyse en moyenne consiste alors à estimer des ressources utiliséespour cette distribution de probabilité. Dans ce cadre, j'ai travaillé sur des algorithmes de génération aléatoire d'automatesdéterministes accessibles (complets ou non). Ces algorithmes sont basés sur de la combinatoirebijective, qui permet d'utiliser un procédé générique : les générateurs de Boltzmann. J'ai ensuite implanté ces méthodes dans deux logiciels : REGAL et PREGA. Je me suis intéressé à l'analyse en moyenne des algorithmes de minimisation d'automateset j'ai obtenu des résultats qui montrent le cas moyen des algorithmes de Moore et Hopcroft est bien meilleur que le pire des cas / This thesis is about the uniform random generation of finite automata and the analysisof their state minimization algorithms. Random generators allow to conduct an experimental study on the properties of the generated objectand on the algorithms that apply to this object. It is also a useful tool for research that facilitates the theoretical study of the average behavior of algorithms. Usually, the analysis of an algorithm focuses on the worst case scenario, which is often not representative of thepractical behavior of the algorithm. From a theoretical point of view, one can define what happens "often" by fixing a probability law on the algorithm's inputs. The average analysis consists in the estimation ofthe requested resources, according to this probability distribution.In this context, I worked on several algorithms for the random generation of deterministic accessibleautomata (complete or not).Those algorithms are based on bijective combinatorics, that allows to use generic tools called the Boltzmann generators. I implemented those methods in two softwares : REGAL and PREGA. I studied the average complexity of state minimization algorithms and obtained results showing that theaverage case of the two algorithms due to Moore and Hopcroft is way better than the worst case

Dans cette thèse, on se propose d'étudier les automates de Mealy, c'est-à-dire des transducteurs complets déterministes lettre à lettre ayant même alphabet d'entrée et de sortie. Ces automates sont utilisés depuis les années 60 pour engendrer des (semi-)groupes qui ont parfois des propriétés remarquables, permettant ainsi de résoudre plusieurs problèmes ouverts en théorie des (semi-)groupes. Dans ce travail, on s’intéresse plus particulièrement aux apports possibles de l'informatique théorique à l'étude de ces (semi-)groupes engendrés par automate. La thèse présentée s'articule autours de deux grands axes. Le premier, qui correspond aux chapitres II et III, traite des problèmes de décision et plus spécifiquement du problème de Burnside dans le chapitre II et des points singuliers dans le chapitre III. Dans ces deux chapitres on met en lien des propriétés structurelles de l'automate avec des propriétés du groupe engendré ou de son action. Le second axe, représenté par le chapitre IV, se rapporte à la génération aléatoire de groupes finis. On cherche, en tirant des automates de Mealy aléatoirement dans des classes spécifiques, à engendrer des groupes finis, et on aboutit à un résultat de convergence pour la distribution ainsi obtenue. Ce résultat fait écho au théorème de Dixon pour les groupes de permutations aléatoires / In this thesis, we study Mealy automata, i.e. complete, deterministic, letter-to-letter transducers which have same input and output alphabet. These automata have been used since the 60s to generate (semi)groups that sometimes have remarkable properties, that were used to solve several open problems in (semi)group theory. In this work, we focus more specifically on the possible contributions that theoretical computer science can bring to the study of these automaton (semi)groups.The thesis consists of two main axis. The first one, which corresponds to the Chapters II and III, deals with decision problems and more precisely with the Burnside problem in Chapter II and with singular points in Chapter III. In these two chapters, we link structural properties of the automaton with properties of the generated group or of its action. The second axis, which comprises the Chapter IV, is related with random generation of finite groups. We seek, by drawing random Mealy automata in specific classes, to generate finite groups, and obtain a convergence result for the obtained distribution. This result echoes Dixon's theorem on random permutation groups

Le cadre générale de cette thèse est l'analyse quantitative des objets issus de la théorie des langages rationnels. On adapte des techniques d'analyse d'algorithmes (complexité en moyenne, complexité générique, génération aléatoire, ...) à des objets et à des algorithmes qui font intervenir des classes particulières d'automates. Dans une première partie nous étudions la complexité de l'algorithme de minimisation de Brzozowski. Bien qu'ayant une mauvaise complexité dans le pire des cas, cet algorithme a la réputation d'être efficace en pratique. En utilisant les propriétés typiques des applications et des permutations aléatoires, nous montrons que la complexité générique de l'algorithme de Brzozowski appliqué à un automate déterministe croît plus vite que tout polynôme en n, où n est le nombre d'états de l'automate. Dans une seconde partie nous nous intéressons à la génération aléatoire d'automates acycliques. Ces automates sont ceux qui reconnaissent les ensembles finis de mots et sont de ce fait utilisés dans de nombreuses applications, notamment en traitement automatique des langues. Nous proposons deux générateurs aléatoires. Le premier utilise le modèle des chaînes de Markov, et le second utilise la "méthode récursive", qui tire partie des décompositions combinatoires des objets pour faire de la génération. La première méthode est souple mais difficile à calibrer, la seconde s'avère plutôt efficace. Une fois implantée, cette dernière nous a notamment permis d'observer les propriétés typiques des grands automates acycliques aléatoires / The general context of this thesis is the quantitative analysis of objects coming from rational language theory. We adapt techniques from the field of analysis of algorithms (average-case complexity, generic complexity, random generation...) to objects and algorithms that involve particular classes of automata. In a first part we study the complexity of Brzozowski's minimisation algorithm. Although the worst-case complexity of this algorithm is bad, it is known to be efficient in practice. Using typical properties of random mappings and random permutations, we show that the generic complexityof Brzozowski's algorithm grows faster than any polynomial in n, where n is the number of states of the automaton. In a second part, we study the random generation of acyclic automata. These automata recognize the finite sets of words, and for this reason they are widely use in applications, especially in natural language processing. We present two random generators, one using a model of Markov chain, the other a ``recursive method", based on a cominatorics decomposition of structures. The first method can be applied in many situations cases but is very difficult to calibrate, the second method is more efficient. Once implemented, this second method allows to observe typical properties of acyclic automata of large size