Valérie Girardin

Séminaire et groupe de travail



 

  Co-organisatrice, avec Guy Laville, du séminaire

    Analyse et physique mathématique

La page du séminaire est  ici. 

 

  Co-organisatrice, avec Brigitte Vallée, du groupe de travail apériodique 

      Entropie, mots, stat 



Le groupe de travail réunit depuis 2007 des collègues de mathématiques, d'informatique et de théorie du signal de l'UNICAEN, de l'ENSICAEN, de l'ESIEE Marne-la-Vallée, du GIPSA-Lab Grenoble, et des Universités de Paris Ouest, Reims-Champagne-Ardennes et Rouen. Les journées de printemps, d'automne et d'hiver accueillent également des exposés invités.

Journées de printemps du GT


Les exposés auront lieu à l'université de Reims Champagne Ardennes, en salle de séminaire du département MMI, bâtiment 3, campus Moulin de la Housse.
 


Jeudi 11 mai :

14h30 - 15h30 -- Aldric Degorre  (IRIF, Paris 7)
Entropie des langages temporisés réguliers

Les automates temporisés (Alur & Dill 1990) sont une extension des automates finis très populaire pour modéliser les systèmes temps réel dans le domaine de la vérification de logiciel.
Dans cet exposé, nous étudions la "taille" du langage des automates temporisés, généralisant une approche classique introduite par Chomsky et Miller pour les automates finis : compter les mots de n symboles et calculer la vitesse de croissance exponentielle de leur nombre, c'est à dire l'entropie du langage.
Pour les automates temporisés, nous remplaçons la cardinalité par le volume et définissons l'entropie (volumétrique) de façon similaire. Elle représente la quantité moyenne d'information par évènement dans un mot temporisé du langage.
Nous décrivons plusieurs techniques pour approcher ce nombre pour un automate donné.
Une technique consiste à discrétiser les comportements d'un automate afin de réduire ce problème au calcul de l'entropie d'un automate fini.
Une autre technique consiste à associer à chaque automate temporisé un opérateur intégral positif dont le logarithme du rayon spectral se trouve être égal à l'entropie. Ainsi des procédures numériques à convergence rapide peuvent être utilisées pour approcher ce nombre. Enfin, nous mettons en évidence un cas particulier dans lequel l'entropie peut même être caractérisée de façon symbolique.

15h30 - 16h30 -- Frédéric Paccaut (LAMFA, Amiens)
g-mesures et mesures de Gibbs : quelles différences ?

Il sera question de g-mesures (processus défini par ses transitions par rapport au passé) et mesures de Gibbs unidimensionnelles (processus défini par ses transitions par rapport au passé et au futur). Peut-on les comparer ? L'intérêt se portera plus particulièrement sur le cas où les transitions ne sont pas continues (aussi bien dans un cas que dans l'autre).

17h - 18h -- Brigitte Vallée / Dimitri Darthenay (GREYC, Caen)
Analyse fine de la Sélection Dichotomique

D'apès un travail commun avec Julien Clément, Dimitri Darthenay, Loïck Lhote, Brigitte Vallée

