D Un peu d’histoire. . .
487
aléatoires qui apparaissent sont étudiées dans le livre de Mahmoud essentiellement
par fonctions génératrices, et la partie probabiliste est utilisée pour le traitement de
l’analyse en moyenne. Par exemple, les polynômes de niveau utiles pour l’analyse
du profil des arbres binaires de recherche sont évoqués, étudiés en moyenne, alors
que leur utilisation en tant que processus ne viendra qu’un peu plus tard. De même,
la notion de martingale apparaît dans le livre pour citer le résultat de Régnier [219]
de 1989 sur les arbres binaires de recherche. En exposant très pédagogiquement,
dès 1992, l’état de l’art sur les arbres de recherche et leur évolution (ce qui
évoque en termes probabilistes le processus d’arbre sous-jacent), ce livre a constitué
une référence incontournable pour les probabilistes souhaitant se rapprocher de
l’analyse d’algorithmes.
En 1996, paraît le livre de Sedgewick et Flajolet An Introduction to the
Analysis of Algorithms [232] (aussi disponible en français). Ce livre se concentre
sur les techniques mathématiques de base d’analyse d’algorithmes et est destiné
à servir de cours d’introduction pour un public ayant déjà quelques bases en
mathématiques discrètes et en programmation. Certains objets d’étude sont communs avec le présent livre (algorithme de tri rapide, arbres de Catalan, arbres
binaires de recherche, tries). Les méthodes employées sont principalement à base
de séries génératrices bivariées et l’approche est plutôt combinatoire (comme dans
le chapitre 4 de notre livre).
Le livre de Szpankowski Average Case Analysis of Algorithms on Sequences
[239] et celui de Jacquet et Szpankowski Analytic Pattern Matching : from DNA
to Twitter [146] s’intéressent principalement aux algorithmes maniant les mots
(ou chaînes de caractères) et les structures de données dédiées. L’orientation est
plutôt méthodologique et les deux principales approches pour l’étude de structures
discrètes sont présentées, et ce, à un niveau plus avancé que dans ce livre :
les méthodes probabilistes (avec par exemple les inégalités de moments, grandes
déviations, martingales, théorie ergodique) et les méthodes analytiques reposant sur
l’utilisation de séries génératrices (analyse de singularité, point de col, transformée
de Mellin, dépoissonisation). Si les méthodes sont similaires à celles de ce livre
(bien que souvent présentées assez différemment), les seuls arbres étudiés sont les
arbres digitaux (tries, arbre digital de recherche, arbres Patricia et bien d’autres
généralisations). Les analyses de ces structures sont plus approfondies et variées
que celles du chapitre 7, et sont souvent aussi plus difficiles.
Les débuts de l’analyse en moyenne d’algorithmes sont d’abord dus à Knuth
au début des années 60, et les ouvrages fondateurs sont précisément les premiers
volumes de sa série The Art of Computer Programming, parus au tournant des
années 60 et 70.
Or, parler d’analyse en moyenne nécessite des notions de probabilités élémentaires ; l’utilisation d’outils un peu plus élaborés tels que les martingales, la
distinction des différents types de convergence, la méthode de contraction, tout ceci
se développe un peu plus tard, essentiellement à partir des années 80 et 90. Dans ces
années-là, probabilistes et informaticiens collaborent, notamment Pittel, Smythe,
Mahmoud et de nombreux travaux en sont le fruit, par exemple [174–176, 237].
487
aléatoires qui apparaissent sont étudiées dans le livre de Mahmoud essentiellement
par fonctions génératrices, et la partie probabiliste est utilisée pour le traitement de
l’analyse en moyenne. Par exemple, les polynômes de niveau utiles pour l’analyse
du profil des arbres binaires de recherche sont évoqués, étudiés en moyenne, alors
que leur utilisation en tant que processus ne viendra qu’un peu plus tard. De même,
la notion de martingale apparaît dans le livre pour citer le résultat de Régnier [219]
de 1989 sur les arbres binaires de recherche. En exposant très pédagogiquement,
dès 1992, l’état de l’art sur les arbres de recherche et leur évolution (ce qui
évoque en termes probabilistes le processus d’arbre sous-jacent), ce livre a constitué
une référence incontournable pour les probabilistes souhaitant se rapprocher de
l’analyse d’algorithmes.
En 1996, paraît le livre de Sedgewick et Flajolet An Introduction to the
Analysis of Algorithms [232] (aussi disponible en français). Ce livre se concentre
sur les techniques mathématiques de base d’analyse d’algorithmes et est destiné
à servir de cours d’introduction pour un public ayant déjà quelques bases en
mathématiques discrètes et en programmation. Certains objets d’étude sont communs avec le présent livre (algorithme de tri rapide, arbres de Catalan, arbres
binaires de recherche, tries). Les méthodes employées sont principalement à base
de séries génératrices bivariées et l’approche est plutôt combinatoire (comme dans
le chapitre 4 de notre livre).
Le livre de Szpankowski Average Case Analysis of Algorithms on Sequences
[239] et celui de Jacquet et Szpankowski Analytic Pattern Matching : from DNA
to Twitter [146] s’intéressent principalement aux algorithmes maniant les mots
(ou chaînes de caractères) et les structures de données dédiées. L’orientation est
plutôt méthodologique et les deux principales approches pour l’étude de structures
discrètes sont présentées, et ce, à un niveau plus avancé que dans ce livre :
les méthodes probabilistes (avec par exemple les inégalités de moments, grandes
déviations, martingales, théorie ergodique) et les méthodes analytiques reposant sur
l’utilisation de séries génératrices (analyse de singularité, point de col, transformée
de Mellin, dépoissonisation). Si les méthodes sont similaires à celles de ce livre
(bien que souvent présentées assez différemment), les seuls arbres étudiés sont les
arbres digitaux (tries, arbre digital de recherche, arbres Patricia et bien d’autres
généralisations). Les analyses de ces structures sont plus approfondies et variées
que celles du chapitre 7, et sont souvent aussi plus difficiles.
Les débuts de l’analyse en moyenne d’algorithmes sont d’abord dus à Knuth
au début des années 60, et les ouvrages fondateurs sont précisément les premiers
volumes de sa série The Art of Computer Programming, parus au tournant des
années 60 et 70.
Or, parler d’analyse en moyenne nécessite des notions de probabilités élémentaires ; l’utilisation d’outils un peu plus élaborés tels que les martingales, la
distinction des différents types de convergence, la méthode de contraction, tout ceci
se développe un peu plus tard, essentiellement à partir des années 80 et 90. Dans ces
années-là, probabilistes et informaticiens collaborent, notamment Pittel, Smythe,
Mahmoud et de nombreux travaux en sont le fruit, par exemple [174–176, 237].