Appendice D
Un peu d’histoire. . .
Nous donnons ici quelques indications sur l’historique des travaux sur les arbres
aléatoires, sous l’angle des motivations informatiques et plus particulièrement algorithmiques. Nous ne prétendons pas être exhaustifs, mais plutôt rendre hommage
aux chercheurs qui nous ont conduits au positionnement de cet ouvrage. Nous
mentionnons ici surtout des livres ou des cours ; la littérature publiée sous forme
d’articles, très abondante, est indiquée dans le cours du livre.
Notre ouvrage peut être considéré comme un descendant d’une part de la littérature sur les arbres, aléatoires ou non, qui sont apparus dans l’analyse d’algorithmes
et d’autre part de la littérature sur les arbres aléatoires étudiés par les probabilistes
avec ou sans motivation algorithmique.
Les fondations de l’analyse d’algorithmes remontent à Knuth, dont la série
The Art of Computer Programming a joué un rôle essentiel pour définir mathématiquement et poser le domaine. Dans le volume 1 Fundamental Algorithms, dont
la première édition date de 1968, Knuth présente les structures de données les
plus courantes, notamment les arbres présentés dans cet ouvrage [157, pages 305–
406]. Après avoir introduit les définitions de base, étudié diverses implémentations,
et considéré les arbres comme un type particulier de graphe, il s’intéresse à
l’énumération de diverses classes d’arbres, puis à la longueur de cheminement
d’un arbre binaire. Il termine en présentant l’historique de la notion mathématique
d’arbre, dont le premier usage systématique semble remonter à Kirchhoff au milieu
du 19-ième siècle. Il s’agit sans doute d’un des premiers livres présentant de façon
unifiée les arbres pour l’algorithmique et les résultats alors disponibles.
Le volume 3, Sorting and Searching [156], étudie de façon encyclopédique
les deux grandes classes de problèmes que sont le tri et la recherche ; il s’y
trouve d’abord une première partie consacrée aux tris, avec l’analyse du tri rapide
(pages 114–123) et celle du tri radix (pages 124–134). La seconde partie traite
de la recherche, et donc (entre autres) des arbres de recherche : arbres binaires
de recherche (pages 406–451), avec des points assez peu traités par ailleurs, telle
la construction et l’analyse des performances d’un arbre binaire de recherche
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0
485
Un peu d’histoire. . .
Nous donnons ici quelques indications sur l’historique des travaux sur les arbres
aléatoires, sous l’angle des motivations informatiques et plus particulièrement algorithmiques. Nous ne prétendons pas être exhaustifs, mais plutôt rendre hommage
aux chercheurs qui nous ont conduits au positionnement de cet ouvrage. Nous
mentionnons ici surtout des livres ou des cours ; la littérature publiée sous forme
d’articles, très abondante, est indiquée dans le cours du livre.
Notre ouvrage peut être considéré comme un descendant d’une part de la littérature sur les arbres, aléatoires ou non, qui sont apparus dans l’analyse d’algorithmes
et d’autre part de la littérature sur les arbres aléatoires étudiés par les probabilistes
avec ou sans motivation algorithmique.
Les fondations de l’analyse d’algorithmes remontent à Knuth, dont la série
The Art of Computer Programming a joué un rôle essentiel pour définir mathématiquement et poser le domaine. Dans le volume 1 Fundamental Algorithms, dont
la première édition date de 1968, Knuth présente les structures de données les
plus courantes, notamment les arbres présentés dans cet ouvrage [157, pages 305–
406]. Après avoir introduit les définitions de base, étudié diverses implémentations,
et considéré les arbres comme un type particulier de graphe, il s’intéresse à
l’énumération de diverses classes d’arbres, puis à la longueur de cheminement
d’un arbre binaire. Il termine en présentant l’historique de la notion mathématique
d’arbre, dont le premier usage systématique semble remonter à Kirchhoff au milieu
du 19-ième siècle. Il s’agit sans doute d’un des premiers livres présentant de façon
unifiée les arbres pour l’algorithmique et les résultats alors disponibles.
Le volume 3, Sorting and Searching [156], étudie de façon encyclopédique
les deux grandes classes de problèmes que sont le tri et la recherche ; il s’y
trouve d’abord une première partie consacrée aux tris, avec l’analyse du tri rapide
(pages 114–123) et celle du tri radix (pages 124–134). La seconde partie traite
de la recherche, et donc (entre autres) des arbres de recherche : arbres binaires
de recherche (pages 406–451), avec des points assez peu traités par ailleurs, telle
la construction et l’analyse des performances d’un arbre binaire de recherche
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0
485