Arbres pour l’Algorithmique
 |
| Arbres pour l’Algorithmique |
Avant-propos
Les recherches sur les structures arborescentes relèvent historiquement de deux
domaines initialement disjoints : les mathématiques, notamment les mathématiques discrètes et les probabilités, et l’informatique fondamentale, avec l’analyse
d’algorithmes. Nous avons cherché à présenter simultanément ces deux approches,
que nous estimons être complémentaires plutôt que concurrentes ; ce livre en est le
résultat. Il est en partie issu d’un cours de troisième cycle, enseigné il y a plusieurs
années par deux des auteurs pour un diplôme de Mathématiques-Informatique, et
qui visait déjà à présenter conjointement les méthodes issues de la combinatoire
analytique et des probabilités.
À qui s’adresse cet ouvrage ? Notre livre s’adresse typiquement aux étudiants de
niveau master scientifique ou en dernière année d’école d’ingénieurs, qui auraient
auparavant suivi un cursus en informatique ou en mathématiques et qui aspirent
à explorer davantage les contrées intermédiaires entre ces deux disciplines ; les
étudiants visant une double compétence en mathématiques et informatique pourront
ainsi y trouver un intérêt. Il s’adresse en outre à toute personne dotée d’un bagage
scientifique « minimal », qui serait amenée à utiliser des structures arborescentes
liées à des algorithmes, et qui souhaiterait avoir une meilleure connaissance de ces
structures et une idée des performances des algorithmes associés, sans se plonger
dans les travaux originaux. Il peut ainsi constituer une introduction à la recherche
sur ces sujets, sans prétendre davantage et notamment sans prétendre se situer à
l’état de l’art. En effet, il ne s’agit pas d’un livre sur les arbres en général, mais
d’un livre sur les arbres pour l’algorithmique. Nous espérons que les spécialistes y
trouveront eux aussi un intérêt. Les probabilistes pourront y trouver des indications
sur l’utilisation des arbres aléatoires en informatique, notamment dans le champ de
l’analyse d’algorithmes ; de leur côté, les informaticiens pourront bénéficier d’un
éclairage probabiliste sur certains de leurs objets de base.
Nous ne prétendons en aucun cas à l’exhaustivité, mais plus raisonnablement
à rendre compte, selon des critères éminemment subjectifs (il a fallu faire des
choix !), des résultats qui nous paraissent à la fois importants et suffisamment
simples à exposer. Nous avons aussi souhaité mettre en avant des méthodes
ix
x Avant-propos
devenues classiques pour établir ces résultats. Certaines parties, qualifiées parfois de
« folklore », et certains théorèmes sont connus depuis des décennies et se trouvent
éparpillés dans divers ouvrages ; quelques-uns de ces ouvrages sont indiqués
dans le chapitre d’introduction et un plus grand nombre sont présentés dans une
perspective historique dans l’annexe D. D’autres parties de ce livre ont trait à des
développements plus récents qui sont encore peu (ou pas) diffusés sous forme
de livre. Enfin quelques résultats importants sont seulement mentionnés car leur
exposition détaillée avec preuve « sortirait du cadre de ce livre ». Pour signaler au
lecteur ces parties, nous les avons écrites sur fond grisé et nous avons distingué
plusieurs cas :
indique qu’il faut prendre un papier et un crayon mais cette partie est
élémentaire, il n’y a pas de difficulté, ni technique ni autre ;
indique que cette partie est plus technique ;
indique que pour cette partie il est nécessaire d’avoir recours à des notions
qui ne sont pas dans ce livre.
En outre, nous avons souvent proposé en exercices des parties de preuves.
Dans notre souci de présenter simultanément des approches a priori distinctes
(probabiliste, combinatoire et algorithmique), nous avons tenté d’unifier les notations et définitions employées par les deux communautés différentes que sont
les mathématiciens et les informaticiens. Il a fallu faire des compromis ; parfois
l’unification était hors d’atteinte. Ainsi des notations pourront sembler lourdes, des
définitions paraîtront inutilement formelles ; inversement, des passages seront plus
intuitifs et moins formels, reposant sur l’exemple. Dans l’ensemble, nous avons
été guidés par un souci de cohérence et de (relative) simplicité. Nous avons ainsi
simplifié certains passages mathématiquement touffus, au nom de l’accessibilité et
de la pédagogie, en espérant ne pas avoir sacrifié la rigueur.
Plan du livre Dans les chapitres 1 à 3 sont posées les bases, sont définis les
modèles : ce qu’est un arbre, ce qu’il modélise et quels sont ses emplois les plus
courants en informatique, ce que signifie la notion d’« arbre aléatoire ». Nous avons
fait le choix de séparer drastiquement l’aléa dans cette présentation, afin de mieux
distinguer ensuite dans les analyses ce qui ressort plutôt de méthodes combinatoires
ou plutôt de méthodes probabilistes.
– Au chapitre 1 sont définies de multiples variétés d’arbres, planaires ou non,
marqués ou non, ainsi que les paramètres les plus classiques sur ces arbres. Il
est tout à fait possible de ne pas lire ce chapitre d’une traite, mais de s’y référer
seulement en cas de besoin.
– Le chapitre 2 enrichit les définitions, en introduisant les types d’aléa, différents
suivant les variétés d’arbres. De même que le chapitre 1, c’est essentiellement un
chapitre de référence, à lire selon le besoin.
– Le chapitre 3 contient plusieurs exemples de modélisations par des structures
arborescentes, soit pour les problèmes classiques que sont le traitement de
Avant-propos xi
chaînes de caractères, la recherche d’un élément dans un ensemble, et le tri d’un
ensemble, soit pour des situations plus élaborées ; c’est ce chapitre qui justifie un
éventuel intérêt pratique du livre.
Dans les chapitres 4 à 9 sont analysées de nombreuses familles d’arbres, qui
diffèrent notamment par le type d’aléa.
– Au chapitre 4 sont étudiés d’abord les arbres binaires planaires, puis différentes
familles d’arbres planaires (familles simples d’arbres, tas, arbres équilibrés), et
ensuite les arbres non planaires, le tout sous un modèle probabiliste où les arbres
de même taille (parfois de même hauteur) sont équiprobables. Nous sommes
ainsi dans le domaine de la combinatoire.
– Au chapitre 5 sont présentés les processus de branchement, notamment les arbres
de Galton-Watson et les marches aléatoires branchantes. Un lien est également
établi entre les arbres de Galton-Watson et les arbres « combinatoires » étudiés
au chapitre précédent. Le point de vue est largement probabiliste, même si la
récursivité partout présente n’est pas sans rappeler les raisonnements du type
« diviser pour régner » utilisés aux chapitres 2 et 4.
– Le chapitre 6 concerne les arbres binaires de recherche et plusieurs de leurs
extensions, venues soit des probabilités (arbres biaisés), soit de l’informatique
(arbres récursifs, arbres binaires de recherche randomisés, lien avec le tri rapide).
Nous utilisons les deux points de vue probabiliste ou combinatoire de façon
complémentaire.
– Les tries, qui sont la structure digitale de base, sont analysés dans le chapitre 7,
essentiellement avec des outils de combinatoire analytique.
– Deux types d’arbres de recherche, étendant les classiques arbres binaires de
recherche, sont analysés en détail dans le chapitre 8 : les arbres m-aires, dans
lesquels il est possible d’avoir plusieurs clés dans un même nœud, puis les arbres
quadrants, qui permettent de prendre en compte des clés multi-dimensionnelles.
– Enfin, au chapitre 9 sont approfondis les résultats sur les arbres de recherche, en
voyant certains de leurs paramètres comme une urne de Pólya ; les analyses font
intervenir successivement combinatoire analytique et probabilités.
Les annexes qui terminent ce livre devraient permettre à nos lecteurs de trouver les
bases nécessaires pour suivre nos modélisations et analyses.
– À l’annexe A sont présentés les algorithmes les plus classiques sur la plupart des
structures arborescentes que nous rencontrons dans les chapitres précédents.
– Les annexes B et C, quant à elles, sont des compendiums des notions mathé-
matiques, respectivement combinatoires et probabilistes, nécessaires à la compréhension des modèles et des analyses présentés dans les chapitres 1 à 9.
– Enfin, l’annexe D présente une histoire, partielle et partiale, de l’utilisation des
arbres en analyse d’algorithmes.
Prérequis Une familiarité avec les outils mathématiques de base (niveau L2)
est souhaitable. Une connaissance de tout ou partie des outils que nous utilisons
(combinatoire analytique, probabilités), ou des implémentations informatiques des
xii Avant-propos
structures arborescentes, est utile mais pas indispensable ; en outre, il y a plusieurs
niveaux de lecture de ce livre, selon que la lectrice/le lecteur souhaite plutôt
utiliser algorithmiquement un résultat donné, ou maîtriser quelques méthodes de
démonstration.
Possibilités de lecture (voir l’illustration ci-dessous) Les chapitres 1 et 2 pourront
servir de chapitres de référence plutôt qu’être lus en tant que tels. Parmi les
chapitres 3 à 9, plusieurs choix pourront être retenus selon les intérêts de la
lectrice/du lecteur ou l’orientation que cette personne souhaiterait donner à un cours
qui serait basé sur ce livre.
Si l’intérêt porte essentiellement sur les algorithmes, le chapitre 3 (arbres comme
modèles d’analyse d’algorithmes) est fondamental ; il sera ensuite loisible de
choisir, dans chaque chapitre, les sections qui mettent en perspective les résultats
mathématiques sur les paramètres des structures arborescentes et les relient aux
performances des algorithmes les utilisant. Si l’accent est mis sur la combinatoire
analytique, le choix portera sur les chapitres 4 (modèle combinatoire pour plusieurs
familles d’arbres), 7 (structures digitales), la seconde partie du chapitre 8 (arbres
quadrants) et la première partie du chapitre 9 (urnes de Pólya). Si l’accent est
mis sur l’analyse probabiliste, le choix portera prioritairement sur les chapitres 5
(processus de branchement) et 6 (arbres binaires de recherche), puis sur la première
partie du chapitre 8 et le chapitre 9 pour aborder des extensions des arbres binaires
de recherche.
Télécharger le livre
