ACI NIM Arbres, chemins: probabilités et algorithmes

Le Projet Arbres et Chemins: Probabilités et Algorithmes s'inscrit à la rencontre de deux courants: d'une part l'application de la combinatoire analytique (méthodes bijectives et asymptotique complexe) et de la théorie des processus (mouvement Brownien, processus de branchement, martingales) aux objets fondamentaux de la combinatoire et des mathématiques discrètes; d'autre part les besoins, nombreux en informatique (particulièrement en structures de données et algorithmique), d'une quantification des propriétés de l'aléa visant à prédire précisément les performances, ainsi qu'à dimensionner et optimiser les algorithmes d'accès à l'information. Le Projet se concentrera sur les chemins et les arbres, envisagés sous les angles combinatoires, probabilistes (processus stochastiques associés), et algorithmiques. Les applications visées se situent dans le domaine de la gestion de données sur support externe (hachage), des arbres de recherche (notamment multidimensionnels ou digitaux), des phénomènes de coalescence (graphes aléatoires et algorithmes de gestion d'équivalences), de la complexité des expressions booléennes, et de la génération aléatoire d'objets structurés (jeux de tests). Ces questions nécessitent le développement de modèles non classiques s'appuyant sur des méthodes combinatoires, analytiques et stochastiques variées, lesquelles ont alors besoin d'être revues sous un éclairage nouveau et unifiées: notre objectif est en quelque sorte de construire, sur nos objets d'étude favoris, les bases d'une théorie des ``processus combinatoires'' adaptée à l'algorithmique.