Considérons un système dynamique binaire B de l'intervalle [0, 1] avec   ses intervalles fondamentaux de profondeur p inférieure à L,   et l'arbre binaire associé complet de hauteur L. 
L'algorithme   Dicho détermine  les L premiers symboles de l'écriture  b(x) d'un réel  x de [0,  1]  en base b en  adoptant le  principe  dichotomique, qui définit un chemin dans l'arbre T avec ses noeuds w et  effectue exactement L comparaisons entre nombres réels, une comparaison entre x et chaque point w du chemin. 
On suppose maintenant qu'on dispose  d'un (autre) système dynamique D de l'intervalle [0, 1] (non nécessairement binaire).   On suppose qu'on connait,  (dans le système dynamique D),  l'écriture  D(x)  du réel x   en même temps que l'écriture des  extrémités  des intervalles fondamentaux  de profondeur p du système B. Grâce à la stratégie dichotomique,  qui détermine  une branche de l'arbre T avec ses noeuds  w, on   peut déterminer  les L premiers symboles de l'écriture  B(x) de x en base b, en comparant  cette fois-ci  le mot D(x)  avec  les mots  D(w) (dans l'ordre lexicographique). 
Le coût d'une comparaison entre  deux mots  D(x) et D(w) est alors le nombre de symboles utilisés dans la comparaison,  égal  à 1 + C(D(x), D(w)), où la coincidence  C(X, Y) entre deux mots X, Y est la longueur du plus grand commun préfixe à ces deux mots.
La complexité de l'algorithme sur l'entrée x est  alors égale au nombre de symboles comparés. 
On  veut  décrire la complexité moyenne de l'algorithme  Dicho quand le réel x est  choisi aléatoirement dans [0, 1] et donné  par son écriture  D(x) dans le système dynamique D de l'intervalle [0, 1]. Un résultat  de la théorie de l'information, lié  la version  ergodique du théorème de Shannon-MacMillan-Breimann, énonce que pour déterminer L symboles de l'écriture  B(x) en base b de x,il faut  un nombre de  symboles de D(x) asymptotiquement égal à L rho(b)} /rho(D)  et fait intervenir les entropies rho(B) et   rho(D) des deux systèmes (pourvu que les deux systèmes dynamiques jouissent de bonnes propriétés). 
Ce résultat  donne ainsi  donc une borne inférieure  pour la complexité d'un algorithme de ``changement de base''. 
Nous montrons qu'une version naïve de  l'algorithme  Dicho a une complexité moyenne  asymptotique à   (1/2) L.L rho(b)} /rho(D), avec une étude précise du terme de reste.  Dans cette version naïve,  une comparaison entre  les mots D(x) et  D(w)  n'utilise pas les comparaisons qui ont déjà été effectuées entre D(x) et les mots ``parents'' D(w-) et D(w+) de w. 
Une version moins naïve de l'algorithme mémorise  ces comparaisons précédentes, il paraît beaucoup plus efficace, mais son analyse est en cours.   
Les deux analyses utilisent des résultats  fins  sur les systèmes dynamiques: 
la loi log-normale  des longueurs des intervalles fondamentaux, et la ``probabilité des préfixes probables''.

Vendredi 12 mai :

10h - 11h -- Charles Tillier (Modal'X, Paris 10)
Etude du comportement extrémal de processus stochastiques en théorie du risque

L'analyse des risques est devenu un enjeu majeur dans notre société. Quels que soient les champs d'application dans lesquels une situation à risque peut survenir, les mathématiques et plus particulièrement les statistiques et les probabilités se révèlent être des outils essentiels. La théorie du risque se situe entre l'analyse des valeurs extrêmes et la théorie des variables aléatoires à variations régulières ou à queues lourdes. Dans cette exposé, j'étudierai le comportement extrémal de processus intervenant en théorie du risque - les processus type Shot Noise - à travers leur queue de distribution ainsi que leur indice extrémal. Ce dernier jouant un rôle prépondérant dans l'évaluation des risques car il mesure, en moyenne, la tendance avec laquelle les valeurs extrêmes se "clesteurisent". Je motiverai ma présentation sur des applications en risque alimentaire et en assurance. 

11h - 12h -- Amor Keziou (LMR, Reims)
Séparation aveugle de sources dépendantes

La séparation aveugle de sources (SAS) est une technique du traitement statistique du signal. Les signaux observés sont des mélanges (inconnus) de signaux inobservables, appelés sources. La SAS vise à reconstituer les signaux sources à partir des signaux observés, qui sont des mélanges inconnus de sources inconnues. 
Sous l'hypothèse fondamentale d'indépendance statistique des sources, plusieurs méthodes ont été proposées dans la littérature. Nous montrons, dans cet exposé, que la séparation de sources dépendantes est possible, et nous proposons une méthode de SAS par minimisation de l'information mutuelle entre copules. La méthode est illustrée sur des exemples de signaux aléatoires simulés, des images et des signaux texte.
 









haut de page