Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2017-06-16  10:45-11:45
TitreCalculer l'entropie des pavages mélangeants 
RésuméLes pavages (ou sous-décalages) correspondent à des assignations d'états à chaque sommet d'une grille Z^d soumises à des contraintes locales. L'entropie d'un espace de pavage est un paramètre pertinent pour diverses communautés : en théorie de l'information (d=1), comme capacité d'un canal de communication ; en mathématiques, comme principal invariant de conjugaison ; en physique statistique (d=2 ou 3), comme entropie thermodynamique du système modélisé. Est-il possible de calculer (algorithmiquement) l'entropie d'un espace de pavages défini par des contraintes fournies en entrée ? Pour des contraintes en nombre fini (pavage de type fini) et en dimension 1, l'entropie est calculable par une méthode algébrique classique. Le cas de la dimension supérieure s'est révélé beaucoup plus difficile, l'entropie de beaucoup d'exemples simples étant encore indéterminée. En 2007, il a été prouvé que l'entropie en dimension 2 n'est pas calculable en général. Des travaux plus récents ont montré que l'entropie redevient calculable sous des hypothèses de mélange, c'est-à-dire d'indépendance des motifs situés à une certaine distance. Où se situe la limite entre les cas calculable et incalculable ? En introduisant une notion de taux de mélange, nous montrons l'existence d'un seuil en fonction de ce taux où la difficulté du problème passe de calculable à incalculable, sans pouvoir le déterminer exactement. Pour une famille plus large de pavages soumis à un nombre infini de contraintes, nous parvenons à déterminer exactement le seuil correspondant, et conjecturons que sa position est la même dans le cas fini. Ces travaux sont en collaboration avec Silvère Gangloff.  
Lieu076 
OrateurBenjamin Hellouin de Menibus 
Emailbenjamin.hellouin@gmail.com 
Urléquipe Automates et applications à l'Institut de Recherche en Informatique Fondamentale (IRIF) de l'université Paris-Diderot 



Aucun document lié à cet événement.

Retour
Retour à l'index