Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 6 Janvier 2015

Processus stochastiques d'entropie maximale pour les automates temporisés

par Nicolas Basset (Oxford)

Nous rappelons d’abord la question que nous généraliserons par la suite au cas temporisé : Comment générer aléatoirement et de façon quasi uniforme les chemins dans un graphe? Une solution à cette question est fondée sur le processus stochastique d'entropie maximale décrit par Shannon (et connu sous le nom de mesure de Parry en dynamique symbolique et théorie ergodique). Ensuite, nous généralisons les notions de processus stochastique et d'entropie aux automates temporisés.

Nous construisons, à l'instar du cas non temporisé, un processus stochastique d'entropie maximale pour un automate temporisé, défini à l'aide des attributs spectraux (rayon spectral, fonctions propres) de l'opérateur d'Asarin et Degorre, qui est un analogue temporisé de la matrice d'adjacence d'un graphe. Ce processus permet de faire une génération aléatoire quasi-uniforme des calculs d'un automate temporisé.

En application, nous décrivons la génération aléatoire (quasi-)uniforme de permutations dont les mots (formés par les montées et descentes successives) appartiennent à un langage régulier.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr