BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20230326T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20231029T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230516T100000
DTEND;TZID=Europe/Paris:20230516T110000
DTSTAMP:20260424T150746
CREATED:20230509T112225Z
LAST-MODIFIED:20230509T112723Z
UID:11191-1684231200-1684234800@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Victor Lutfalla (GREYC\, Caen)
DESCRIPTION:Un pavage est un recouvrement du plan par des tuiles qui ne se chevauchent pas. On appelle sous-shift un ensemble de pavages qui est invariant par translation et fermé (pour la topologie habituelle sur les pavages). Ici on s’intéresse au cas où il y a un nombre fini de tuiles à translation près\, les tuiles sont des losanges\, et\, à chaque fois que deux tuiles sont adjacentes\, elles partagent soit un unique sommet en commun soit une arête entière en commun. Sur ces pavages\, on peut imposer des règles locales (à la manière des tuiles de Wang) en ajoutant des couleurs sur les arêtes des tuiles avec la règle que deux tuiles qui partagent une arête doivent avoir la même couleur pour cette arête. Dans ce cas\, pour une même tuile géométrique\, on peut avoir plusieurs copies avec des couleurs différentes sur les arêtes. \nÉtant donné un sous-shift X de pavages par losanges\, le problème du domino sur X prend en entrée un ensemble fini de règles locales F et renvoie Vrai si il existe un pavage de X qui respecte les règles locales F et Faux dans le cas contraire. Ce problème est Π01-difficile et nous allons présenter une réduction many-one depuis le problème du domino classique sur les tuiles de Wang.
URL:https://www.greyc.fr/event/seminaire-algorithmique-victor-lutflalla-greyc-caen-le-probleme-du-domino-sur-les-pavages-par-losanges/
LOCATION:Salle à déterminer
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
END:VCALENDAR