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 7 Février 2017

Entropie des pavages mélangeants

par Benjamin Hellouin (IRIF, Paris 7)

L'entropie est un paramètre réel capturant une notion de complexité d'un système, avec de nombreuses applications en mathématiques et en informatique. La question de notre capacité à calculer (par un algorithme) la valeur de ce paramètre a été étudiée sur de nombreux systèmes. J'étudie ce problème dans le cas des pavages (ou sous-décalages), i.e. des colorations du plan (de l'espace) soumis à des contraintes.

Quand les contraintes sont en nombre fini (pavage de type fini), l'entropie est calculable en dimension 1 par une méthode algébrique classique. Le cas de la dimension 2 s'est révélé beaucoup plus difficile, l'entropie de beaucoup d'exemples simples étant encore inconnue. En 2007, il a été prouvé que l'entropie en dimension 2 n'est pas calculable en général.

Cependant, des travaux plus récents ont montré que l'entropie redevient calculable sous des hypothèses supplémentaires : des hypothèses de mélange, c'est-à-dire d'indépendance des motifs situés à une certaine distance. Cependant, nous ne savons pas encore la limite exacte entre les mondes calculable et incalculable.

Dans cet exposé, je parlerai de nos travaux sur les pavages soumis à un nombre potentiellement infini de contraintes. Dans ce contexte, nous montrons l'existence d'un seuil de difficulté (correspondant à un taux de mélange limite) au-delà duquel l'entropie passe du calculable à l'incalculable - exactement le résultat conjecturé dans le cas de type fini.

Ces travaux sont en collaboration avec Silvère Gangloff et Cristobal Rojas.

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