Ce mémoire aborde les questions relatives à la mise en place de procédures de conception rapide, fiable et automatisée des volumes élémentaires représentatifs (VER) d’un matériau composite à microstructure complexe (matrice/inclusions), et de la détermination de leurs propriétés homogénéisées ou effectives. Nous avons conçu et développé des algorithmes conduisant à des outils efficaces permettant la génération aléatoire de tels matériaux à inclusions sphériques, cylindriques, elliptiques ou toute combinaison de celles-ci. Ces outils sont également capables d’altérer les inclusions : inflation, déflation, arrachements aléatoires, ondulation et de les pelliculer permettant ainsi de générer des VER s’approchant des matériaux composites fabriqués. Un soin particulier a été porté sur la génération de VER périodiques. Les caractéristiques homogénéisées ou propriétés effectives de matériaux constitués de tels VER périodiques peuvent alors être déterminées selon le principe d’homogénéisation périodique, soit par une méthode basée sur un schéma itératif utilisant la FFT (Transformation de Fourier Rapide) via l’équation de Lippmann-Schwinger, soit par une méthode d’éléments finis. Le caractère aléatoire de la génération nous amène à réaliser des études en moyenne à partir d’un ensemble de paramètres morphologiques déterminé : nombre d’inclusions, type et forme, fraction volumique, orientation des inclusions, prise en compte d’une éventuelle altération. Deux études particulières sur la conductivité thermique apparente ont été menées, la première sur les composites à inclusions sphériques pelliculées de façon à déterminer l’influence de l’épaisseur de la pellicule et la seconde sur les composites de type stratifié en polymère et fibre de carbone, cousu par un fil de cuivre pour évaluer l'apport de la couture en cuivre selon la fibre de carbone utilisée. / This thesis focuses on setting up of fast, reliable and automated approaches to design representative volume elements (RVE) of composite materials with complex microstructures (matrix/inclusions) and the evaluation of their effective properties via a homogenization process. We developed algorithms and efficient tools for the random generation of such materials. Inclusions shapes may be spherical, cylindrical, elliptical or any combinations of them. Inflation, deflation, dislocation, undulation and coating are also available to generate RVE. The aim is to approach realistic materials subjected to be damaged during production. Particular attention has been focused on the periodic RVE generation.The homogenized characteristics or effective properties of materials formed from such periodic RVE may then be determined according to the principle of periodic homogenization, by an iterative scheme using FFT (Fast Fourier Transform) via the integral Lippmann-Schwinger or by a finite elements method.The stochastic generation of RVE and the set of morphological parameters studied: number of inclusions, type and shape, volume fraction, orientation of the inclusions lead to achieve an average process. Moreover, a special study has been led to take into account the behavior of altered inclusions. Furthermore, we studied two particular cases on the apparent thermal conductivity of the composite, the first for coated spherical inclusions in order to determine the influence of the layer thickness and the second for laminated polymer and carbon fiber composite sewn by a copper wire, in order to determine the influence of the sewing contribution according to the carbon fiber used.

