488
D Un peu d’histoire. . .
Également dans les années 80 paraissent les premiers résultats de Devroye sur
la hauteur de différents arbres de recherche qui sont en fait des résultats de grandes
déviations et s’appuient sur des processus de branchement et des marches aléatoires
branchantes. Devroye reprend et formalise ces résultats dans son cours de 1998 [59],
Branching Processes and Their Applications in the Analysis of Tree Structures
and Tree Algorithms. Dans les années 90, de plus en plus de probabilistes se
rapprochent de l’analyse d’algorithmes, tels Biggins par exemple, qui dans un article
de 1997 [27] transfère un résultat purement probabiliste sur les marches aléatoires
branchantes à la hauteur des arbres binaires de recherche.
Du côté des probabilistes, le formalisme de Neveu sur les arbres est explicité
en 1986 [194]. C’est celui qui est utilisé dans ce livre. L’intérêt pour les arbres
aléatoires grandit, les processus de branchement profitent de cet intérêt, et lors
d’un workshop de 1994 sur ce thème sont diffusés les premiers concepts fondateurs
d’arbre biaisé par Lyons, Pemantle et Peres [171]. Dans le riche livre de Peres [205]
correspondant à son cours à Saint-Flour en 1997, Probability on trees : an
introductory climb, les arbres sont aléatoires, ils peuvent être de Galton-Watson,
biaisés, couvrants. En outre, des objets mathématiques plus élaborés sont définis sur
des arbres : des mesures, la dimension de Hausdorff de la frontière, des marches
aléatoires. Les arbres aléatoires sont également au cœur du cours de Duquesne et Le
Gall [72] en 2000, Random Trees, Levy Processes and Spatial Branching Processes.
Les conditions sont réunies pour que les développements probabilistes autour
des arbres aléatoires puissent à la fois être utilisés en analyse d’algorithmes et se
nourrir de nouvelles motivations algorithmiques. A l’instar de Devroye, plusieurs
cours manifestent de cet échange fructueux : le cours de Neininger [191] à Graz
en 2006, Probabilistic analysis of algorithms, stochastic fixed-point equations and
ideal metrics, met l’accent sur la méthode de contraction, et les objets étudiés
sont les arbres de recherche (binaires, m-aires), avec quelques applications à des
algorithmes. Le cours de Marckert [178] à Graz en 2009, Limit of random walks
and of random trees, marque une progression vers la réunion de plusieurs pôles :
probabilités sophistiquées, motivations algorithmiques et méthodes combinatoires.
En outre, la place naturelle prise par les mathématiques discrètes (à travers les
marches aléatoires, les arbres, les graphes ou les cartes) est complétée par l’étude
des limites continues de ces processus aléatoires. Le mouvement brownien et ses
proches (excursion brownienne, carte brownienne, serpent brownien) se mêlent à
l’histoire. Une belle synthèse sur le hachage et les fonctions de parking, en termes
de processus discrets et continus est écrite à ce propos en 2003 par Chassaing et
Flajolet [34].
Ainsi les liens se resserrent entre communautés, concomitamment à l’essor de
la combinatoire analytique, qui devient autour de Flajolet l’outil mathématique
fondamental dans l’analyse d’algorithmes. L’ouvrage de référence, fruit de plus de
vingt (trente ?) années foisonnantes de résultats et de maturation, est le livre de
Flajolet et Sedgewick Analytic Combinatorics [94] paru en 2009. Il y est exposé
comment, grâce à la méthode symbolique, les structures combinatoires encapsulées
dans des séries génératrices conduisent « automatiquement » à des équations sur ces
D Un peu d’histoire. . .
Également dans les années 80 paraissent les premiers résultats de Devroye sur
la hauteur de différents arbres de recherche qui sont en fait des résultats de grandes
déviations et s’appuient sur des processus de branchement et des marches aléatoires
branchantes. Devroye reprend et formalise ces résultats dans son cours de 1998 [59],
Branching Processes and Their Applications in the Analysis of Tree Structures
and Tree Algorithms. Dans les années 90, de plus en plus de probabilistes se
rapprochent de l’analyse d’algorithmes, tels Biggins par exemple, qui dans un article
de 1997 [27] transfère un résultat purement probabiliste sur les marches aléatoires
branchantes à la hauteur des arbres binaires de recherche.
Du côté des probabilistes, le formalisme de Neveu sur les arbres est explicité
en 1986 [194]. C’est celui qui est utilisé dans ce livre. L’intérêt pour les arbres
aléatoires grandit, les processus de branchement profitent de cet intérêt, et lors
d’un workshop de 1994 sur ce thème sont diffusés les premiers concepts fondateurs
d’arbre biaisé par Lyons, Pemantle et Peres [171]. Dans le riche livre de Peres [205]
correspondant à son cours à Saint-Flour en 1997, Probability on trees : an
introductory climb, les arbres sont aléatoires, ils peuvent être de Galton-Watson,
biaisés, couvrants. En outre, des objets mathématiques plus élaborés sont définis sur
des arbres : des mesures, la dimension de Hausdorff de la frontière, des marches
aléatoires. Les arbres aléatoires sont également au cœur du cours de Duquesne et Le
Gall [72] en 2000, Random Trees, Levy Processes and Spatial Branching Processes.
Les conditions sont réunies pour que les développements probabilistes autour
des arbres aléatoires puissent à la fois être utilisés en analyse d’algorithmes et se
nourrir de nouvelles motivations algorithmiques. A l’instar de Devroye, plusieurs
cours manifestent de cet échange fructueux : le cours de Neininger [191] à Graz
en 2006, Probabilistic analysis of algorithms, stochastic fixed-point equations and
ideal metrics, met l’accent sur la méthode de contraction, et les objets étudiés
sont les arbres de recherche (binaires, m-aires), avec quelques applications à des
algorithmes. Le cours de Marckert [178] à Graz en 2009, Limit of random walks
and of random trees, marque une progression vers la réunion de plusieurs pôles :
probabilités sophistiquées, motivations algorithmiques et méthodes combinatoires.
En outre, la place naturelle prise par les mathématiques discrètes (à travers les
marches aléatoires, les arbres, les graphes ou les cartes) est complétée par l’étude
des limites continues de ces processus aléatoires. Le mouvement brownien et ses
proches (excursion brownienne, carte brownienne, serpent brownien) se mêlent à
l’histoire. Une belle synthèse sur le hachage et les fonctions de parking, en termes
de processus discrets et continus est écrite à ce propos en 2003 par Chassaing et
Flajolet [34].
Ainsi les liens se resserrent entre communautés, concomitamment à l’essor de
la combinatoire analytique, qui devient autour de Flajolet l’outil mathématique
fondamental dans l’analyse d’algorithmes. L’ouvrage de référence, fruit de plus de
vingt (trente ?) années foisonnantes de résultats et de maturation, est le livre de
Flajolet et Sedgewick Analytic Combinatorics [94] paru en 2009. Il y est exposé
comment, grâce à la méthode symbolique, les structures combinatoires encapsulées
dans des séries génératrices conduisent « automatiquement » à des équations sur ces