Brigitte Chauvin (Université de Versailles et INRIA Rocquencourt)

Quelques arbres et martingales pour l'analyse d'algorithmes

Cet exposé est l'occasion de présenter différentes familles d'arbres aléatoires liées à l'analyse d'algorithmes très utilisés en informatique. Ainsi en va-t-il des arbres binaires de recherche pour l'algorithme de tri Quicksort. Des martingales naturelles jouent un rôle clé dans l'analyse asymptotique de ces arbres, comme c'était déjà le cas pour les processus de branchement.
Le passage de modèles discrets (arbres binaires ou m-aires de recherche, urnes de Pólya) vers des modèles continus permet de jouer avec des martingales, des lois limites non usuelles et des équations de point fixe.