Introduction à l'analyse des algorithmes

L'informatique met en jeu des programmes et des systèmes chaque jour plus complexes. Cependant, de tels systèmes ne s'appuient que sur la résolution d'un petit nombre de " grands " algorithmes dont le rôle est souvent critique. L'analyse d'algorithmes se donne pour objectif de se caractériser précisément les performances de ces algorithmes fondamentaux. Ce livre présente une étude approfondie des techniques fondamentales utilisées en analyse mathématique d'algorithmes. Les sujets abordés par les auteurs gravitent auteur de thèmes mathématiques, notamment les mathématiques discrètes, l'analyse réelle élémentaire, et la combinatoire, mais également autour de thèmes proprement informatiques, en particulier les algorithmes et les structures de données. Ils se sont attachés principalement à l'analyse " en moyenne " et à l'analyse " probabilistique ", tout en introduisant les outils nécessaires à l'analyse " dans le pire des cas " ou à l'analyse de " complexité ". 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