Combinatoire et Algorithmique
Responsable : R. KlasingMembres Publications
Combinatoire et Algorithmique

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


Liste des Membres de l'équipe Combinatoire et Algorithmique


Nom-PrénomEmailTéléphoneBureauStatutWebFonction
Alexandre Fredericemail+33 (0)5 40 00 0 DR
Aval Jean-Christopheemail+33 (0)5 40 00 35 29 316 CR Correspondant BMI et SCD
Baudon Olivieremail+33 (0)5 40 00 69 21 213 MdC
Beaumont Olivieremail+33 (0)5 40 00 37 98 302 DR
Bensmail Julienemail+33 (0)5 40 00 35 17 357 Doct
Bianchi Giulianaemail+33 (0)5 40 00 60 87 315 MdC
Bonichon Nicolasemail+33 (0)5 40 00 69 31 304 MdC
Bonnin Davidemail+33 (0)5 40 00 35 31 328 Doct
Bousquet-Mélou Mireilleemail+33 (0)5 40 00 69 06 112 DR
Boussicault Adrienemail+33 (0)5 40 00 60 93 205 MdC Responsable Master 1 MIAGe
Bouvel Mathildeemail+33 (0)5 40 00 69 08 115 CR
Bouvier Tomemail+33 (0)5 40 00 37 96 257 Doct
Bultel Jean-Paulemail+33 (0)5 40 00 38 83 306ATER
Casse Jeromeemail+33 (0)5 40 00 84 19 123 Doct
Charpentier Clementemail+33 (0)5 40 00 84 15 274 Doct
Cori Robertemail+33 (0)5 40 00 60 85 326 Pr
Courtes Ludovicemail+33 (0)5 40 00 INRIA IR
Courtiel Julienemail+33 (0)5 40 00 35 13 119 Doct
Delmas Olivieremail+33 (0)5 40 00 69 35 358 MdC
Dorbec Paulemail+33 (0)5 40 00 69 86 215 MdC
Duchon Philippeemail+33 (0)5 40 00 35 19 214 Pr Responsable Master Informatique
Duvignau Romaricemail+33 (0)5 40 00 35 31 328 Doct
Eyraud-dubois Lionelemail+33 (0)5 40 00 60 88 305 CR Co-Editeur du LaBRI-Hebdo
Feray Valentinemail+33 (0)5 40 00 35 27 314 CR
Fontaine Allyxemail+33 (0)5 40 00 69 37 327 Doct
Gavoille Cyrilemail+33 (0)5 40 00 88 12 359 Pr Directeur adjoint UFR Maths Info
Glacet Christianemail+33 (0)5 40 00 35 14 105 Doct
Guibert Olivieremail+33 (0)5 40 00 35 02 371 MdC
Halftermeyer Pierreemail+33 (0)5 40 00 31 09 256 Doct
Hanusse Nicolasemail+33 (0)5 40 00 26 04 360 DR
Hocquard Hervéemail+33 (0)5 40 00 69 32 110PRCE
Ilcinkas Davidemail+33 (0)5 40 00 69 12 361 CR
Johnen Coletteemail+33 (0)5 40 00 60 47 319 Pr
Kardos Frantisekemail+33 (0)5 40 00 69 86 215 MdC
Klasing Ralfemail+33 (0)5 40 00 35 24 317 DR Responsable Equipe CombAlgo / Responsable des Relations Internationales
Kosowski Adrianemail+33 (0)5 40 00 60 88 305 CR
Le Borgne Yvanemail+33 (0)5 40 00 60 95 313 CR
Marckert Jean-Françoisemail+33 (0)5 40 00 35 34 108 CR
Mazoit Fredericemail+33 (0)5 40 00 69 12361 MdC
Metivier Yvesemail+33 (0)5 40 00 69 09 116 Pr
Milani Alessiaemail+33 (0)5 40 00 35 03 377 MdC
Mishna Marniemail+33 (0)5 40 00 69 34 261 Pr
Morsellino Thomasemail+33 (0)5 40 00 35 17 357ATER
Narbel Philippeemail+33 (0)5 40 00 38 73 311 MdC
Pajak Dominikemail+33 (0)5 40 00 35 53 367 Doct
Pecher Arnaudemail+33 (0)5 40 00 60 78 212 Pr
Penaud Jean-Guyemail+33 (0)5 40 00 353 Pr
Raspaud Andreemail+33 (0)5 40 00 69 29 207 Pr
Renaud-goud Paulemail+33 (0)5 40 00 36 10 301 PostDoc
Renault Gabrielemail+33 (0)5 40 00 84 19 123 Doct
Robson Mikeemail+33 (0)5 40 00 60 86 117 Pr
Selig Thomasemail+33 (0)5 40 00 35 47 68 Doct
Sen Sagnikemail+33 (0)5 40 00 35 37 69 Doct
Silimbani Matteoemail+33 (0)5 40 00 35 15 258 PostDoc
Sopena Ericemail+33 (0)5 40 00 38 71 370 Pr Directeur Adjoint
Tout Omaremail+33 (0)5 40 00 84 19 123 Doct
Travers Corentinemail+33 (0)5 40 00 35 29 316 MdC
Uznanski Przemyslawemail+33 (0)5 40 00 36 10 301 Doct
Verdonk Lucasemail+33 (0)5 40 00 35 14 105 IE
Viennot Xavieremail+33 (0)5 40 00 60 85326 DR
Ville Jean-Claudeemail+33 (0)5 40 00 60 87 315PRAG
Wade Ahmed-Mouhamadouemail+33 (0)5 40 00 35 37 69 Doct
Zemmari Akkaemail+33 (0)5 40 00 60 93 205 MdC Co-Responsable de la licence informatique, parcours "Informatique de gestion"
Zvonkine Alexandreemail+33 (0)5 40 00 69 13 203 Pr

Page mise à jour le 25/10/2012 à 14:38