Résumé :
Malgré une très grande utilisation des arbres en analyse d'algorithmes et en informatique en général, les arbres dits de "Galton-Watson" ont été largement ignorés. Néanmoins, ces arbres ont été largement étudiés en probabilités et des résultats élégants et généraux ont été obtenus les concernant.
Durant cet exposé, je décrirai brièvement la construction de ces arbres et je présenterai des résultats fondamentaux concernant leur croissance. Ensuite, je montrerai comment utiliser ces résultats dans le cadre d'une analyse d'un algorithme de parcours en largeur. Puis on en déduira un résultat concernant la borne supérieure du seuil de satisfaisabilité de Random 2-SAT.
Abstract:
In spite of a wide use of trees in analysis of algorithms and in computer science in general, the particular class of Galton-Watson trees is mostly ignored. Nevertheless those trees have been widely studied from a probabilistic point of view and very elegant and general results have been obtained.
In this talk, we will shortly describe
the construction of these trees, and present some fundamental results concerning
their growth. Then we will show how one can use these results for the analysis
of a width searching algorithm and then deduce an approximation of the
upper bound of the satisfiability threshold of Random 2-SAT.
Related papers: