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
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