Around a few statistics on binary search trees and on accessible deterministic automata - Université de Lorraine Access content directly
Theses Year : 2018

Around a few statistics on binary search trees and on accessible deterministic automata

Autour de quelques statistiques sur les arbres binaires de recherche et sur les automates déterministes

Abstract

This Phd thesis is divided into two independent parts. In the first part, we provide an asymptotic analysis of some statistics on the binary search tree. In the second part, we study the coupon collector problem with a constraint. In the first part, following the model introduced by Aguech, Lasmar and Mahmoud [Probab. Engrg. Inform. Sci. 21 (2007) 133—141], the weighted depth of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyze the following statistics : the weighted depths of nodes with given labels, the last inserted node, nodes ordered as visited by the depth first search procees, the weighted path length, the weighted Wiener index and the weighted depths of nodes with at most one child in a random binary search tree. In the second part, we study the asymptotic shape of the completion curve of the collection conditioned to T_n≤ (1+Λ), Λ>0, where T_n≃n ln⁡n is the time needed to complete accessible automata, we provide a new derivation of a formula due to Korsunov [Kor78, Kor86]
Cette thèse comporte deux parties indépendantes. Dans la première partie, nous nous intéressons à l’analyse asymptotique de quelques statistiques sur les arbres binaires de recherche (ABR). Dans la deuxième partie, nous nous intéressons à l’étude du problème du collectionneur de coupons impatient. Dans la première partie, en suivant le modèle introduit par Aguech, Lasmar et Mahmoud [Probab. Engrg. Inform. Sci. 21 (2007) 133—141], on définit la profondeur pondérée d’un nœud dans un arbre binaire enraciné étiqueté comme la somme de toutes les clés sur le chemin qui relie ce nœud à la racine. Nous analysons alors dans ABR, les profondeurs pondérées des nœuds avec des clés données, le dernier nœud inséré, les nœuds ordonnés selon le processus de recherche en profondeur, la profondeur pondérée des trajets, l’indice de Wiener pondéré et les profondeurs pondérées des nœuds avec au plus un enfant. Dans la deuxième partie, nous étudions la forme asymptotique de la courbe de la complétion de la collection conditionnée à T_n≤ (1+Λ), Λ>0, où T_n≃n ln⁡n désigne le temps nécessaire pour compléter la collection. Puis, en tant qu’application, nous étudions les automates déterministes et accessibles et nous fournissons une nouvelle dérivation d’une formule due à Korsunov [Kor78, Kor86]
No file

Dates and versions

tel-02096118 , version 1 (11-04-2019)

Identifiers

  • HAL Id : tel-02096118 , version 1

Intranet access

Cite

Anis Amri. Around a few statistics on binary search trees and on accessible deterministic automata. Mathematics [math]. Université de Lorraine, 2018. English. ⟨NNT : 2018LORR0301⟩. ⟨tel-02096118⟩
25 View
0 Download

Share

Gmail Facebook X LinkedIn More