Distribution of Valuations on Trees.
Distribution de valuations sur les arbres.
Résumé
This thesis studies the limit distribution of parameters recursively defined on trees (rooted graphs). A first parameter which is studied is the result of arithmetical expressions drawn at random. An application is the heuristic improvement of an algorithm of research of RNA secondary structures. Another parameter I study is the size of logical or arithmetical expressions reduced according to idempotent, nilpotent or absorption laws. I study polynomial functionals of standard Brownian motion, of Brownian bridge, meander and excursion with the use of the method of moments which relies on generating functions and singularity analysis. I obtain the Gaussian limit of the joint law of the size and the internal path length of tries with Bernoulli source by using fixed point methods.
Cette thèse étudie la distribution limite de paramètres définis récursivement sur des arbres (graphes enracinés). Un premier paramètre étudié est le résultat d'expressions arithmétiques tirées aléatoirement. Une application est l'amélioration heuristique d'un algorithme de recherche de structures secondaires d'ARN. Un autre paramètre étudié est la taille d'expressions logiques ou arithmétiques réduites selon des lois idempotentes, nilpotentes ou d'absorption. J'étudie des fonctionnelles polynomiales du mouvement brownien standard, du pont, du méandre, et de l'excursion browniens en utilisant la méthode des moments à base de séries génératrices et d'analyse de singularité. J'obtiens la limite gaussienne de la loi jointe de la taille et de la longueur de cheminement interne des tries avec source de Bernoulli en utilisant des méthodes de point fixe.