xxvi
Table des matières
2.3 Aléa sur les arbres digitaux . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 54
2.3.1 Modèles usuels. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 55
2.3.2 Sources de symboles : aléa sur les clés . . .. . . . . . . . . . . . . . . . . . . . 56
2.3.3 Sources sans mémoire .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 57
2.3.4 Source avec dépendance markovienne . . .. . . . . . . . . . . . . . . . . . . . 58
2.4 Aléa et choix de notations.. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 60
3 Arbres, algorithmes et données . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 61
3.1 Représentation d’expressions . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 61
3.2 Recherche de clés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 63
3.2.1 Arbres binaires de recherche .. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 64
3.2.2 Autres arbres de recherche . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 67
3.2.3 Structures digitales et dictionnaires.. . . . . .. . . . . . . . . . . . . . . . . . . . 75
3.3 Tri d’un ensemble de clés . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 78
3.3.1 Tri rapide .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 78
3.3.2 Recherche par rang . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 90
3.3.3 Tas, files de priorité, et tri par tas . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 91
3.3.4 Tri radix .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 93
3.4 Modélisations par des structures arborescentes . . .. . . . . . . . . . . . . . . . . . . . 95
3.4.1 Arbres d’expressions booléennes . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 95
3.4.2 Arbres de génération . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 99
3.4.3 Arbres Union-Find . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 101
3.4.4 Algorithme des buveurs de bière.. . . . . . . . .. . . . . . . . . . . . . . . . . . . . 106
3.4.5 Protocole en arbre . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 107
3.4.6 Échantillonnage adaptatif . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 108
3.4.7 Index dans les bases de données . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 111
3.4.8 Tables de routage IP . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 112
3.4.9 Compression de données .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 112
Partie II Analyses
4 Approche combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 121
4.1 Les arbres binaires.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 121
4.1.1 Dénombrement . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 122
4.1.2 Longueur de cheminement .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 125
4.1.3 Paramètres additifs . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 133
4.2 Familles simples d’arbres . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 135
4.2.1 L’exemple des expressions (mathématiques) .. . . . . . . . . . . . . . . . 135
4.2.2 Dénombrement exact .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 137
4.2.3 Dénombrement asymptotique .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 139
4.2.4 Paramètres additifs sur les familles simples d’arbres . . . . . . . . 141
4.2.5 Un exemple : complexité de la différentiation . . . . . . . . . . . . . . . 143
4.3 Tas .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 146
4.3.1 Nombre de tas de taille donnée . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 146
4.3.2 Dénombrement asymptotique des tas. . . . .. . . . . . . . . . . . . . . . . . . . 151
4.3.3 Complexité des opérations sur un tas . . . . .. . . . . . . . . . . . . . . . . . . . 155
Table des matières
2.3 Aléa sur les arbres digitaux . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 54
2.3.1 Modèles usuels. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 55
2.3.2 Sources de symboles : aléa sur les clés . . .. . . . . . . . . . . . . . . . . . . . 56
2.3.3 Sources sans mémoire .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 57
2.3.4 Source avec dépendance markovienne . . .. . . . . . . . . . . . . . . . . . . . 58
2.4 Aléa et choix de notations.. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 60
3 Arbres, algorithmes et données . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 61
3.1 Représentation d’expressions . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 61
3.2 Recherche de clés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 63
3.2.1 Arbres binaires de recherche .. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 64
3.2.2 Autres arbres de recherche . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 67
3.2.3 Structures digitales et dictionnaires.. . . . . .. . . . . . . . . . . . . . . . . . . . 75
3.3 Tri d’un ensemble de clés . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 78
3.3.1 Tri rapide .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 78
3.3.2 Recherche par rang . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 90
3.3.3 Tas, files de priorité, et tri par tas . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 91
3.3.4 Tri radix .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 93
3.4 Modélisations par des structures arborescentes . . .. . . . . . . . . . . . . . . . . . . . 95
3.4.1 Arbres d’expressions booléennes . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 95
3.4.2 Arbres de génération . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 99
3.4.3 Arbres Union-Find . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 101
3.4.4 Algorithme des buveurs de bière.. . . . . . . . .. . . . . . . . . . . . . . . . . . . . 106
3.4.5 Protocole en arbre . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 107
3.4.6 Échantillonnage adaptatif . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 108
3.4.7 Index dans les bases de données . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 111
3.4.8 Tables de routage IP . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 112
3.4.9 Compression de données .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 112
Partie II Analyses
4 Approche combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 121
4.1 Les arbres binaires.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 121
4.1.1 Dénombrement . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 122
4.1.2 Longueur de cheminement .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 125
4.1.3 Paramètres additifs . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 133
4.2 Familles simples d’arbres . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 135
4.2.1 L’exemple des expressions (mathématiques) .. . . . . . . . . . . . . . . . 135
4.2.2 Dénombrement exact .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 137
4.2.3 Dénombrement asymptotique .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 139
4.2.4 Paramètres additifs sur les familles simples d’arbres . . . . . . . . 141
4.2.5 Un exemple : complexité de la différentiation . . . . . . . . . . . . . . . 143
4.3 Tas .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 146
4.3.1 Nombre de tas de taille donnée . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 146
4.3.2 Dénombrement asymptotique des tas. . . . .. . . . . . . . . . . . . . . . . . . . 151
4.3.3 Complexité des opérations sur un tas . . . . .. . . . . . . . . . . . . . . . . . . . 155