Ce mémoire de thèse est consacré à l'étude de quelques problèmes de probabilités provenant de l'informatique théorique. Dans une première partie, nous étudions un algorithme probabiliste qui compte le nombre de mots différents dans une liste. Nous montrons que l'étude peut se ramener à un problème d'estimation, et qu'en modifiant légèrement cet algorithme, il est d'une certaine manière optimal. La deuxième partie est consacrée à l'étude de plusieurs problèmes de convergences pour des systèmes finis de particules, nous envisageons différents types de passage à une limite infinie. La première famille de systèmes considérés est une classe particulière d'automates cellulaires. En dimension 1, il apparaît des marches aléatoires dont nous caractérisons de façon complète les comportements limites. En dimension 2, sur une grille carrée, nous étudions quelques-un des cas les plus représentatifs. Nous en déterminons le temps moyen de convergence vers une configuration fixe. Enfin, nous étudions un modèle d'urnes avec des boules à deux états. Dans la troisième partie, nous étudions deux problèmes particuliers de marches aléatoires. Ces deux questions sont initialement motivées par l'étude de certains automates cellulaires, mais nous les présentons de façon indépendante. Le premier de ces deux problèmes est l'étude de marches aléatoires sur un tore discret, réfléchies les unes sur les autres. On montre la convergence de ce processus vers une limite brownienne. Nous étudions enfin de façon entièrement combinatoire une famille de marches aléatoires sur un intervalle, biaisées vers le bas. Nous déterminons le temps moyen de sortie vers le haut de la marche. / This thesis deals with several problems in probability, mostly motivated by theoretical computer science. In the first part, we study of a probabilistic algorithm that counts the number of different words in a given sequence, by boiling it down to a statistical problem. We show that slightly improved, it achieves an optimal bound. The second and main part is devoted to different asymptotic problems concerning finite particle systems, for which we consider different kinds of infinite limits. We first deal with cellular automata. In dimension one, it appears random walks for which we entirely describe the asymptotic behaviors. In dimension two, on a square grid, we study some caracteristic rules for which we estimate the converge time. Lastly, we study a family of urn models. The third part focuses on two random walks problems. These questions where motivated by the study of cellular automata, but presented here in a self-contained way. The first problem is the study of a family of self-reflected random walks on a circle, for which we show a ``brownian limit''. The latter is a combinatorial description of a family of biased random walks on an interval.

Cette thèse traite d'algorithmique des ensembles de données en adoptant le point de vue de la combinatoire analytique. On traite ici de trois problèmes qui illustrent cette approche: les listes à sauts associées à de l'analyse asymptotique bivariée, le hachage à essai aléatoire avec pagination et le comptage probabiliste. Les listes à sauts sont une structure de données intermédiaire entre les skiplists et les arbres binaires de recherche. L'étude de cette structure a donné lieu à un problème d'asymptotique bivariée avec coalescence de singularités. Le hachage avec essai aléatoire est un algorithme qui gère les collisions d'une table de hachage. Dans le contexte étudié qui est celui de la pagination, on obtient la moyenne, ainsi que tous les moments successifs du coût de construction. Les algorithmes de comptage probabilistes originaux Loglog et Super Loglog permettent d'estimer le cardinal d'un ensemble en utilisant un kilooctet de mémoire avec une précision d'environ 3%.