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 5 Avril 2011

Indécidabilité, pavages et polyominos

par Nicolas Ollinger (LIF, Marseille)

Un polyomino est une figure finie simplement connexe obtenue en collant des carrés unité les uns aux autres arête à arête. Une famille de polyominos pave le plan si on peut recouvrir le plan euclidien avec des copies de ces polyominos sans chevauchement et sans trou. Dans cet exposé, on étudie le problème de décision suivant : étant donnée une famille finie de polyominos, pave-t-elle le plan ? Dans un premier temps, on redémontrera l'indécidabilité du problème à l'aide du Domino Problem, introduit par Wang en 1961. Puis, on s'intéressera à la famille de problèmes de décision indexée par la taille de la famille de polyominos et on montrera qu'il existe une frontière entre décidable et indécidable pour ce paramètre. On conclura par quelques problèmes ouverts intrigants et l'existence d'une famille de 5 polyominos qui pave le plan uniquement de manière non récursive.

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