Approches dynamiques des Codes identifiants – IDEA

Les problèmes de reconstruction sont centraux en combinatoire. Nous pouvons par exemple mentionner la question de déterminer, parmi un ensemble de vecteurs binaires, un sous-ensemble minimal dont la somme (ou exclusif) est égale à un vecteur donné. Dans le cadre de la théorie des codes correcteurs d'erreurs, cette question est équivalente au problème de décodage. Considérons maintenant le problème analogue de reconstruction d'un ensemble de vecteurs dont la somme (ou inclusif) est égale à un vecteur donné. En terme d'ensembles, il s'agit de reconstruire une collection de sous-ensembles d'un ensemble donné à partir de leur union. Ce problème possède un grand nombre d'applications dans différent domaine : tatouage numérique, tests groupés (dans lesquelles des échantillons sont testés en pools, et où le but est de déterminer les échantillons ayant une propriété donnée). Les familles de sous-ensembles ayant de telles propriétés de reconstruction sont connues sous la dénomination de codes superimposés, et ont été étudiés dans différentes communautés, parfois de façon indépendante. Nous nous intéressons au cas où l'ensemble considéré a des propriétés structurelles additionnelles, dans le sens où c'est l'ensemble des sommets d'un certain graphe. Sélectionnons un certain sous-ensemble de ces sommets, qui va jouer un rôle particulier, et que nous appelons code. Considérons alors la collection formée des voisins de sommets du code. Un tel code ayant les propriétés de reconstruction susmentionnées est appelé un code identifiant. Cette notion a été introduite en 1998 par Karpovsky et al. afin de modéliser un problème de détection de défaillances dans des réseaux multiprocesseurs. Dans ce cadre, on suppose que chacun des processeurs du sous-ensemble correspondant au code a la capacité de tester si il y a un processeur défectueux dans son voisinage. L'objectif est de déterminer l'ensemble des processeurs défectueux (ou de certifier qu'aucun processeur ne l'est) à partir des réponses fournies par les processeurs du code. Les liens avec la théorie des codes superimposés a été établi récemment, et donne des perspectives pour des développements futurs ainsi que pour des applications nouvelles. Ce problème relève clairement de la théorie des graphes, qui paraît donc naturellement être un outil approprié pour étudier ces codes. Ses liens avec les codes superimposés suggèrent de plus que les techniques spécifiques de la théorie des codes peuvent être pertinentes pour explorer ces questions, et donner des persectives originales sur le problème. Nos objectifs concernent l'investigation de versions dynamiques de ces codes, et ce selon deux angles. Premièrement, nous allons supposer que le graphe est donné de façon dynamique, et nous allons construire un code identifiant efficient étape par étape, au fur et à mesure que le graphe nous est donné. Cette approche est complètement nouvelle dans le cadre des codes identifiants, et semble de plus particulièrement pertinente dans des perspectives applicatives (concernant les graphes scale-free). L'aspect dynamique prend en particulier en compte l'ajout ou la suppression de sommets ou d'arêtes, et conduit alors à l'étude de la robustesse des codes vis-à-vis des changements de structures. Deuxièmement, nous allons développer une approche adaptative de ces codes, dans le sens où les sommets peuvent être testés séquentiellement, et où la séquence de sommets à interroger va être construite au fur et à mesure, en fonction des réponses des sommets déjà interrogés. Ceci conduit à la détermination d'une stratégie d'identification, et donc à un arbre de décision, plutôt qu'à la détermination d'un code statique. Nous nous intéresserons à des questions structurelles aussi bien qu'algorithmiques (complexité et détermination d'algorithmes efficaces). Le développement d'outils appropriés passera par l'étude de versions statiques de ces codes dans versions généralisées.