Return to search

Génération aléatoire d'automates et analyse d'algorithmes de minimisation

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

Identiferoai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00587637
Date28 September 2010
CreatorsDavid, Julien
PublisherUniversité Paris-Est
Source SetsCCSD theses-EN-ligne, France
LanguageFrench
Detected LanguageFrench
TypePhD thesis

Page generated in 0.002 seconds