Graphes, ALgorithmes et Combinatoire (GALaC)

Le but principal de ce groupe est de concevoir, modéliser, étudier le controle et les performances des algorithmiques conçus spéficiquement pour les systèmes répartis et leurs applications. La contribution scientifique que nous visons est à la fois théorique avec le développement de nouveaux modèles mathématiques et des preuves de qualité et mais aussi bien appliquée avec le développement d’outils innovants pour différents types de réseaux (opportunistes, centrés sur le contenu ou congitifs).

Plus précisément les objectifs du group ANS (pour Algorithms for Networked systems) sont :

• D’établir des briques de bases pour la conception et l’optimisation des systèmes en réseaux. Ceci inclue la théorie du controle, la théorie des jeux, les algorithmes répartis et particulièrement l’auto-stabilisation et plus généralement la tolérance aux fautes aussi bien que la simulation de systèmes via des modèles à évenements discrets.
• De concevoir des algorithmes efficaces et des protocoles basés sur le développement des trames théoriques, d’en evaluer les performance grace à des scénarii pratiques. Ceci inclue les réseaux sans fils opportunistes (entre autre réseaux de robots, réseau sans fils ad hoc, réseaux de capteurs), les futures infrasctrutures et protocoles pour l’internet (information, Réseau centrés sur le contenus), la sécurité et la sureté dans les systemèmes cyber-physiques.

Les collaborations de cet axe prennent place sur les 5 continents.

L’intérêt principal de cette activité est l’étude des relations entre les structures algébriques et les algorithmes. Les chercheurs s’attachent particulirement aux sujets suivants:

• les structures algébriques (combinatoire des algèbres de Hopf, Opérades, Monoides, …) relatives aux algorithmes;
• la combinatoire énumérative et la dynamique symbolique.
• Les logiciels orientés objets conçus pour la modélisation des mathématiques, en particulier le développement du logiciel SageMath;

Plus précisément, les projets de recherches relèvent de la combinatoire algébrique, sont à l’interface de la combinatoire énumérative et concernent l’analyse d’algorithmes d’un point de vue des calculs symboliques et algébriques ou de calcul algébriques. Les objectifs sont doubles: d’abord, grâce à une généralisation massive de la notion de série génératrice nous espérons proposer un canevas théorique permettant l’étude du comportement fin de nombreux et différents algorithmes et ensuite et de manière réciproque l’étude des même algorithmes ouvre de nouvelles pistes pour la découverte d’objets ou d’identités algébriques d’intérêt. Ces identités ont plusieurs applications en mathématiques, en particulier dans la théorie des représentations mais aussi en physique (principalement en physique statistique).

Les recherches reposent largement sur l’expérimentation par ordinateur, il s’en suit une part importante de développement via le projet logiciel Sage-Combinat.

Cependant, le niveau de sophistication, la souplesse et la qualité des outils de calcul requis atteint un point où à grande échelle le développement collaboratif est essentiel. La conception et le développement collaboratif d’un tel logiciel soulève la recherche de qualité. Les défis sont tant du domaine de l’informatique qu’autour de la modélisation mathématique et de la gestion d’un grande hiérarchie de (orientée objet) classes, etc.

Ces questions spécifiques posent aussi de manière plus générale des questions combinatoires. Il est alors envisager un travail sur la combinatoire enumérative, les automates cellulaires en particulier les arbres.

Cet axe nourrit des collaborations régulières en France mais aussi avec l’Allemagne, l’Amérique du nord et l’Inde.

Le sujet principal est une point de vue structurel et algorithmique. L’équipe a établi une expertise comprenant les problèmes tel que trouver les grands cycles d’un graphe donné, colorier un graphe, résoudre des problèmes de couverture, ou faire avancer la théorie des graphes en trouvant les graphes extrèmes répondant à une contrainte.

La généralisation de quelques problèmes est aussi considérée pour les graphes arêtes ou sommets colorés. Par exemple, il a été étudié les graphes couvrants colorés pour des graphes arêtes ou sommets colorés. De manière alternative il a été recherche l’ensemble dominant dans un graphe ayant au moins un sommet de chaque couleur. au delà de l’intérêt purement théoriques ces démarches ont un grand intérêt aussi bien dans le domaine de la bioinformatique que dans celui du Web.

Bon nombre des questions que nous considérons peuvent aussi être déclarée en termes d’optimisation de linéaire. Ce qui ouvre des perspectives.

Nous avons de nombreuses collaborations avec les groupes français : LaBRILaboratoire Bordelais de Recherche en Informatique, LIRMMLaboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier, LIAFALaboratoire d'Informatique Algorithmique: Fondements et Applications et LIMOSLaboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes aussi bien qu’en Europe, en Amérique du nord et du sud et principalement en Asie avec la Chine, le Japan, l’Inde.