Un programme concurrent est composé de plusieurs unités logiques : les processus. Chaque processus a un comportement qui lui est propre : il exécute ses actions de façon séquentielle. Un objectif important est de s'assurer que de tels systèmes concurrents complexes soient cependant exempts de défaut. Cette problématique est étudiée dans le cadre de la théorie de la concurrence. Quand plusieurs processus s’exécutent en parallèle, l’ordre d’exécution des actions du programme global n’est plus déterminé. On assiste au fameux phénomène "d’explosion combinatoire" faisant référence au très grand nombre d’exécutions globales possibles. Les diverses techniques et méthodes d'analyse existantes (model checking, analyse statique, tests automatisés, etc) se heurtent irrémédiablement à cette "explosion". Cette thèse s'inscrit dans un projet à long terme d'étude quantitative de ce phénomène et de développement des techniques d’analyse statistique basées sur la génération aléatoire uniforme. Notre objectif dans cette thèse est de traiter une composante fondamentale de la concurrence : la synchronisation. Ce mécanisme permet aux processus de communiquer entre eux. Dans cette thèse nous proposons un modèle combinatoire de structures croissantes pour modéliser les exécutions de programmes concurrents synchronisés. Avec des outils de combinatoire analytique nous obtenons plusieurs résultats exacts et asymptotiques sur le nombre moyen d'exécutions dans des sous-classes de programmes concurrents. Nous présentons aussi plusieurs algorithmes de génération aléatoire uniforme de structures croissantes et de leurs étiquetages. / A concurrent program is a composition of several logical blocks: the processes. Each process has its own behavior, independent from the others: it sequentially runs its actions. An important goal is to ensure that such concurrent complex systems are faultless. This problem is studied in the field of concurrency theory. When several process are running in parallel, the running order of the actions of the total program is no more decided. This is the well-known "combinatorial explosion" phenomena, meaning that the number of possible runs of the global program is huge. The analysis techniques and methods existing (model checking, static analysis, automated testing, etc) are irremediably limited by this "explosion". This thesis is a part of a long-term project about the quantitative study of this phenomena and the development of statistic analysis methods based on the uniform random generation. Our specific goal is to study a fundamental principle of the concurrency theory: the synchronization. This mechanism allows communications between the processes. In this thesis we propose a combinatorial model of increasingly labeled structures to deal with runs of synchronized concurrent programs. Using the tools of analytic combinatorics we obtain close formulas and asymptotic equivalents for the average number of runs in several subclasses of concurrent programs. We also present algorithms of uniform random generation of increasingly labeled structures and for their increasing labelings.

