Introduction à l'analyse des algorithmes

Couverture
Page de titre
Préface
Notations
CHAPITRE UN : L'ANALYSE D'ALGORITHMES
1.1 Pourquoi analyser un algorithme ?
1.2 Calcul de complexité
1.3 Analyse d'algorithmes
1.4 Analyse en moyenne
1.5 Exemple: l'analyse du tri rapide (Quicksort)
1.6 Approximations asymptotiques
1.7 Distributions
1.8 Algorithmes probabilistes
CHAPITRE DEUX : RELATIONS DE RÉCURRENCE
2.1 Propriétés élémentaires
2.2 Récurrences du premier ordre
2.3 Récurrences non linéaires du premier ordre
2.4 Récurrences d'ordre supérieur
2.5 Méthodes de résolution des récurrences
2.6 Récurrences « diviser pour régner » binaires et nombres binaires
2.7 Récurrences « diviser pour régner » générales
CHAPITRE TROIS : SÉRIES GÉNÉRATRICES
3.1 Séries génératrices ordinaires
3.2 Séries génératrices exponentielles
3.3 Série génératrice solution de récurrences
3.4 Développement de série génératrice
3.5 Transformations par séries génératrices
3.6 Équations fonctionnelles de séries génératrices
3.7 Résolution de la récurrence du tri « médiane de trois » par SGO
3.8 Dénombrer avec les séries génératrices
3.9 La méthode symbolique
3.10 Inversion de Lagrange
3.11 Série génératrice de probabilité
3.12 Séries génératrices bivariées
3.13 Fonctions spéciales
CHAPITRE QUATRE : APPROXIMATIONS ASYMPTOTIQUES
4.1 Notation des approximations asymptotiques
4.2 Développements asymptotiques
4.3 Manipulation des développements asymptotiques
4.4 Approximations asymptotiques des sommes finies
4.5 Sommation d'Euler-Maclaurin
4.6 Asymptotique bivariée
4.7 Méthode de Laplace
4.8 Exemples « normaux » en analyse d'algorithmes
4.9 Exemples de « Poisson » en analyse d'algorithmes
4.10 Asymptotique des séries génératrices
CHAPITRE CINQ : ARBRES
5.1 Arbres binaires
5.2 Arbres et forêts
5.3 Propriétés des arbres
5.4 Algorithmes sur les arbres
5.5 Arbres binaires de recherche
5.6 Longueur de cheminement moyenne des arbres de Catalan
5.7 Longueur de cheminement des arbres binaires de recherche
5.8 Paramètres additifs des arbres aléatoires
5.9 Hauteur
5.10 Résumé des résultats en moyenne sur les propriétés des arbres
5.11 Représentations des arbres et des arbres binaires
5.12 Arbres non ordonnés
5.13 Arbres étiquetés
5.14 Autres types d'arbres
CHAPITRE SIX : PERMUTATIONS
6.1 Propriétés élémentaires des permutations
6.2 Algorithmes sur les permutations
6.3 Représentations des permutations
6.4 Problèmes de dénombrement
6.5 Analyse des propriétes des permutations par les SGCs
6.6 Inversions et tris par insertion
6.7 Maximums de gauche à droite et tri par sélection
6.8 Cycles et permutations in situ
6.9 Paramètres extrémaux
CHAPITRE SEPT : CHAÎNES ET ARBRES DIGITAUX
7.1 Recherche de motifs
7.2 Propriétés combinatoires des suites de bits
7.3 Expressions régulières
7.4 Automates finis et algorithme de Knuth-Morris-Pratt
7.5 Grammaires context-free
7.6 Arbres digitaux
7.7 Algorithmes sur les arbres digitaux
7.8 Propriétés combinatoires des arbres digitaux
7.9 Alphabets de grande taille
CHAPITRE HUIT : MOTS ET MAPPES
8.1 Hachage avec chaînage séparé
8.2 Propriétés élémentaires des mots
8.3 Paradoxe des anniversaires et problème du collectionneur de coupons
8.4 Restrictions sur l'occupation et paramètres extrémaux
8.5 Distributions d'occupation
8.6 Hachage avec adressage ouvert
8.7 Mappes
8.8 Factorisation d'entiers et mappes
Table des théorèmes
Index