|
|
Combinatoire et Algorithmique
| Responsable : R. Klasing |  |
L'informatique définit, étudie et manipule des structures finies ou discrètes à travers des algorithmes. Un cadre formel naturel et important pour abriter cette activité est la combinatoire. Ainsi la recherche conduite au sein de cette équipe mêle étroitement l'informatique et la combinatoire : beaucoup d'algorithmes et les analyses ou les preuves associées utilisent des objets, des constructions et des analyses combinatoires et en retour sont à l'origine de problèmes combinatoires nouveaux.
Parmi les objets ou les structures les plus utilisés, on peut citer les mots, les arbres, les graphes, les cartes, les chemins, les permutations, les partitions et les séries génératrices.
Les exemples classiques d'opérations ou de manipulations définies ou étudiées sont : les bijections, les codages, l'énumération, la génération aléatoire, les dessins (la visualisation), le coloriage et plus généralement le ré-étiquetage.
La recherche d'algorithmes, c'est à dire de procédures effectives permettant de répondre à des questions ou bien de calculer la valeur d'une fonction en un nombre fini d'étapes, est particulièrement active autour des thèmes suivants :
- la génération aléatoire qui a pour objectif d'engendrer des objets combinatoires non pas de façon exhaustive mais selon une loi de probabilité donnée,
- le calcul formel,
- les problèmes de communication dans les réseaux d'interconnexion,
- la modélisation et l'étude de problèmes issus des systèmes distribués,
- les algorithmes probabilistes.
Les questions combinatoires suscitées par l'algorithmique peuvent être de nature différente :
- énumération et comptage d'objets permettant en particulier d'effectuer des analyses exactes et en moyenne d'algorithmes,
- représentation et manipulation efficaces d'objets mathématiques variés (graphes, nœuds, groupes, séries formelles...),
- calculs explicites sur ces objets,
- mise à jour de correspondances entre ces objets à travers des bijections,
- études purement combinatoires des propriétés de certains objets ou familles d'objets comme les mots, les arbres, les tas de sable ou bien encore les graphes.
Thèmes de recherche:
- Combinatoire énumérative et algébrique
- Responsable : J.-F. Marckert.
- Mots clés : énumération, lois limites, génération aléatoire ou exhaustive, arbres, cartes, chemins, partitions planes, permutations, invariants et co-invariants polynomiaux.
- Graphes et applications
- Responsable : A. Pêcher.
- 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 : N. Hanusse.
- 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, dynamicité dans les réseaux.
Projet:
- Equipe Projet INRIA CEPAGE
- Responsable : O. Beaumont.
- Mots clés : calcul à grande échelle, exploration de graphes, détection de pannes, modélisation, approximation topologique des distances, réseaux pair-à-pair, dynamicité dans les réseaux, ordonnancement, décomposition de graphes
|
|