Introduction
xxiii
distribution, i.e., d’obtenir moments ou convergence vers une loi limite. Nous
renvoyons aux livres de Flajolet et Sedgewick [93, 94] pour une présentation de
ce domaine de recherche et pour les applications en analyse d’algorithmes.
Probabilités
Les structures arborescentes qui apparaissent aussi bien dans la représentation
des données que dans la représentation des choix d’exécution d’un algorithme
conduisent naturellement à une modélisation par des arbres aléatoires, en d’autres
termes par un ensemble d’arbres sur lequel une loi de probabilité a été définie. De
plus, les arbres aléatoires peuvent aussi être vus comme un cas particulier de graphes
aléatoires, qui sont eux-mêmes des modèles intervenant par exemple pour décrire
des réseaux de télécommunication. Rappelons cependant que dans ce livre un arbre
sera toujours enraciné, i.e. un sommet est désigné comme racine (à la différence de
la plupart des arbres rencontrés en théorie des graphes, où aucun sommet ne joue a
priori de rôle particulier).
Une bonne manipulation des arbres aléatoires nécessite de travailler sur des
espaces probabilisés. Les processus aléatoires (on dit aussi stochastiques) qui
appartiennent à la famille des processus de branchement seront naturellement
présents. Ils peuvent décrire simplement l’évolution d’une population en comptant
le nombre d’individus à la n-ième génération (ce sont les processus de GaltonWatson), ou bien décrire des évolutions plus riches, en marquant les nœuds ou les
branches d’un arbre par toutes sortes de variables qui présentent un intérêt pour
l’étude. Les marches aléatoires branchantes en sont un exemple.
D’autres processus stochastiques peuvent aussi intervenir, par exemple pour
l’étude des arbres binaires de recherche. Dans les cas détaillés dans cet ouvrage,
des méthodes probabilistes classiques, couplées parfois à des méthodes analytiques,
permettent de déterminer le comportement asymptotique d’une variable aléatoire
correspondant au coût d’un algorithme. Des martingales apparaissent, des marches
aléatoires sont associées aux arbres, et les différentes notions de convergence
fournissent autant de notions de limite.
Un exemple d’utilisation conjointe : les urnes de Pólya
Les urnes de Pólya sont un modèle polyvalent qui apparaît dès qu’il y a un choix
uniforme à faire entre des objets (boules) de différentes espèces (couleurs). Ce sera
typiquement le cas lors de l’insertion d’une nouvelle clé dans un arbre de recherche,
par exemple dans un arbre 2–3 suivant que la feuille où prend place cette clé contient
déjà une ou deux clés. Dans une modélisation d’arbre par une urne de Pólya, les
xxiii
distribution, i.e., d’obtenir moments ou convergence vers une loi limite. Nous
renvoyons aux livres de Flajolet et Sedgewick [93, 94] pour une présentation de
ce domaine de recherche et pour les applications en analyse d’algorithmes.
Probabilités
Les structures arborescentes qui apparaissent aussi bien dans la représentation
des données que dans la représentation des choix d’exécution d’un algorithme
conduisent naturellement à une modélisation par des arbres aléatoires, en d’autres
termes par un ensemble d’arbres sur lequel une loi de probabilité a été définie. De
plus, les arbres aléatoires peuvent aussi être vus comme un cas particulier de graphes
aléatoires, qui sont eux-mêmes des modèles intervenant par exemple pour décrire
des réseaux de télécommunication. Rappelons cependant que dans ce livre un arbre
sera toujours enraciné, i.e. un sommet est désigné comme racine (à la différence de
la plupart des arbres rencontrés en théorie des graphes, où aucun sommet ne joue a
priori de rôle particulier).
Une bonne manipulation des arbres aléatoires nécessite de travailler sur des
espaces probabilisés. Les processus aléatoires (on dit aussi stochastiques) qui
appartiennent à la famille des processus de branchement seront naturellement
présents. Ils peuvent décrire simplement l’évolution d’une population en comptant
le nombre d’individus à la n-ième génération (ce sont les processus de GaltonWatson), ou bien décrire des évolutions plus riches, en marquant les nœuds ou les
branches d’un arbre par toutes sortes de variables qui présentent un intérêt pour
l’étude. Les marches aléatoires branchantes en sont un exemple.
D’autres processus stochastiques peuvent aussi intervenir, par exemple pour
l’étude des arbres binaires de recherche. Dans les cas détaillés dans cet ouvrage,
des méthodes probabilistes classiques, couplées parfois à des méthodes analytiques,
permettent de déterminer le comportement asymptotique d’une variable aléatoire
correspondant au coût d’un algorithme. Des martingales apparaissent, des marches
aléatoires sont associées aux arbres, et les différentes notions de convergence
fournissent autant de notions de limite.
Un exemple d’utilisation conjointe : les urnes de Pólya
Les urnes de Pólya sont un modèle polyvalent qui apparaît dès qu’il y a un choix
uniforme à faire entre des objets (boules) de différentes espèces (couleurs). Ce sera
typiquement le cas lors de l’insertion d’une nouvelle clé dans un arbre de recherche,
par exemple dans un arbre 2–3 suivant que la feuille où prend place cette clé contient
déjà une ou deux clés. Dans une modélisation d’arbre par une urne de Pólya, les