Jeudi 16 novembre 2023, 14:00 à 15:00

Damien Regnault

(IBISC, Université d'Évry Paris-Saclay)

Les pavages sont un modèle de calculs utilisant des tuiles pour former des assemblages capables de faire des calculs d'une complexité équivalente à ceux d'une machine de Turing. En tant que modèle de calcul, les pavages présentent néanmoins un défaut majeur : les tuiles doivent être placées minutieusement pour obtenir l'assemblage souhaité. Les pavages étant utilisés pour étudier des structures nanoscopiques en cristallographie ou pour modéliser l'interaction de brins d'ADN, il est nécessaire d'envisager que l'assemblage ne se déroule pas parfaitement. Nous présenterons deux approches pour gérer ce problème : l'auto-assemblage où les différences possibilités de placement des tuiles lors de l'assemblage sont prises en compte et l'auto-stabilisation où les tuiles peuvent se réorganiser localement pour corriger d'éventuelles erreurs survenues lors de leur placement.