Chef de l’équipe: SEMRI Ahmed – Professeur,
A. OBJECTIFS D’ENSEMBLE
On s’intéresse à la résolution de certains problèmes d’optimisation posés en Théorie des Graphes et en Géométrie Discrète. Les codes identifiants définis par M. Karpovsky, K. Chakrabarty et L. Levitin 1998 pour modéliser un problème de détection de processeurs défectueux dans des réseaux multiprocesseurs ont suscité de nombreux travaux avec à la clef des applications pratiques directes à l’instar de celle développée par une équipe de l’Université de Boston qui a utilisé les codes identifiants pour la conception de systèmes de localisation dans des environnements fermés munis de capteurs sans fil. Le problème de la détermination d’un code Identifiant de cardinalité minimum dans les espaces de Hamming qui équivaut à un problème de recouvrement d’un espace par des codes est un sujet d’actualité même si le problème est connu pour être NP‐dur. De nombreuses variantes des codes Identifiants ont été introduites depuis, tels que les a,b‐codes, les codes adaptatifs. Il s’agit aussi d’étudier ce type de codes et d’éventuellement en définir de nouveaux. Le problème d’empilement nécessitant des activités importantes en termes de modélisation, d’optimisation et de preuve nous a amenés à faire une analyse didactique de ce type de problème.
B. FONDEMENTS SCIENTIFIQUES
L’équipe se propose de développer les thèmes suivants :
- Détermination de codes optimaux sur des Structures Particulières.
- Recherche sur les problèmes d’empilement de disques égaux dans des domaines simples.
- Développement d’Ingénierie Didactique de problèmes de Mathématiques discrètes.
- Recherche autour de problèmes de coloration, de plongement et de rétracte en Théorie des Graphes.
C. MOTS‐CLÉS :
Codes, Empilement, coloration, Plongement, Graphes, Géométrie Discrète, Ingénierie Didactique.