Equipe de recherche ALGORITHMS

Algorithmes

Présentation de l'équipe

Algorithmes : analyse de systèmes complexes discrets présentant une composante aléatoire ; automatisation des méthodes d'analyses. Applications à l'étude quantitative d'algorithmes probabilistes.
Calcul formel : systèmes fonctionnels complexes, algorithmique rapide, systèmes différentiels, fonctions spéciales.

Axes de recherche

Problématique scientifique :
L'analyse et l'optimisation d'algorithmes requièrent une compréhension fine de structures aléatoires discrètes, comme les mots, les arbres, les graphes, les permutations, etc. En effet, l'efficacité de la plupart des algorithmes utilisés en pratique dépend de la forme attendue des données qu'ils traitent. ALGORITHMS quantifie précisément le comportement moyen des algorithmes, en visant des modèles réalistes des données. Les méthodes développées reposent sur l'établissement de liens entre des propriétés combinatoires et le comportement de fonctions analytiques. Étant donné le caractère très systématique de l'approche poursuivie, des méthodes de décision réalisables en calcul formel font aussi partie des objectifs d'ALGORITHMS. Cette approche est un moteur puissant de renouvellement qui conduit à la révision d'approches classiques en calcul formel dans ce domaine, la recherche est largement centrée sur l'étude des fonctions spéciales et des développements en séries. L'objectif est alors de disposer d'une algorithmique fiable et complète pour de grandes classes de problèmes issus de la combinatoire, des sciences physiques ou de l'analyse classique.

Fait marquant :
Hyperloglog, mis au point par ALGO, est le meilleur algorithme connu d'estimation de cardinalité de grands ensembles. Il évalue le nombre d'objets différents dans un ensemble pouvant en contenir des milliards, avec une consommation mémoire infime.

Logiciel développé :
Algolib : bibliothèque Maple pour l'analyse de structures combinatoires, de séries génératrices, d'équations différentielles ou de récurrences linéaires, de systèmes d'opérateurs linéaires.

Logiciels

Relations industrielles et internationales

Collaborations privilégiées :
  • Universités de Princeton, Linz, Pierre et Marie Curie, Caen et École Polytechnique.
  • GDR Informatique mathématique (groupes de travail Alea et Calcul formel).
  • Projets ANR Gecko (approche géométrique de la complexité) et Sada (structures aléatoires discrètes et algorithmes).
  • Master Parisien de Recherche en Informatique ; École Polytechnique.

Mots-clés : Analyse d’algorithmes Calcul formel

Equipes de recherche du même thème :

Siège et centres de recherche Inria

Accès direct

Social