A Probabilistic Analysis of Tree Algorithms.

Étude Probabiliste d'Algorithmes en Arbre

Hanene Mohamed (1, 2)

1 LPMA - Laboratoire de Probabilités et Modèles Aléatoires
2 RAP - Networks, Algorithms and Probabilities

In this thesis a general class of tree algorithms is analyzed. It is shown that, by using an appropriate probabilistic representation of the quantities of interest, the asymptotic behavior of these algorithms can be obtained quite easily. This approach gives a unified probabilistic treatment of these questions. It simplifies and extends some of the results known in this domain.

Cette thèse est dédiée à l'étude d'une large classe d'algorithmes, appelés algorithmes en arbre. En utilisant une représentation probabiliste appropriée, le comportement asymptotique de tels algorithmes est analysé. L'approche unifie les études faites sur ces algorithmes ainsi que simplifie et généralise certains résultats établis dans le domaine.

Mots clés: Splitting Algorithms. Divide and Conquer Algorithms. Unusual Laws of Large Numbers. Asymptotic Oscillating Behavior. Data Structures. Tries. Renewal Theorem.

Mots clés: Algorithmes en Arbre. Diviser pour Régner. Étrange Loi des Grands Nombres. Phénomène d'Oscillations Asymptotiques. Structures de Données. Tries. Théorème de Renouvellement.; Algorithmes en Arbre. Diviser pour Régner. Étrange Loi des Grands Nombres. Phénomène d'Oscillations Asymptotiques. Structures de Données. Tries. Théorème de Renouvellement

Domaines: Mathématiques [math]

Hanene Mohamed. Étude Probabiliste d'Algorithmes en Arbre. Mathématiques [math]. Université Pierre et Marie Curie - Paris VI, 2007. Français. ⟨NNT : ⟩. ⟨tel-00270742⟩