Probabilité et combinatoire en informatique algorithmique

 

Luc Devroye

Université McGill

 

Domaine : structures abstraites

Programme projet de recherche en équipe

Concours 2010-2011

Comment les outils probabilistes et combinatoires peuvent-ils être utilisés pour attaquer des problèmes en informatique algorithmique? Réciproquement, comment peut-on utiliser les outils venant de l'analyse d'algorithmes dans des preuves probabilistes et combinatoires? En général, ce sont des questions que nous étudions dans notre projet. Nous étudions des problèmes dans le domaine de la probabilité discrète qui sont à saveur algorithmique, et nous prouvons des résultats probabilistes tout en découvrant leur structure combinatoire. De même, nous visons à créer et développer des outils probabilistes pour l'analyse des algorithmes et du comportement des grandes structures de données.

Certains des problèmes spécifiques que nous considérons incluent la percolation "premier-passage" sur les arbres et les graphes, la hauteur des arbres aléatoires, les distances dans les graphes aléatoires, la largeur de prélèvement des chaînes de Markov, et l'utilisation des inégalités de concentration dans l'analyse d'algorithmes et des données aléatoires.