Projet ANR-08-EMER-0007 – IDEA : Approches dynamiques des Codes identifiants
Programme : domaines émergent (DEFIS) 2008
Année de financement : 2008
Coordinateur du projet : ralf KLASING (UNIVERSITE BORDEAUX I)
Partenaires : Centre national de la recherche scientifique; Université de Bordeaux
Montant : 242757.0 euros
Date de début : 2009
Durée : 36 mois
Résumé : 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