Stochastic algorithms and trees

Cette thèse est consacrée à l'analyse de plusieurs problèmes issus de l'informatique et de la combinatoire. Dans une première partie, nous étudions les effets que produisent des erreurs de comparaison lorsque l'on traite une liste avec l'algorithme de tri Quicksort. Lorsque une comparaison est erronée avec une probabilité p, on montre que le nombre d'inversions de la liste restituée par Quicksort est de l'ordre de grandeur de n2p. Dans la deuxième partie, nous démontrons la convergence d'un processus appelé watermelon vers un processus défini par des équations différentielles stochastiques. Nous donnons également quelques propriétés de ce processus limite : la loi de sa norme, quelques moments, un lien avec les valeurs propres de matrices aléatoires, ... La dernière partie est consacrée à l'étude du comportement asymptotique des lois locales des arbres simples. Nous montrons que la loi des arbres simples de taille n converge vers une mesure de probabilité que nous décrivons.This thesis deals with the probabilistic analysis of some problems comming from computer science and combinatoric. In a first part, we study the effects of errors of comparison when we sort an input list with the sorting algorithm Quicksort. When a comparison can err with probability p, we show that the number of inversions in the output list of Quicksort has the order of magnitude n2p. In the second part, we prove the convergence of a process known as watermelon to a process defined by stochastic differential equations. We also give some properties of this limit process: the law of his norm, some moments, a link with the eigen values of random matrices, ... The last part deals with the study of the asymptotic behaviour of the local laws of simple trees. We show that the law of simple trees with n vertices converges to a probablity measure we describe