Le test boîte blanche basé sur les chemins est largement utilisé pour la validation de programmes. A partir du graphe de flot de contrôle (CFG) du programme sous test, les cas de test sont générés en sélectionnant des chemins d'intérêt, puis en essayant de fournir, pour chaque chemin, des valeurs d'entrées concrètes qui déclencheront l'exécution du programme le long de ce chemin.Il existe de nombreuses manières de définir les chemins d'intérêt: les méthodes de test structurel sélectionnent des chemins remplissant un critère de couverture concernant les éléments du graphe; dans l'approche aléatoire, les chemins sont tirés selon une distribution de probabilité sur ces éléments. Ces méthodes aléatoires ont l'avantage de fournir un moyen d'évaluer la qualité d'un jeu de test à travers la probabilité minimale de couvrir un élément du critère.Fournir des valeurs concrètes d'entrées nécessite de construire le prédicat de cheminement chaque chemin, i.e. la conjonction des contraintes sur les entrées devant être vérifiée pour que le système s'exécute le long de ce chemin. Cette construction se fait par exécution symbolique. Les données de test sont ensuite déterminées par résolution de contraintes. Si le prédicat d'un chemin est insatisfiable, le chemin est dit infaisable. Il est très courant qu'un programme présente de tels chemins, leur nombre surpassent généralement de loin celui des faisables. Les chemins infaisables sélectionnés lors la première étape ne contribuent pas au jeu de test final, et doivent être tirés à nouveau. La présence de ces chemins pose un sérieux problème aux méthodes structurelles et à toutes les méthodes d'analyse statique, la qualité des approximations qu'elles fournissent étant réduite par les données calculées le long de chemins infaisables.De nombreuses méthodes ont été proposées pour résoudre ce problème, telles que le test concolique ou le test aléatoire basé sur les domaines d'entrée. Nous présentons un algorithme qui construit de meilleures approximations du comportement d'un programme que son CFG, produisant un nouveau CFG qui sur-approxime l'ensemble des chemins faisables mais présentant moins de chemins infaisables. C'est dans ce nouveau graphe que sont tirés les chemins.Nous avons modélisé notre approche et prouvé formellement, à l'aide de l'assistant de preuve interactif Isabelle/HOL, les propriétés principales établissant sa correction.Notre algorithme se base sur l'exécution symbolique et la résolution de contraintes, permettant de détecter si certains chemins sont infaisables ou non. Nos programmes peuvent contenir des boucles, et leurs graphes des cycles. Afin d'éviter de suivre infiniment les chemins cycliques, nous étendons l'exécution symbolique avec la détection de subsomptions. Une subsomption peut être vue comme le fait qu'un certain point atteint durant l'analyse est un cas particulier d'un autre atteint précédemment: il n'est pas nécessaire d'explorer les successeurs d'un point subsumé, ils sont subsumés par les successeurs du subsumeur. Notre algorithme a été implémenté par un prototype, dont la conception suit fidèlement la formalisation, offrant un haut niveau de confiance dans sa correction.Dans cette thèse, nous présentons les concepts théoriques sur lesquels notre approche se base, sa formalisation à l'aide d'Isabelle/HOL, les algorithmes implémentés par notre prototype et les diverses expériences menées et résultats obtenus à l'aide de ce prototype. / White-box, path-based, testing is largely used for the validation of programs. Given the control-flow graph (CFG) of the program under test, a test suit is generated by selecting a collection of paths of interest, then trying to provide, for each path, some concrete input values that will make the program follow that path during a run.For the first step, there are various ways to define paths of interest: structural testing methods select some set of paths that fulfills coverage criteria related to elements of the graph; in random-based techniques, paths are selected according to a given distribution of probability over these elements (for instance, uniform probability over all paths of length less than a given bound). Both approaches can be combined as in structural statistical testing. The random-based methods above have the advantage of providing a way to assess the quality of a test set as the minimal probability of covering an element of a criterion.The second step requires to produce for each path its path predicate, i.e. the conjunction of the constraints over the input parameters that must hold for the system to run along that path. This is done using symbolic execution. Then, constraint-solving is used to compute test data. If there is no input values such that the path predicate evaluates to true, the path is infeasible. It is very common for a program to have infeasible paths and such paths can largely outnumber feasible paths. Infeasible paths selected during the first step will not contribute to the final test suite, and there is no better choice than to select another path, hoping for its feasibility. Handling infeasible paths is the serious limitation of structural methods since most of the time is spent selecting useless paths. It is also a major challenge for all techniques in static analysis of programs, since the quality of the approximations they provide is lowered by data computed for paths that do not correspond to actual program runs.To overcome this problem, different methods have been proposed, like concolic testing or random testing based on the input domain. In path-biased random testing, paths are drawn according to a given distribution and their feasibility is checked in a second step. We present an algorithm that builds better approximations of the behavior of a program than its CFG, providing a transformed CFG, which still over-approximates the set of feasible paths but with fewer infeasible paths. This transformed graph is used for drawing paths at random.We modeled our graph transformations and formally proved, using the interactive theorem proving environment Isabelle/HOL, the key properties that establish the correctness of our approach.Our algorithm uses symbolic execution and constraint solving, which allows to detect whether some paths are infeasible. Since programs can contain loops, their graphs can contain cycles. In order to avoid to follow infinitely a cyclic path, we enrich symbolic execution with the detection of subsumptions. A subsumption can be interpreted as the fact that some node met during the analysis is a particular case of another node met previously: there is no need to explore the successors of the subsumed node: they are subsumed by the successors of the subsumer. Our algorithm has been implemented by a prototype, whose design closely follows said formalization, giving a good level of confidence in its correctness.In this thesis, we introduce the theoretical concepts on which our approach relies, its formalization in Isabelle/HOL, the algorithms our prototype implements and the various experiments done and results obtained using it.

