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