Algorithmique: cours avec 957 exercices et 158 problèmes

Description

Ce livre de cours traduit de l'américain, sans équivalent et d'accès facile, est une introduction complète à l'algorithmique et s'adresse aussi bien aux étudiants qu'aux professionnels en informatique. L'éventail des algorithmes étudiés va des plus classiques (tris, hachage...) aux plus récents (algorithmes parallèles...) permettant ainsi de passer progressivement des notions élémentaires aux thèmes les plus pointus. Les algorithmes sont présentés dans un pseudo-code proche des langages Pascal, C et Fortan, ce qui les rend très faciles à comprendre et à implémenter. Ils sont complétés par des preuves mathématiques et illustés par de nombreux exemples. Au total, plus de 920 exercices et 140 problèmes sont proposés. Cette 3ème édition, révisée et mise à jour, comporte deux nouveaux chapitres, l'un sur les arbres de Van Emde Boas et l'autre sur les algorithmes multithreads. Plusieurs nouveaux énoncés d'exercices et de problèmes ont été ajoutés à cette nouvelle édition. Couverture Page de titre PRÉFACE À L'ÉDITION FRANÇAISE PRÉFACE PARTIE 1 . INTRODUCTION CHAPITRE 1 . RÔLE DES ALGORITHMES EN INFORMATIQUE 1.1 Algorithmes Exercices 1.2 Algorithmes en tant que technologie Exercices PROBLÈMES CHAPITRE 2 . PREMIERS PAS 2.1 Tri par insertion Exercices 2.2 Analyse des algorithmes Exercices 2.3 Conception des algorithmes Exercices PROBLÈMES CHAPITRE 3 . CROISSANCE DES FONCTIONS 3.1 Notation asymptotique Exercices 3.2 Notations standard et fonctions classiques Exercices PROBLÈMES CHAPITRE 4 . DIVISER POUR RÉGNER 4.1 Le problème du sous-tableau maximal Exercices 4.2 Algorithme de Strassen pour la multiplication matricielle Exercices 4.3 La méthode de substitution pour la résolution des récurrences Exercices 4.4 La méthode de l'arbre récursif pour la résolution des récurrences Exercices 4.5 La méthode générale pour la résolution des récurrences Exercices 4.6 Démonstration du théorème général Exercices PROBLÈMES CHAPITRE 5 . ANALYSE PROBABILISTE ET ALGORITHMES RANDOMISÉS 5.1 Le problème de l'embauche Exercices 5.2 Variables aléatoires indicatrices Exercices 5.3 Algorithmes randomisés Exercices 5.4 Analyse probabiliste et autres emplois des variables aléatoires indicatrices Exercices PROBLÈMES PARTIE 2 . TRI ET RANGS CHAPITRE 6 . TRI PAR TAS 6.1 Tas Exercices 6.2 Conservation de la propriété de tas Exercices 6.3 Construction d'un tas Exercices 6.4 Algorithme du tri par tas Exercices 6.5 Files de priorités Exercices PROBLÈMES CHAPITRE 7 . TRI RAPIDE 7.1 Description du tri rapide Exercices 7.2 Performances du tri rapide Exercices 7.3 Une version randomisée du tri rapide Exercices 7.4 Analyse du tri rapide Exercices PROBLÈMES CHAPITRE 8 . TRI EN TEMPS LINÉAIRE 8.1 Minorants pour le tri Exercices 8.2 Tri par dénombrement Exercices 8.3 Tri par base Exercices 8.4 Tri par paquets Exercices PROBLÈMES CHAPITRE 9 . MÉDIANS ET RANGS 9.1 Minimum et maximum Exercices 9.2 Sélection en temps espéré linéaire Exercices 9.3 Sélection en temps linéaire dans le cas le plus défavorable Exercices PROBLÈMES PARTIE 3 . STRUCTURES DE DONNÉES CHAPITRE 10 . STRUCTURES DE DONNÉES ÉLÉMENTAIRES 10.1 Piles et files Exercices 10.2 Listes chaÎnées Exercices 10.3 Implémentation de pointeurs et d'objets Exercices 10.4 Représentation des arbres Exercices PROBLÈMES CHAPITRE 11 . TABLES DE HACHAGE 11.1 Tables à adressage direct Exercices 11.2 Tables de hachage Exercices 11.3 Fonctions de hachage Exercices 11.4 Adressage ouvert Exercices 11.5 Hachage parfait Exercices PROBLÈMES CHAPITRE 12 . ARBRES BINAIRES DE RECHERCHE 12.1 Qu'est-ce qu'un arbre binaire de recherche? Exercices 12.2 Requête dans un arbre binaire de recherche Exercices 12.3 Insertion et suppression Exercices 12.4 Arbres binaires de recherche construits aléatoirement Exercices PROBLÈMES CHAPITRE 13 . ARBRES ROUGE-NOIR 13.1 Propriétés des arbres rouge-noir Exercices 13.2 Rotations Exercices 13.3 Insertion Exercices 13.4 Suppression Exercices PROBLÈMES CHAPITRE 14 . EXTENSION DES STRUCTURES DE DONNÉES 14.1 Rangs dynamiques Exercices 14.2 Comment étendre une structure de données Exercices 14.3 Arbres d'intervalles Exercices PROBLÈMES PARTIE 4 . TECHNIQUES AVANCÉES DE CONCEPTION ET D'ANALYSE CHAPITRE 15 . PROGRAMMATION DYNAMIQUE 15.1 découpe de barres Exercices 15.2 Multiplications matricielles enchaînées Exercices 15.3 Éléments de programmation dynamique Exercices 15.4 Plus longue sous-séquence commune Exercices 15.5 Arbres binaires de recherche optimaux Exercices PROBLÈMES CHAPITRE 16 . ALGORITHMES GLOUTONS 16.1 Un problème de choix d'activités Exercices 16.2 Éléments de la stratégie gloutonne Exercices 16.3 Codages de Huffman Exercices 16.4 Matroïdes et méthodes gloutonnes Exercices 16.5 Un problème d'ordonnancement de tâches en tant que matroïde Exercices PROBLÈMES CHAPITRE 17 . ANALYSE AMORTIE 17.1 Analyse de l'agrégat Exercices 17.2 Méthode comptable Exercices 17.3 Méthode du potentiel Exercices 17.4 Tables dynamiques Exercices PROBLÈMES PARTIE 5 . STRUCTURES DE DONNÉES AVANCÉES CHAPITRE 18 . B-ARBRES 18.1 Définition d'un B-arbre Exercices 18.2 Opérations fondamentales sur les B-arbres Exercices 18.3 Suppression d'une clé dans un B-arbre Exercices PROBLÈMES CHAPITRE 19 . TAS DE FIBONACCI 19.1 Structure des tas de Fibonacci 19.2 Opérations sur les tas fusionnables Exercices 19.3 Diminution d'une clé et suppression d'un nœud Exercices 19.4 Borne du degré maximal Exercices PROBLÈMES CHAPITRE 20 . ARBRES DE VAN EMDE BOAS 20.1 Approches préliminaires Exercices 20.2 Une structure récursive Exercices 20.3 L'arbre de van Emde Boas Exercices PROBLÈMES CHAPITRE 21 . STRUCTURES DE DONNÉES POUR ENSEMBLES DISJOINTS 21.1 Opérations sur les ensembles disjoints Exercices 21.2 Représentation d'ensembles disjoints par des listes chaÎnées Exercices 21.3 Forêts d'ensembles disjoints Exercices 21.4 Analyse de l'union par rang avec compression de chemin Exercices PROBLÈMES PARTIE 6 . ALGORITHMES POUR LES GRAPHES CHAPITRE 22 . ALGORITHMES ÉLÉMENTAIRES POUR LES GRAPHES 22.1 Représentation des graphes Exercices 22.2 Parcours en largeur Exercices 22.3 Parcours en profondeur Exercices 22.4 Tri topologique Exercices 22.5 Composantes fortement connexes Exercices PROBLÈMES CHAPITRE 23 . ARBRES COUVRANTS MINIMAUX 23.1 Construction d'un arbre couvrant minimal Exercices 23.2 Algorithmes de Kruskal et de Prim Exercices PROBLÈMES CHAPITRE 24 . PLUS COURTS CHEMINS À ORIGINE UNIQUE 24.1 Algorithme de Bellman-Ford Exercices 24.2 Plus courts chemins à origine unique dans les graphes orientés sans circuit Exercices 24.3 Algorithme de Dijkstra Exercices 24.4 Contraintes de différence et plus courts chemins Exercices 24.5 Démonstrations des propriétés de plus court chemin Exercices PROBLÈMES CHAPITRE 25 . PLUS COURTS CHEMINS ENTRE TOUTES PAIRES DE SOMMETS 25.1 Plus courts chemins et multiplication de matrices Exercices 25.2 L'algorithme de Floyd-Warshall Exercices 25.3 Algorithme de Johnson pour les graphes peu denses Exercices PROBLÈMES CHAPITRE 26 . FLOT MAXIMUM 26.1 Réseaux de flot Exercices 26.2 La méthode de Ford-Fulkerson Exercices 26.3 Couplage biparti maximum Exercices 26.4 Algorithmes pousser-réétiqueter Exercices 26.5 Algorithme réétiqueter-vers-l'avant Exercices PROBLÈMES PARTIE 7 . MORCEAUX CHOISIS CHAPITRE 27 . ALGORITHMES MULTITHREAD 27.1 Fondements du multithread dynamique Exercices 27.2 Multiplication matricielle multithread Exercices 27.3 Tri par fusion multithread Exercices PROBLÈMES CHAPITRE 28 . CALCUL MATRICIEL 28.1 Résolution de systèmes d'équations linéaires Exercices 28.2 Inversion des matrices Exercices 28.3 Matrices symétriques définies positives et approximation par la méthode des moindres carrés Exercices PROBLÈMES CHAPITRE 29 . PROGRAMMATION LINÉAIRE 29.1 Forme standard et forme canonique Exercices 29.2 Formulation de problèmes comme programmes linéaires Exercices 29.3 Algorithme du simplexe Exercices 29.4 Dualité Exercices 29.5 La solution réalisable de base initiale Exercices PROBLÈMES CHAPITRE 30 . POLYNÔMES ET TRANSFORMÉE DE FOURIER RAPIDE 30.1 Représentation des polynômes Exercices 30.2 Transformée discrète de Fourier et transformée rapide de Fourier Exercices 30.3 Implémentations efficaces de la transformée rapide de Fourier Exercices PROBLÈMES CHAPITRE 31 . ALGORITHMES DE LA THÉORIE DES NOMBRES 31.1 Notions élémentaires de la théorie des nombres Exercices 31.2 Plus grand commun diviseur Exercices 31.3 Arithmétique modulaire Exercices 31.4 Résolution d'équations linéaires modulaires Exercices 31.5 Théorème du reste chinois Exercices 31.6 Puissances d'un élément Exercices 31.7 Le cryptosystème à clés publiques RSA Exercices 31.8 Test de primarité Exercices 31.9 Factorisation des entiers Exercices PROBLÈMES CHAPITRE 32 . RECHERCHE DE CHAÎNES DE CARACTÈRES 32.1 Algorithme naïf de recherche de chaîne de caractères Exercices 32.2 Algorithme de Rabin-Karp Exercices 32.3 Recherche de chaîne de caractères au moyen d'automates finis Exercices 32.4 Algorithme de Knuth-Morris-Pratt Exercices PROBLÈMES CHAPITRE 33 . GÉOMÉTRIE ALGORITHMIQUE 33.1 Propriétés des segments de droite Exercices 33.2 Déterminer si deux segments donnés se coupent Exercices 33.3 Recherche de l'enveloppe convexe Exercices 33.4 Recherche des deux points les plus rapprochés Exercices PROBLÈMES CHAPITRE 34 . NP-COMPLÉTUDE 34.1 Temps polynomial Exercices 34.2 Vérification en temps polynomial Exercices 34.3 NP-complétude et réductibilité Exercices 34.4 Preuves de NP-complétude Exercices 34.5 Problèmes NP-complets Exercices PROBLÈMES CHAPITRE 35 . ALGORITHMES D'APPROXIMATION 35.1 Problème de la couverture de sommets Exercices 35.2 Problème du voyageur de commerce Exercices 35.3 Problème de la couverture d'ensemble Exercices 35.4 Randomisation et programmation linéaire Exercices 35.5 Problème de la somme de sous-ensemble Exercices PROBLÈMES ANNEXES. ÉLÉMENTS DE MATHÉMATIQUES ANNEXE A . SOMMES A.1 Formules et propriétés des sommes Exercices A.2 Bornes des sommes Exercices PROBLÈMES ANNEXE B . ENSEMBLES, ETC B.1 Ensembles Exercices B.2 Relations Exercices B.3 Fonctions Exercices B.4 Graphes Exercices B.5 Arbres Exercices PROBLÈMES ANNEXE C . DÉNOMBREMENT ET PROBABiliTÉS C.1 Dénombrement Exercices C.2 Probabilités Exercices C.3 Variables aléatoires discrètes Exercices C.4 Distributions géométrique et binomiale Exercices C.5 Queues de la distribution binomiale Exercices PROBLÈMES ANNEXE D . MATRICES D.1 Matrices et opérations matricielles Exercices D.2 Propriétés fondamentales des matrices Exercices PROBLÈMES BIBLIOGRAPHIE INDEX