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.
Author(s): Thomas H. Cormen; Charles Eric Leiserson; Ronald L. Rivest; Clifford Stein
Edition: 3
Publisher: Dunod
Year: 2010
Language: French
Pages: 1188
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 nud
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
