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 4 Novembre 2008

Pavages auto-assemblants et géométrie

par Florent Becker (LIP, Lyon)

Dans la nature, le phénomène d'auto-assemblage est omni-présent: de « petites » entités interagissent, s'agrègent et forme des structures complexes, avec une forme et une fonction « intéressante ». Dans les années 90, une équipe de l'université de Standford, autour d'Erik Winfree, Ned Seeman et Leonard Adleman ont tenté d'utiliser des molécules d'ADN ayant la faculté de s'auto-assembler pour exécuter des algorithmes.

Je présenterai leur démarche, et le modèle théorique qui en découle, celui des pavages auto-assemblants, une variante des pavages de Wang. Ce modèle constitue un modèle de calcul original, que l'on pourrait comparer à des automates cellulaires en 1.5 dimensions. Je montrerai comment calculer avec ces objets, au niveau microscopique.

Malheureusement, le calcul avec ces objets tel qu'il était présenté traditionnellement se fait à très bas niveau, et il faut concevoir (et prouver !) des systèmes à partir des interactions microscopiques. Pour relever ce défi, je donnerai des pistes vers un langage de programmation adapté à l'auto-assemblage. Pour cela, nous verrons que la géométrie, qui est un peu oubliée dans l'approche classique, joue un rôle crucial.

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