[CoA 2014] Pierre-Étienne Meunier

troisièmes journées du GT CoA Complexité et Algorithmes :
Algorithmes naturels
du mercredi 10 septembre 12h30 au vendredi 12 septembre 13h30, Université Paris Diderot
LIAFA, Salle 1009, Bâtiment Sophie Germain Paris 13ème

15:45-16:45 - Exposé invité n°5 : Pierre-Étienne MEUNIER (U. Aalto)
Non-cooperative self-assembly : A geometric pumping lemma

L'auto-assemblage est le mécanisme par lequel des entités atomiques se composent pour former de grandes molécules complexes. Un modèle de ce phénomène est dérivé des tuiles de Wang : on représente les molécules élémentaires par des tuiles, qui viennent s'assembler à une structure existante suivant une condition de couleurs sur les côtés des tuiles.
Le modèle non-coopératif de l'auto-assemblage est un modèle où cette condition est très faible : les tuiles peuvent s'assembler dès lors qu'au moins un des côtés est de la bonne couleur. Malgré la simplicité de sa définition, c'est l'un des modèles les moins bien compris d'auto-assemblage.
Les résultats présentés dans cet exposé montreront l'existence de constructions algorithmiques efficaces, un résultat qui a longtemps été cru impossible. Malgré ces constructions, nous verrons aussi pourquoi ce modèle ne peut pas faire de calcul Turing arbitraires (en deux dimensions), alors que sa variante en trois dimensions en est capable.