Journées GT Entropie

Jeudi 17 novembre

• 14h30 Cédric Lecouvey, Université de Tours, « Quelques interactions entre la théorie des représentations et l’étude de marches aléatoires dans des réseaux ou des alcôves »

Résumé : De nombreux exemples de marches aléatoires conditionnées à rester dans un cône sont contrôlés par des structures algébriques issues de la théorie des représentations et de la combinatoire des systèmes de racines. Le but de l’exposé sera de proposer une introduction à cette classe de problèmes et de montrer comment la notion de graphe multiplicatif y joue un rôle central en lien avec des problèmes géométriques de grande complexité.

• 15h30 Martin Pépin, Université Sorbonne Paris-Nord, « Énumération et génération aléatoire des graphes dirigés ordonnés sans cycles et liens avec les DAGs étiquetés »

Résumé : Les graphes dirigés sans cycles (ou DAGs pour “Directed Acyclic Graphs” en anglais) sont des graphes dirigés dans lesquels il n’y a aucun chemin d’arêtes d’un sommet vers lui même. Il s’agit d’une structure de données omniprésente en informatique dont le problème du comptage par nombre de sommets a été résolu par Robinson dans les années 1970. Afin de contrôler la densité de ces graphes, il est utile de fixer aussi leur d’arêtes. Cependant, l’approche Robinson (étendue par Gessel dans les années 1990) amène à des formules de récurrence faisant apparaître le principe d’inclusion-exclusion, qui se prête mal à la génération aléatoire (efficace) par les méthodes classiques.

Dans cet exposé je présenterai deux contributions. D’abord nous étudierons une nouvelle classe de DAGs (les DOAGs), enrichie avec un ordre sur les arêtes sortantes de chaque sommet, offrant un nouvel outil de modélisation. Pour cette classe nous obtenons une décomposition récursive amenant à des algorithmes de génération aléatoire efficaces ainsi qu’un équivalent asymptotique dans le cas dense. Ensuite je montrerai comment l’approche utilisée pour cette nouvelle classe peut-être utilisée dans le cadres des DAGs classiques pour obtenir de nouvelles relations de récurrence, cette fois sans inclusion-exclusion. Une conséquence de ce résultat est l’obtention d’un algorithme de génération aléatoire efficace à nombre de sommets et arêtes fixés pour les DAGs.

• 16h30 Pause
• 17h Lala Maghnia Moali, Université de Caen, « Monotonie et comparabilité du réseau de files d’attente [M2/G2/1 –> ./G/1/1] avec priorité relative »

La difficulté d’étudier les propriétés des flux inter-stations rend l’obtention de résultats de performance explicites, pour la plupart des réseaux de files d’attente, une tâche quasiment impossible. Pour palier ces difficultés, plusieurs chercheurs ont développé des approches de substitution d’un réseau compliqué par un autre plus simple qui lui soit le plus proche possible et pour lequel des résultats analytiques existent. Les méthodes de bornes stochastiques s’appliquent aux chaînes de Markov multidimensionnelles, et permettent ainsi d’apporter des solutions intéressantes pour l’évaluation des performances des systèmes complexes.

Dans ce travail, nous nous sommes focalisés sur l’application des méthodes de comparaison stochastique pour l’étude des propriétés de monotonie et de comparabilité d’un réseau de files d’attente avec priorité relative. Nous avons dérivé différentes inégalités stochastiques par rapport aux ordres stochastique et convexe, qui assurent la monotonie de l’opérateur de transition associé à la chaîne de Markov induite. Les inégalités stochastiques obtenues fournissent des bornes simples pour la distribution stationnaire des chaînes de Markov induites liées au modèle d’attente étudié.

Vendredi 18 novembre

• 10h15 café
• 10h30 Amor Keziou, Université de Reims « Vraisemblance empirique robuste »

Résumé : Nous proposons une version robuste de la méthode de vraisemblance empirique, dans des modèles semi-paramétriques, par minimisation de la divergence de Kullback-Leibler entre la mesure empirique et des ensembles de lois de probabilités vérifiant des contraintes définies par des fonctions d’orthogonalité tronquées.

11h25-12h20 Théo Grente, France Energies Marines, Caen, « Grammaires conjonctives, automates cellulaires et logique »

Les grammaires conjonctives sont une extension des grammaires algébriques avec une opération de conjonction. Leur pouvoir expressif (même sur un alphabet unaire) est largement inconnu. Le but de cet exposé est de prouver l’inclusion des langages conjonctifs dans une des classes de complexité des automates cellulaires (AC), un modèle de calcul parallèle et local. En effet, lorsqu’on restreint le temps, l’espace ou même la communication, les AC peuvent agir comme des reconnaisseurs de langages définissant des classes de complexité.

La preuve présentée dans cet exposé utilise une méthode de programmation qui repose sur des caractérisations exactes des classes de complexité intéressantes de l’AC par des sous-logiques ESO (logique existentielle du second ordre) avec des formules de Horn comme partie du premier ordre.

En utilisant cette méthode, il suffit de définir des grammaires conjonctives dans notre logique pour obtenir naturellement un résultat d’inclusion.