"Th\u00E8ses et \u00E9crits acad\u00E9miques" . . . . "Analyse d'algorithmes et de structures de donn\u00E9es" . . "Algorithmes" . . "Bases de donn\u00E9es relationnelles" . "Bases de donn\u00E9es, allocations al\u00E9atoires, quelques analyses de performances" . "Bases de donn\u00E9es, allocations al\u00E9atoires, quelques analyses de performances" . "1989" . "Probabilit\u00E9s" . . . "Loi de probabilit\u00E9 limite" . "Text" . "Arbres de donn\u00E9es relationnelles" . "This thesis is devoted to the analysis of some parameters of interest for estimating the performance of computer systems, most notably database systems. The unifying features are the description of the phenomena to be studied in terms of random allocations and the systematic use of methods from the average-case analysis of algorithms. We associate a generating function with each parameter of interest, which we use to derive an asymptotic expression of this parameter.The main problem studied in this work is the estimation of the sizes of derived relations in a relational database framework. We show that this is closely related to the so-called \\\"occupancy problem\\\" in urn models, a classical tool of discrete probability theory. We characterize the conditional distribution of the size of a relation derived from relations whose sizes are known, and give conditions which ensure the a.symptotic normality of the limiting distribution. We next study the implementation of \\\"logical\\\" relations by multi-attribute or doubly chained trees, for which we give results on the complexity of a random orthogonal range query. Finally, we study some \\\"dynamic\\\" random allocation phenomena, such as the birthday problem, which models the occurrence of collisions in hashing, and a model of the Least Recently Used cache memory algorithm." . "Database systems, random allocations, some performance analysis studies" . "Tailles de relations d\u00E9riv\u00E9es" . . . . . . "Fonctions g\u00E9n\u00E9ratrices" . . "Cette th\u00E8se est consacr\u00E9e \u00E0 l'\u00E9tude de divers param\u00E8tres des tiques, entre autres des bases de donn\u00E9es, qui ont pour point commun de se pr\u00EAter naturellement \u00E0 une mod\u00E9lisation en termes de ph\u00E9nom\u00E8nes d'allocation al\u00E9atoire. Leur \u00E9tude utilise les techniques classiques de l'analyse en moyenne des algorithmes, \u00E0 savoir les s\u00E9ries g\u00E9n\u00E9ratrices et l'approximation asymptotique de leurs c\u0153fficients. Le probl\u00E8me initialement pos\u00E9 concerne l'\u00E9tude des tailles de relations d\u00E9riv\u00E9es dans l\u2019alg\u00E8bre relationnelle. Il admet une mod\u00E9lisation en termes de probl\u00E8mes probabilistes d\u2019allocation al\u00E9atoire, du type \\\"mod\u00E8les d'urnes\\\". Nous donnons des r\u00E9sultats sur les lois de probabilit\u00E9 conditionnelles des tailles de relations obtenues par application des op\u00E9rateurs de projection et jointure \u00E0 une ou plusieurs relations de taille connue. En particulier, nous obtenons divers th\u00E9or\u00E8mes sur les distributions limites de ces tailles, et montrons que, sous des hypoth\u00E8ses assez peu contraignantes, ces distributions limites sont fr\u00E9quemment normales. Une extension naturelle est ensuite de regarder comment impl\u00E9menter les relations \\\"logiques\\\", d\u00E9finies \u00E0 un niveau abstrait ; nous \u00E9tudions ici les arbres multi-attributs ou doublement cha\u00EEn\u00E9s.Les m\u00EAmes m\u00E9thodes permettent enfin de traiter certains ph\u00E9nom\u00E8nes d'allocation al\u00E9atoire de caract\u00E8re plus dynamique, par exemple le classique \\\"paradoxe des anniversaires\\\" (qui mod\u00E9lise la fr\u00E9quence d'apparition des collisions dans une table de hachage) ou l'algorithme de gestion m\u00E9moire \\\"Least Recently Used\\\"." . .