La mise en évidence des mécanismes de sélection agissant sur les données génomiques structurées (ARN, Protéines, ADN...) nécessite l'élaboration de modèles de séquences. Une fois un tel modèle élaboré, il est possible, au prix d'une analyse mathématique parfois complexe ou par le biais de la<br />génération aléatoire, d'évaluer la significativité d'un phénomène observé. Tout d'abord, nous nous intéressons aux propriétés des grammaires pondérées, un formalisme particulièrement adapté à la modélisation de la structure des ARN, dérivant des algorithmes de génération aléatoire efficaces implémentés au sein du prototype GenRGenS. Nous abordons le calcul automatique des pondérations réalisant des valeurs observées pour les paramètres du modèle, ainsi qu'une implémentation basée sur une approche optimisation. Dans un second temps, nous abordons la modélisation de la structure secondaire d'ARN. Après quelques rappels de biologie moléculaire, nous proposons plusieurs modèles basés sur des grammaires pondérées permettant la génération de structures d'ARN réalistes. L'utilisation d'un algorithme d'optimisation permet le calculer des pondérations correspondant à certaines familles d'ARN. Nous proposons enfin un algorithme d'extraction de structure secondaire maximale dans une structure générale, qui permet de profiter des données récentes issues de la cristallographie. Le dernier chapitre de cette thèse s'intéresse à l'analyse d'un algorithme de recherche de similarité heuristique, dont la sensibilité s'avère étroitement liée à la probabilité de présence d'un motif au sein de marches aléatoires particulières, les chemins culminants. Ces marches restent positives, et atteignent une altitude maximale en leur dernier pas. Nous proposons un algorithme récursif de génération aléatoire pour ces chemins. En combinant des techniques issues de la combinatoire énumérative, l'analyse asymptotique et la théorie des langages, nous dérivons des algorithmes de génération aléatoire par rejet linéaires dans de nombreux cas.

Cette thèse s'inscrit dans la problématique de la comparaison de graphes. Nous proposons dans la première partie de ce manuscrit plusieurs algorithmes de recherche de motifs similaires dans de grands graphes. La seconde partie de cette thèse traite de l'étude des arborescences de fichiers, structure de données pour laquelle la méthode initiale de reconnaissance de motifs a été développée. Nous présentons un modèle stochastique pour la génération aléatoire de structure arborescentes, basé sur les observations de l'étude statistique des données réelles. Enfin, nous détaillons deux adaptations de l'algorithme de reconnaissance de motifs similaires à des applications particulières. La première concerne la reconnaissance d'objets extraits de la video basse résolution pour l'indexation grossière. La deuxième application a été développée pour la visualisation de l'évolution de projets logiciels.

