Combinatoire et Algorithmique
Responsable : J.-F. MarckertMembres

La combinatoire a pour objet l'étude des structures discrètes. Celles-ci apparaissent dans toutes les sciences : en biologie, en mathématiques, en physique et bien sûr, en informatique, où elles jouent un rôle particulier ; en effet, les ordinateurs travaillent avec des objets discrets uniquement.

Ainsi, l'arborescence des fichiers dans un ordinateur, une structure de données, le codage d'un brin d'ADN, un réseau informatique, sont des objets combinatoires : des arbres, des tableaux, des mots, des graphes.

L'équipe de Combinatoire et Algorithmique s'emploie à comprendre, décrire et parfois définir ces structures. Elle contribue également à inventer, analyser et optimiser les algorithmes qui travaillent sur ces objets. Parmi ses spécialités, il y a l'énumération de structures, l'étude des graphes et l'algorithmique distribuée.


Thèmes de recherche:

  • Combinatoire énumérative et algébrique
    • Responsable : P. Duchon.
    • Mots clés : énumération, lois limites, génération aléatoire ou exhaustive, arbres, cartes, chemins, permutations,tas de sable, structures aléatoires.
  • Graphes et optimisation
    • Responsable : F. Kardoš.
    • Mots clés : codage, coloration, coloration par listes, étiquetage, homomorphisme, optimisation combinatoire, polytopes, propriétés structurelles, routage dans les réseaux, structures de données compactes.
  • Algorithmique distribuée
    • Responsable : A. Zemmari
    • Mots clés : calculs locaux, élection, détection de terminaison, reconnaissance, fibration, revêtement, algorithme probabiliste, systèmes agents mobiles, tolérance aux fautes, autostabilisation, réseaux pair-à-pair, circulation de jeton, modèle de communication, réseaux dynamiques.