xii
Avant-propos
structures arborescentes, est utile mais pas indispensable ; en outre, il y a plusieurs
niveaux de lecture de ce livre, selon que la lectrice/le lecteur souhaite plutôt
utiliser algorithmiquement un résultat donné, ou maîtriser quelques méthodes de
démonstration.
Possibilités de lecture (voir l’illustration ci-dessous) Les chapitres 1 et 2 pourront
servir de chapitres de référence plutôt qu’être lus en tant que tels. Parmi les
chapitres 3 à 9, plusieurs choix pourront être retenus selon les intérêts de la
lectrice/du lecteur ou l’orientation que cette personne souhaiterait donner à un cours
qui serait basé sur ce livre.
Si l’intérêt porte essentiellement sur les algorithmes, le chapitre 3 (arbres comme
modèles d’analyse d’algorithmes) est fondamental ; il sera ensuite loisible de
choisir, dans chaque chapitre, les sections qui mettent en perspective les résultats
mathématiques sur les paramètres des structures arborescentes et les relient aux
performances des algorithmes les utilisant. Si l’accent est mis sur la combinatoire
analytique, le choix portera sur les chapitres 4 (modèle combinatoire pour plusieurs
familles d’arbres), 7 (structures digitales), la seconde partie du chapitre 8 (arbres
quadrants) et la première partie du chapitre 9 (urnes de Pólya). Si l’accent est
mis sur l’analyse probabiliste, le choix portera prioritairement sur les chapitres 5
(processus de branchement) et 6 (arbres binaires de recherche), puis sur la première
partie du chapitre 8 et le chapitre 9 pour aborder des extensions des arbres binaires
de recherche.
Style Le style est celui de Springer. Ce style a parfois induit une lisibilité réduite.
Par exemple, la fin des définitions n’est signalée que par un saut de ligne et non par
un changement de fonte.
Remerciements Nous remercions ici nos collègues qui ont relu tout ou partie
des différentes versions du livre : Marie-Louise Bruner, Élie de Panafieu, Philippe
Avant-propos
structures arborescentes, est utile mais pas indispensable ; en outre, il y a plusieurs
niveaux de lecture de ce livre, selon que la lectrice/le lecteur souhaite plutôt
utiliser algorithmiquement un résultat donné, ou maîtriser quelques méthodes de
démonstration.
Possibilités de lecture (voir l’illustration ci-dessous) Les chapitres 1 et 2 pourront
servir de chapitres de référence plutôt qu’être lus en tant que tels. Parmi les
chapitres 3 à 9, plusieurs choix pourront être retenus selon les intérêts de la
lectrice/du lecteur ou l’orientation que cette personne souhaiterait donner à un cours
qui serait basé sur ce livre.
Si l’intérêt porte essentiellement sur les algorithmes, le chapitre 3 (arbres comme
modèles d’analyse d’algorithmes) est fondamental ; il sera ensuite loisible de
choisir, dans chaque chapitre, les sections qui mettent en perspective les résultats
mathématiques sur les paramètres des structures arborescentes et les relient aux
performances des algorithmes les utilisant. Si l’accent est mis sur la combinatoire
analytique, le choix portera sur les chapitres 4 (modèle combinatoire pour plusieurs
familles d’arbres), 7 (structures digitales), la seconde partie du chapitre 8 (arbres
quadrants) et la première partie du chapitre 9 (urnes de Pólya). Si l’accent est
mis sur l’analyse probabiliste, le choix portera prioritairement sur les chapitres 5
(processus de branchement) et 6 (arbres binaires de recherche), puis sur la première
partie du chapitre 8 et le chapitre 9 pour aborder des extensions des arbres binaires
de recherche.
Style Le style est celui de Springer. Ce style a parfois induit une lisibilité réduite.
Par exemple, la fin des définitions n’est signalée que par un saut de ligne et non par
un changement de fonte.
Remerciements Nous remercions ici nos collègues qui ont relu tout ou partie
des différentes versions du livre : Marie-Louise Bruner, Élie de Panafieu, Philippe