Le sujet de cette thèse se divise en trois parties: les deux premières traitent chacune d'une extension du modèle utilisé en théorie des automates, tandis que la dernière aborde une partie plus concrète qui consiste à générer des automates avec des propriétés particulières. Tout d'abord, nous donnons une extension du concept d'automate universel, défini sur les mots finis, aux omega-langages. Pour cela, nous avons défini une forme normale pour tenir compte de la spécificité du mode d'acceptation des automates de Büchi qui nous permettent de reconnaître les omega-langages. Ensuite nous avons défini deux types d'omega-factorisations, "classiques" et "pures", qui sont des extensions du concept de factorisation d'un langage, ce qui nous a permis de définir l'automate universel d'un omega-langage. Nous avons prouvé que ce dernier dispose bien des différentes propriétés attendues: il est le plus petit automate de Büchi reconnaissant l'omega-langage et qui possède la propriété d'universalité (moyennant la forme normale). Nous présentons également une méthode pour calculer efficacement les omega-factorisations maximales d'un langage à partir d'un automate prophétique reconnaissant le dit langage. Dans la seconde partie, nous traitons le cas des automates bidirectionnels à multiplicité dans un semi-anneau. Dans un premier temps, nous donnons une version légérement différente de la construction permettant de passer d'un automate bidirectionnel à multiplicité à un automate unidirectionnel à multiplicité et nous prouvons qu'elle préserve la non-ambiguïté mais pas le déterminisme. Nous montrons, également à l'aide d'une construction, que les automates bidirectionnels à multiplicité non-ambigus sont équivalents aux automates unidirectionnels à multiplicité déterministes. Dans un second temps, nous nous concentrons sur les semi-anneaux tropicaux (ou min-+). Nous montrons que sur N-min-+, les automates bidirectionnels sont équivalents aux automates unidirectionnels. Nous montrons également que sur Z-min-+, les automates bidirectionnels n'ont pas toujours un comportement défini et que cette propriété est décidable tandis qu'il n'est pas décidable s'il existe un mot pour lequel le comportement est défini. Dans la dernière partie, nous proposons un algorithme de génération aléatoire d'automate acycliques, accessibles et déterministes ainsi que d'automates acycliques minimaux avec une distribution qui est quasiment uniforme, tout cela à l'aide de chaîne de Markov. Nous prouvons l'exactitude de chacun de ces deux algorithmes et nous expliquons comment adapter en tenant compte de contraintes sur l'ensemble des états finals / The subject of this thesis is decided into three parts: two of them are about extensions of the classical model in automata theory, whereas the third one is about a more concrete aspect which consists in randomly generate automata with specific properties. We first give an extension of the universal automaton on finite words to infinite words. To achieve this, we define a normal form in order to take account of the specific acceptance mode of Büchi automata which recognize omega-langages. Then we define two kinds of omega-factorizations, a "regular" one and the "pure" kind, which are both extensions of the classical concept of factorization of a language. This let us define the universal automaton of an omega-language. We prove that it has all the required properties: it is the smallest Buchi automaton, in normal form, that recognizes the omega-language and which has the universal property. We also give an effective way to compute the "regular" omega-factorizations of a language using a prophetic automaton recognizing the language. In the second part, we deal with two-way automata weighted over a semi ring. First, we give a slightly different version of the computation of a weighted one-way automaton from a weighted two-way automaton and we prove that it preserves the non-ambiguity but not the determinism. We prove that non-ambiguous weighted two-way automata are equivalent to deterministic weighted one-way automata. In a later part, we focus on tropical semi rings (or min-+). We prove that two-way automata on N-min-+ are equivalent to one-way automata on N-min-+. We also prove that the behavior of two-way automata on Z-min-+ are not always defined and that this property is decidable whereas it is undecidable whether or not there exists a word on which the behavior is defined. In the last section, we propose an algorithm in order to randomly generate acyclic, accessible and determinist automata and minimal acyclic automata with an almost uniform distribution using Morkov chains. We prove the reliability of both algorithms and we explain how to adapt them in order to fit with constraints on the set of final states

Les réaliseurs, ou arbres de Schnyder, ont été introduits par Walter Schnyder à la fin des années 80 pour caractériser les graphes planaires, puis pour dessiner ces mêmes graphes sur des grilles $(n-2)\times(n-2)$.<br>Dans ce document nous proposons dans un premier temps une extension du théorème de Wagner aux réaliseurs, qui nous permet d'établir une relation entre le nombre de feuilles et le nombre de faces tricolores d'un réaliseur.<br>Ensuite, à l'aide d'une bijection entre les réaliseurs et les paires de chemins de Dyck qui ne se coupent pas, nous énumérons les réaliseurs. Un algorithme de génération aléatoire de $p$ chemins de Dyck ne se coupant pas, est également présenté. Il permet en outre de générer aléatoirement des réaliseurs en temps linéaire.<br>Puis nous montrons que grâce aux réaliseurs, il est possible de dessiner, à l'aide de lignes brisées des graphes planaires sur des grilles de largeur et de surface optimales.<br>Enfin, nous proposons une généralisation des réaliseurs minimaux aux graphes planaires connexes : les arbres recouvrants bien-ordonnés. Grâce à cette généralisation ainsi qu'à une méthode de triangulation adaptée nous proposons un algorithme de codage des graphes planaires à $n$ sommets en $5,007n$ bits.

