Evènement pour le groupe Séminaire du LaBRI


Date 2009-05-14  14:00-15:00
TitreSém. LaBRI. Le problème du pavage dans le plan hyperbolique 
RésuméLe problème du pavage a été posé dans les années 50 par Hao Wang. Existe-t-il un algorithme possédant la propriété suivante : appliqué à un ensemble fini de tuiles T, l'algorithme répond "OUI" si on peut paver le plan en utilisant des copies d'éléments de T et "NON" si c'est impossible. Hao Wang démontra en 1958 qu'une version partielle du problème est indécidable. Il conjectura que le problème général, sans restriction sur l'utilisation de l'ensemble de tuiles, était décidable. Un de ses élèves, Robert Berger démontra en 1966 que le problème général était lui aussi indécidable. Il convenait de préciser dans ce qui précède que lorsqu'on parlait du plan, il s'agissait du plan euclidien. Dans une preuve restée célèbre du même problème simplifiant beaucoup celle de Berger, Raphael Robinson posa en 1971 la question suivante : "Qu'en est-il du problème du pavage en ce qui concerne le plan hyperbolique?". Robinson apporta une réponse partielle en 1978, toujous dans le sens de l'indécidabilité. Rien ne changea jusqu'en 2006 où l'auteur apporta une réponse également négative dans un cas toujours partiel mais plus général que le cas étudié par Robinson en 1978. En 2007, le problème fut résolu, indépendamment et simultanément (les approches sont très différentes) par l'auteur et Jarkko Kari, dans le sens de l'indécidabilité. La preuve de l'auteur a été publiée en 2008 dans TCS, N°407. L'exposé se propose de donner les grandes lignes de cette preuve. 
LieuAmphi LaBRI 
OrateurMaurice Margenstern 
Emailmargenstern@gmail.com 
UrlUniversité Paul Verlaine - METZ, IUT de Metz 



Aucun document lié à cet événement.

Retour
Retour à l'index