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 :
Complete list of metadata
Contributor : Thèses UL Connect in order to contact the contributor
Submitted on : Thursday, March 29, 2018 - 10:45:21 AM
Last modification on : Saturday, October 16, 2021 - 11:18:03 AM

Links full text


  • 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