Nous étudions le problème de maintenir une distribution donnée de graphes aléatoires après une séquence arbitraire d’insertions et de suppressions de sommets. Dans l’objectif de modéliser l’évolution de réseaux logiques dynamiques,nous travaillons dans un modèle local où l’accès à la liste des sommets est restreint. À la place, nous faisons l’hypothèse d’un accès à une primitive globale qui retourne un sommet aléatoire, choisi uniformément dans l’ensemble total des sommets. Le problème de maintenance a été exploré sur plusieurs modèles simples de graphes aléatoires (graphes d’Erdos–Rényi, graphes basés sur le modèle par paires, graphes k-sortants uniformes). Pour chacun des modèles, un ou plusieurs algorithmes pour la tâche de maintenance ont été décris et analysés ; les plus élaborés de ces algorithmes sont asymptotiquement optimaux. Le problème de maintenance soulève plusieurs problèmes de simulation liés à notre contexte distribué. Nous nous sommes intéressé en particulier à la maintenabilité de distributions de graphes et à la simulabilité de familles de distributions de probabilité sur les entiers, dans le modèle d’aléa présenté.Une attention particulière a été portée sur la simulation efficace de lois spécifiques nous intéressant (certaines lois binomiales). Cette dernière a pu être obtenue en exploitant les propriétés d’un nouvel arbre de génération pour les permutations, que nous avons introduit. / We study the problem of maintaining a given distribution of randomgraphs under an arbitrary sequence of vertex insertions and deletions. Keeping inmind our objective to model the evolution of dynamic logical networks, we work ina local model where we do not have direct access to the list of all vertices. Instead,we assume access to a global primitive that returns a random vertex, chosen uniformlyfrom the whole vertex set. The maintenance problem has been explored onseveral simple random graph models (Erdos–Rényi random graphs, pairing modelbased random graphs, uniform k-out graphs). For each model, one or several updatealgorithms for the maintenance task have been described and analyzed ; the mostelaborate of them are asymptically optimal. The maintenance task rise several simulationissues linked to our distributed context. In particular, we have focused onmaintenability of random graph distributions and simulability of families of probabilitydistributions over integers in our local random model. Special attention hasbeen paid to efficient simulation of particular distributions we were interested in(certain binomial distributions). The latter has been obtained through the use ofproperties of a new generation tree for permutations, which has been introducedalong the way

Avec l'augmentation de l'utilisation des smartphones, des objets connectés et des véhicules automatiques, le domaine des systèmes embarqués est devenu omniprésent dans notre environnement. Ces systèmes sont souvent contraints en terme de consommation et de taille. L'utilisation des processeurs many-cores dans des systèmes embarqués permet une conception rapide tout en respectant des contraintes temps-réels et en conservant une consommation énergétique basse.Exécuter une application sur un processeur many-core requiert un dispatching des tâches appelé problème de mapping et est connu comme étant NP-complet.Les contributions de cette thèse sont divisées en trois parties :Tout d'abord, nous étendons d'importantes propriétés dataflow au modèle Phased Computation Graph.Ensuite, nous présentons un générateur de graphe dataflow capable de générer des Synchonous Dataflow Graphs, Cyclo-Static Dataflow Graphs et Phased Computation Graphs vivant avec plus de 10000 tâches en moins de 30 secondes. Le générateur est comparé à SDF3 et PREESM.Enfin, la contribution majeure de cette thèse propose une nouvelle méthode d'évaluation d'un mapping en utilisant les modèles Synchonous Dataflow Graphe et Cyclo-Static Dataflow Graphe. La méthode évalue efficacement la mémoire consommée par les communications d'un dataflow mappé sur une architecture à mémoire distribuée. L'évaluation est déclinée en deux versions, la première garantit la vivacité alors que la seconde ajoute une contrainte de débit. La méthode d'évaluation est expérimentée avec des dataflow générés par Turbine et avec des applications réelles. / With the increasing use of smart-phones, connected objects or automated vehicles, embedded systems have become ubiquitous in our living environment. These systems are often highly constrained in terms of power consumption and size. They are more and more implemented with many-core processor array that allow, rapid design to meet stringent real-time constraints while operating at relatively low frequency, with reduced power consumption.Running an application on a processor array requires dispatching its tasks on the processors in order to meet capacity and performance constraints. This mapping problem is known to be NP-complete.The contributions of this thesis are threefold:First we extend important notions from the Cyclo-Static Dataflow Graph to the Phased Computation Graph model and two equivalent sufficient conditions of liveness.Second, we present a random dataflow graph generator able to generate Synchonous Dataflow Graphs, Cyclo-Static Dataflow Graphs and Phased Computation Graphs. The Generator, is able to generate live dataflow of up to 10,000 tasks in less than 30 seconds. It is compared with SDF3 and PREESM.Third and most important, we propose a new method of evaluation of a mapping using the Synchonous Dataflow Graph and the Cyclo-Static Dataflow Graph models. The method evaluates efficiently the memory footprint of the communications of a dataflow graph mapped on a distributed architecture. The evaluation is declined in two versions, the first guarantees a live mapping while the second accounts for a constraint on throughput.The evaluation method is experimented on dataflow graphs from Turbine and on real-life applications.

