Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 03 novembre 2009 à 14h en B311, Julien David nous parlera de : Analyse de la complexité moyenne de l'algorithme de Moore

Résumé : Dans un premier temps, on présentera une méthode de génération aléatoire d’automates déterministes accessibles complets et un outil, REGAL, utilisant cette méthode. Les générateurs implantés dans REGAL permettent d’engendrer des automates de plusieurs milliers d’états et ce faisant, d’établir des conjectures crédibles sur les propriétés en moyenne des automates, ainsi que sur les algorithmes qui s’y appliquent. Dans une deuxième partie, on présentera un résultat théorique sur la complexité moyenne de l’algorithme de Moore: si la complexité dans le pire cas de l’algorithme est connu pour être en $\mathcal{O}(n^2)$, on montrera que pour un alphabet fini arbitraire et la distribution uniforme sur l’ensemble des automates déterministes accessibles complets n états, la complexité moyenne est $\mathcal{O}(n\log n)$.


Dernière modification : mercredi 06 juillet 2011 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr