xxii
Introduction
est effectuée dans les chapitres 4 à 9, le plus souvent possible sous les deux angles
de la combinatoire analytique et des probabilités.
Plusieurs annexes rappellent, d’une part les structures de données informatiques
et les algorithmes permettant de manipuler ces structures arborescentes (c’est
l’annexe A), d’autre part les outils mathématiques nécessaires pour suivre les
analyses (ce sont l’annexe B pour la combinatoire et l’analyse, et l’annexe C pour les
probabilités). Enfin l’annexe D présente un historique et une bibliographie subjectifs
et non exhaustifs. Donnons maintenant un bref aperçu des méthodes utilisées.
Méthodes
L’exemple des arbres binaires de recherche montre qu’il y a en gros deux classes de
méthodes possibles : analytiques et combinatoires d’une part, probabilistes d’autre
part. Tout au long de ce livre, nous nous efforçons de présenter ces méthodes
simultanément et concurremment.
Combinatoire analytique
Supposons avoir dégagé d’une part une notion de taille des données en entrée d’un
algorithme et d’autre part une notion de coût d’un algorithme, exprimé en fonction
d’un paramètre de l’arbre τ associé aux données. Appelons ce coût c(τ ). Lorsque les
données sont supposées aléatoires, alors c(τ ) devient une variable aléatoire. Il est
alors loisible de définir le coût moyen, appelons-le c n , pour une donnée aléatoire
de taille n. Une technique puissante de résolution, lorsqu’il existe une relation
de récurrence sur c n , ou directement sur c(τ ), consiste à introduire la fonction
génératrice de la suite (c n ), disons C(z) =
n c n z n . L’obtention de C(z), ou
plus fréquemment d’une équation dont elle est solution, est possible grâce à des
techniques de combinatoire, en particulier la méthode symbolique. Il arrive parfois
d’obtenir une expression explicite pour C(z) et pour ses coefficients. Lorsque ce
n’est pas le cas, il est néanmoins fructueux de considérer C(z) comme une fonction
analytique dans le plan complexe, et d’obtenir sinon la valeur exacte du n-ième
coefficient de la fonction, i.e., de c n , du moins son comportement asymptotique –
c’est souvent le plus intéressant, la question du coût d’un algorithme n’ayant un
intérêt pratique que pour des données de « grande » taille. L’outil de base pour
cette étude asymptotique est la formule de Cauchy ou les adaptations qui en ont
été faites, la plus notable pour notre sujet étant le lemme de transfert de Flajolet et
Odlyzko [90].
Cette approche, qui fait appel à la combinatoire et à l’analyse, a été développée
et systématisée par Flajolet, qui lui a donné le nom de Combinatoire analytique.
Elle permet, à partir d’une spécification formelle des objets combinatoires étudiés
(ici, des arbres), d’étudier leurs paramètres, non seulement en moyenne, mais en
Introduction
est effectuée dans les chapitres 4 à 9, le plus souvent possible sous les deux angles
de la combinatoire analytique et des probabilités.
Plusieurs annexes rappellent, d’une part les structures de données informatiques
et les algorithmes permettant de manipuler ces structures arborescentes (c’est
l’annexe A), d’autre part les outils mathématiques nécessaires pour suivre les
analyses (ce sont l’annexe B pour la combinatoire et l’analyse, et l’annexe C pour les
probabilités). Enfin l’annexe D présente un historique et une bibliographie subjectifs
et non exhaustifs. Donnons maintenant un bref aperçu des méthodes utilisées.
Méthodes
L’exemple des arbres binaires de recherche montre qu’il y a en gros deux classes de
méthodes possibles : analytiques et combinatoires d’une part, probabilistes d’autre
part. Tout au long de ce livre, nous nous efforçons de présenter ces méthodes
simultanément et concurremment.
Combinatoire analytique
Supposons avoir dégagé d’une part une notion de taille des données en entrée d’un
algorithme et d’autre part une notion de coût d’un algorithme, exprimé en fonction
d’un paramètre de l’arbre τ associé aux données. Appelons ce coût c(τ ). Lorsque les
données sont supposées aléatoires, alors c(τ ) devient une variable aléatoire. Il est
alors loisible de définir le coût moyen, appelons-le c n , pour une donnée aléatoire
de taille n. Une technique puissante de résolution, lorsqu’il existe une relation
de récurrence sur c n , ou directement sur c(τ ), consiste à introduire la fonction
génératrice de la suite (c n ), disons C(z) =
n c n z n . L’obtention de C(z), ou
plus fréquemment d’une équation dont elle est solution, est possible grâce à des
techniques de combinatoire, en particulier la méthode symbolique. Il arrive parfois
d’obtenir une expression explicite pour C(z) et pour ses coefficients. Lorsque ce
n’est pas le cas, il est néanmoins fructueux de considérer C(z) comme une fonction
analytique dans le plan complexe, et d’obtenir sinon la valeur exacte du n-ième
coefficient de la fonction, i.e., de c n , du moins son comportement asymptotique –
c’est souvent le plus intéressant, la question du coût d’un algorithme n’ayant un
intérêt pratique que pour des données de « grande » taille. L’outil de base pour
cette étude asymptotique est la formule de Cauchy ou les adaptations qui en ont
été faites, la plus notable pour notre sujet étant le lemme de transfert de Flajolet et
Odlyzko [90].
Cette approche, qui fait appel à la combinatoire et à l’analyse, a été développée
et systématisée par Flajolet, qui lui a donné le nom de Combinatoire analytique.
Elle permet, à partir d’une spécification formelle des objets combinatoires étudiés
(ici, des arbres), d’étudier leurs paramètres, non seulement en moyenne, mais en