Le concept d’automate, central en théorie des langages, est l’outil d’appréhension naturel et efficace de nombreux problèmes concrets. L’usage intensif des automates finis dans un cadre algorithmique s ’illustre par de nombreux travaux de recherche. La correction et l’ évaluation sont les deux questions fondamentales de l’algorithmique. Une méthode classique d’ évaluation s’appuie sur la génération aléatoire contrôlée d’instances d’entrée. Les travaux d´écrits dans cette thèse s’inscrivent dans ce cadre et plus particulièrement dans le domaine de la génération aléatoire uniforme d’automates finis.L’exposé qui suit propose d’abord la construction d’un générateur aléatoire d’automates à pile déterministes, real time. Cette construction s’appuie sur la méthode symbolique. Des résultats théoriques et une étude expérimentale sont exposés.Un générateur aléatoire d’automates non-déterministes illustre ensuite la souplesse d’utilisation de la méthode de Monte-Carlo par Chaînes de Markov (MCMC) ainsi que la mise en œuvre de l’algorithme de Metropolis - Hastings pour l’ échantillonnage à isomorphisme près. Un résultat sur le temps de mélange est donné dans le cadre général .L’ échantillonnage par méthode MCMC pose le problème de l’évaluation du temps de mélange dans la chaîne. En s’inspirant de travaux antérieurs pour construire un générateur d’automates partiellement ordonnés, on montre comment différents outils statistiques permettent de s’attaquer à ce problème. / The concept of automata, central to language theory, is the natural and efficient tool to apprehendvarious practical problems.The intensive use of finite automata in an algorithmic framework is illustrated by numerous researchworks.The correctness and the evaluation of performance are the two fundamental issues of algorithmics.A classic method to evaluate an algorithm is based on the controlled random generation of inputs.The work described in this thesis lies within this context and more specifically in the field of theuniform random generation of finite automata.The following presentation first proposes to design a deterministic, real time, pushdown automatagenerator. This design builds on the symbolic method. Theoretical results and an experimental studyare given.This design builds on the symbolic method. Theoretical results and an experimental study are given.A random generator of non deterministic automata then illustrates the flexibility of the Markov ChainMonte Carlo methods (MCMC) as well as the implementation of the Metropolis-Hastings algorithm tosample up to isomorphism. A result about the mixing time in the general framework is given.The MCMC sampling methods raise the problem of the mixing time in the chain. By drawing on worksalready completed to design a random generator of partially ordered automata, this work shows howvarious statistical tools can form a basis to address this issue.