Skip to Main content Skip to Navigation

Etude d'algorithmes stochastiques et arbres

Abstract : 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.
Document type :
File URL :
Complete list of metadata
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 10:45:21 AM
Last modification on : Tuesday, March 2, 2021 - 5:12:06 PM


  • HAL Id : tel-01746814, version 1



Florent Gillet. Etude d'algorithmes stochastiques et arbres. Mathématiques générales [math.GM]. Université Henri Poincaré - Nancy 1, 2003. Français. ⟨NNT : 2003NAN10191⟩. ⟨tel-01746814⟩



Record views