486
D Un peu d’histoire. . .
« optimal » pour un ensemble de clés données ; puis arbres binaires de recherche
« équilibrés », soit par hauteur (ce sont les arbres AVL dus à Adel’son-Vel’skii et
Landis [1]), soit par poids ; enfin les arbres-B (pages 451–480) et les arbres digitaux
(pages 481–505). Dans le même esprit que le volume 1, ce volume 3, datant de
1973 pour la première édition, présente les algorithmes dans un langage proche
de l’assembleur (MIX) dû à Knuth, ainsi que les analyses mathématiques de leurs
performances. Son importance vient du fait qu’il fut le premier à poser clairement
les bases d’une analyse mathématique des divers algorithmes présentés ; quiconque
est en quête de renseignements sur l’historique de ces notions y trouvera là aussi de
précieuses indications.
En 1981, le premier à notre connaissance, le livre de Greene et Knuth, Mathematics for the Analysis of Algorithms [123], rassemble les outils mathématiques
nécessaires à l’analyse des algorithmes (identités binomiales, relations de récurrence, analyse asymptotique) dans un seul ouvrage. Les fonctions génératrices,
présentes dans tout le livre, y sont davantage vues comme un outil intéressant que
comme la méthode fondamentale qu’elles deviendront plus tard, notamment grâce
aux travaux de Flajolet. Ce livre est presque uniquement centré sur les techniques
mathématiques et ne présente que très peu d’analyses d’algorithmes, restreintes au
hachage.
Le livre de Hofri, Probabilistic Analysis of Algorithms [132], paru en 1987,
présente lui aussi les outils mathématiques de base en un gros chapitre d’une
centaine de pages, cette fois avec un accent plus fort sur les fonctions génératrices et
en incluant par exemple les transformées de Laplace et de Mellin. Le reste du livre
est dédié à l’analyse de divers algorithmes : sur les permutations, pour les réseaux
de télécommunications, et des heuristiques de « bin packing ».
En 1995, une édition remaniée de ce livre est publiée, sous le titre Analysis of
Algorithms – Computational Methods and Mathematical Tools [133]. La première
partie présente, en près de 400 pages, les méthodes : là encore, fonctions génératrices et constructions admissibles, puis un chapitre d’illustrations sur différents
paramètres des permutations, ensuite les transformées de Laplace et de Mellin,
l’asymptotique par analyse de singularité ou méthode de col, quelques résultats
de probabilités : inégalités, marches aléatoires. La deuxième partie traite des
applications : tri (surtout) et recherche (quelques pages sont consacrées aux arbres
binaires de recherche) ; protocoles de communication (dont l’analyse du protocole
en arbre dont nous parlons chapitre 3) ; diverses heuristiques de bin-packing. Les
arbres apparaissent assez peu, dans quelques cas limités.
À peu près à la même époque, le livre de Mahmoud paru en 1992, Evolution
of Random Search Trees [172], apporte une grande avancée dans l’exposition, à
un niveau élémentaire, des méthodes probabilistes et combinatoires pour l’analyse
d’algorithmes, en se concentrant sur les arbres de recherche. Il y est question
d’arbres binaires, m-aires et arbres quadrants que nous traitons aussi, d’arbres kd dont nous ne parlons pas dans ce livre, ainsi que d’arbres digitaux : les tries,
auxquels nous consacrons aussi une part importante, et les arbres digitaux de
recherche, auxquels Mahmoud consacre un chapitre entier alors que leur analyse
ne fait l’objet que d’exercices dans notre livre. Plus précisément, les variables
D Un peu d’histoire. . .
« optimal » pour un ensemble de clés données ; puis arbres binaires de recherche
« équilibrés », soit par hauteur (ce sont les arbres AVL dus à Adel’son-Vel’skii et
Landis [1]), soit par poids ; enfin les arbres-B (pages 451–480) et les arbres digitaux
(pages 481–505). Dans le même esprit que le volume 1, ce volume 3, datant de
1973 pour la première édition, présente les algorithmes dans un langage proche
de l’assembleur (MIX) dû à Knuth, ainsi que les analyses mathématiques de leurs
performances. Son importance vient du fait qu’il fut le premier à poser clairement
les bases d’une analyse mathématique des divers algorithmes présentés ; quiconque
est en quête de renseignements sur l’historique de ces notions y trouvera là aussi de
précieuses indications.
En 1981, le premier à notre connaissance, le livre de Greene et Knuth, Mathematics for the Analysis of Algorithms [123], rassemble les outils mathématiques
nécessaires à l’analyse des algorithmes (identités binomiales, relations de récurrence, analyse asymptotique) dans un seul ouvrage. Les fonctions génératrices,
présentes dans tout le livre, y sont davantage vues comme un outil intéressant que
comme la méthode fondamentale qu’elles deviendront plus tard, notamment grâce
aux travaux de Flajolet. Ce livre est presque uniquement centré sur les techniques
mathématiques et ne présente que très peu d’analyses d’algorithmes, restreintes au
hachage.
Le livre de Hofri, Probabilistic Analysis of Algorithms [132], paru en 1987,
présente lui aussi les outils mathématiques de base en un gros chapitre d’une
centaine de pages, cette fois avec un accent plus fort sur les fonctions génératrices et
en incluant par exemple les transformées de Laplace et de Mellin. Le reste du livre
est dédié à l’analyse de divers algorithmes : sur les permutations, pour les réseaux
de télécommunications, et des heuristiques de « bin packing ».
En 1995, une édition remaniée de ce livre est publiée, sous le titre Analysis of
Algorithms – Computational Methods and Mathematical Tools [133]. La première
partie présente, en près de 400 pages, les méthodes : là encore, fonctions génératrices et constructions admissibles, puis un chapitre d’illustrations sur différents
paramètres des permutations, ensuite les transformées de Laplace et de Mellin,
l’asymptotique par analyse de singularité ou méthode de col, quelques résultats
de probabilités : inégalités, marches aléatoires. La deuxième partie traite des
applications : tri (surtout) et recherche (quelques pages sont consacrées aux arbres
binaires de recherche) ; protocoles de communication (dont l’analyse du protocole
en arbre dont nous parlons chapitre 3) ; diverses heuristiques de bin-packing. Les
arbres apparaissent assez peu, dans quelques cas limités.
À peu près à la même époque, le livre de Mahmoud paru en 1992, Evolution
of Random Search Trees [172], apporte une grande avancée dans l’exposition, à
un niveau élémentaire, des méthodes probabilistes et combinatoires pour l’analyse
d’algorithmes, en se concentrant sur les arbres de recherche. Il y est question
d’arbres binaires, m-aires et arbres quadrants que nous traitons aussi, d’arbres kd dont nous ne parlons pas dans ce livre, ainsi que d’arbres digitaux : les tries,
auxquels nous consacrons aussi une part importante, et les arbres digitaux de
recherche, auxquels Mahmoud consacre un chapitre entier alors que leur analyse
ne fait l’objet que d’exercices dans notre livre. Plus précisément, les variables