Algorithmique
Cours avec 957 exercices et 158 problèmes
Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest
Clifford Stein
Dunod
Préface à l'édition françaiseV
PréfaceIX
Partie 1 ¤ Introduction
Chapitre 1 ¤ Rôle des algorithmes en informatique
3
1.1 Algorithmes3
Exercices8
1.2 Algorithmes en tant que technologie9
Exercices11
Problèmes
12
Chapitre 2 ¤ Premiers pas
13
2.1 Tri par insertion13
Exercices19
2.2 Analyse des algorithmes19
Exercices25
2.3 Conception des algorithmes26
Exercices34
Problèmes
35
Chapitre 3 ¤ Croissance des fonctions
39
3.1 Notation asymptotique40
Exercices48
3.2 Notations standard et fonctions classiques49
Exercices55
Problèmes
55
Chapitre 4 ¤ Diviser pour régner
59
4.1 Le problème du sous-tableau maximal62
Exercices68
4.2 Algorithme de Strassen pour la multiplication matricielle69
Exercices75
4.3 La méthode de substitution pour la résolution des récurrences76
Exercices80
4.4 La méthode de l'arbre récursif pour la résolution des récurrences81
Exercices85
4.5 La méthode générale pour la résolution des récurrences86
Exercices89
4.6 Démonstration du théorème général89
Exercices97
Problèmes
98
Chapitre 5 ¤ Analyse probabiliste et algorithmes randomisés
105
5.1 Le problème de l'embauche105
Exercices108
5.2 Variables aléatoires indicatrices109
Exercices112
5.3 Algorithmes randomisés113
Exercices118
5.4 Analyse probabiliste et autres emplois des variables aléatoires indicatrices120
Exercices131
Problèmes
132
Partie 2 ¤ Tri et rangs
Chapitre 6 ¤ Tri par tas
139
6.1 Tas140
Exercices141
6.2 Conservation de la propriété de tas142
Exercices144
6.3 Construction d'un tas144
Exercices147
6.4 Algorithme du tri par tas147
Exercices148
6.5 Files de priorités149
Exercices152
Problèmes
153
Chapitre 7 ¤ Tri rapide
157
7.1 Description du tri rapide157
Exercices161
7.2 Performances du tri rapide161
Exercices164
7.3 Une version randomisée du tri rapide165
Exercices166
7.4 Analyse du tri rapide166
Exercices170
Problèmes
171
Chapitre 8 ¤ Tri en temps linéaire
177
8.1 Minorants pour le tri177
Exercices179
8.2 Tri par dénombrement180
Exercices181
8.3 Tri par base182
Exercices184
8.4 Tri par paquets185
Exercices188
Problèmes
189
Chapitre 9 ¤ Médians et rangs
197
9.1 Minimum et maximum198
Exercices199
9.2 Sélection en temps espéré linéaire199
Exercices203
9.3 Sélection en temps linéaire dans le cas le plus défavorable203
Exercices206
Problèmes
207
Partie 3 ¤ Structures de données
Chapitre 10 ¤ Structures de données élémentaires
215
10.1 Piles et files215
Exercices218
10.2 Listes chaînées219
Exercices222
10.3 Implémentation de pointeurs et d'objets223
Exercices227
10.4 Représentation des arbres227
Exercices229
Problèmes
230
Chapitre 11 ¤ Tables de hachage
235
11.1 Tables à adressage direct236
Exercices237
11.2 Tables de hachage238
Exercices242
11.3 Fonctions de hachage243
Exercices249
11.4 Adressage ouvert250
Exercices257
11.5 Hachage parfait258
Exercices262
Problèmes
262
Chapitre 12 ¤ Arbres binaires de recherche
267
12.1 Qu'est-ce qu'un arbre binaire de recherche ?268
Exercices269
12.2 Requête dans un arbre binaire de recherche270
Exercices273
12.3 Insertion et suppression274
Exercices278
12.4 Arbres binaires de recherche construits aléatoirement279
Exercices282
Problèmes
283
Chapitre 13 ¤ Arbres rouge-noir
287
13.1 Propriétés des arbres rouge-noir287
Exercices290
13.2 Rotations291
Exercices292
13.3 Insertion293
Exercices300
13.4 Suppression301
Exercices307
Problèmes
308
Chapitre 14 ¤ Extension des structures de données
315
14.1 Rangs dynamiques316
Exercices320
14.2 Comment étendre une structure de données321
Exercices323
14.3 Arbres d'intervalles324
Exercices328
Problèmes
329
Partie 4 ¤ Techniques avancées de conception et d'analyse
Chapitre 15 ¤ Programmation dynamique
333
15.1 découpe de barres334
Exercices343
15.2 Multiplications matricielles enchaînées343
Exercices350
15.3 Éléments de programmation dynamique351
Exercices361
15.4 Plus longue sous-séquence commune362
Exercices367
15.5 Arbres binaires de recherche optimaux368
Exercices374
Problèmes
375
Chapitre 16 ¤ Algorithmes Gloutons
383
16.1 Un problème de choix d'activités384
Exercices390
16.2 Éléments de la stratégie gloutonne391
Exercices395
16.3 Codages de Huffman396
Exercices403
16.4 Matroïdes et méthodes gloutonnes404
Exercices409
16.5 Un problème d'ordonnancement de tâches en tant que matroïde410
Exercices412
Problèmes
412
Chapitre 17 ¤ Analyse amortie
417
17.1 Analyse de l'agrégat418
Exercices422
17.2 Méthode comptable422
Exercices424
17.3 Méthode du potentiel424
Exercices427
17.4 Tables dynamiques428
Exercices436
Problèmes
437
Partie 5 ¤ Structures de données avancées
Chapitre 18 ¤ B-arbres
447
18.1 Définition d'un B-arbre451
Exercices453
18.2 Opérations fondamentales sur les B-arbres453
Exercices460
18.3 Suppression d'une clé dans un B-arbre461
Exercices464
Problèmes
464
Chapitre 19 ¤ Tas de Fibonacci
467
19.1 Structure des tas de Fibonacci469
19.2 Opérations sur les tas fusionnables471
Exercices479
19.3 Diminution d'une clé et suppression d'un noeud479
Exercices483
19.4 Borne du degré maximal483
Exercices486
Problèmes
486
Chapitre 20 ¤ Arbres de Van Emde Boas
491
20.1 Approches préliminaires492
Exercices495
20.2 Une structure récursive496
Exercices503
20.3 L'arbre de van Emde Boas504
Exercices514
Problèmes
514
Chapitre 21 ¤ Structures de données pour ensembles disjoints
519
21.1 Opérations sur les ensembles disjoints519
Exercices522
21.2 Représentation d'ensembles disjoints par des listes chaînées522
Exercices525
21.3 Forêts d'ensembles disjoints526
Exercices529
21.4 Analyse de l'union par rang avec compression de chemin530
Exercices537
Problèmes
538
Partie 6 ¤ Algorithmes pour les graphes
Chapitre 22 ¤ Algorithmes élémentaires pour les graphes
545
22.1 Représentation des graphes545
Exercices548
22.2 Parcours en largeur549
Exercices556
22.3 Parcours en profondeur557
Exercices564
22.4 Tri topologique566
Exercices568
22.5 Composantes fortement connexes568
Exercices572
Problèmes
573
Chapitre 23 ¤ Arbres couvrants minimaux
577
23.1 Construction d'un arbre couvrant minimal578
Exercices582
23.2 Algorithmes de Kruskal et de Prim583
Exercices588
Problèmes
589
Chapitre 24 ¤ Plus courts chemins à origine unique
595
24.1 Algorithme de Bellman-Ford602
Exercices605
24.2 Plus courts chemins à origine unique dans les graphes orientés sans circuit606
Exercices608
24.3 Algorithme de Dijkstra609
Exercices613
24.4 Contraintes de différence et plus courts chemins614
Exercices618
24.5 Démonstrations des propriétés de plus court chemin620
Exercices625
Problèmes
626
Chapitre 25 ¤ Plus courts chemins entre toutes paires de sommets
631
25.1 Plus courts chemins et multiplication de matrices633
Exercices637
25.2 L'algorithme de Floyd-Warshall639
Exercices645
25.3 Algorithme de Johnson pour les graphes peu denses646
Exercices650
Problèmes
650
Chapitre 26 ¤ Flot maximum
653
26.1 Réseaux de flot654
Exercices657
26.2 La méthode de Ford-Fulkerson658
Exercices672
26.3 Couplage biparti maximum673
Exercices676
26.4 Algorithmes pousser-réétiqueter677
Exercices686
26.5 Algorithme réétiqueter-vers-l'avant688
Exercices698
Problèmes
698
Partie 7 ¤ Morceaux choisis
Chapitre 27 ¤ Algorithmes multithread
709
27.1 Fondements du multithread dynamique711
Exercices726
27.2 Multiplication matricielle multithread727
Exercices731
27.3 Tri par fusion multithread732
Exercices738
Problèmes
739
Chapitre 28 ¤ Calcul matriciel
747
28.1 Résolution de systèmes d'équations linéaires747
Exercices760
28.2 Inversion des matrices760
Exercices764
28.3 Matrices symétriques définies positives et approximation par la méthode des moindres carrés765
Exercices770
Problèmes
771
Chapitre 29 ¤ Programmation linéaire
775
29.1 Forme standard et forme canonique782
Exercices788
29.2 Formulation de problèmes comme programmes linéaires789
Exercices794
29.3 Algorithme du simplexe795
Exercices807
29.4 Dualité808
Exercices814
29.5 La solution réalisable de base initiale814
Exercices820
Problèmes
822
Chapitre 30 ¤ Polynômes et transformée de Fourier rapide
827
30.1 Représentation des polynômes829
Exercices834
30.2 Transformée discrète de Fourier et transformée rapide de Fourier835
Exercices842
30.3 Implémentations efficaces de la transformée rapide de Fourier842
Exercices847
Problèmes
847
Chapitre 31 ¤ Algorithmes de la théorie des nombres
853
31.1 Notions élémentaires de la théorie des nombres854
Exercices858
31.2 Plus grand commun diviseur860
Exercices864
31.3 Arithmétique modulaire865
Exercices870
31.4 Résolution d'équations linéaires modulaires871
Exercices874
31.5 Théorème du reste chinois875
Exercices877
31.6 Puissances d'un élément878
Exercices881
31.7 Le cryptosystème à clés publiques RSA881
Exercices887
31.8 Test de primarité888
Exercices896
31.9 Factorisation des entiers897
Exercices901
Problèmes
902
Chapitre 32 ¤ Recherche de chaînes de caractères
905
32.1 Algorithme naïf de recherche de chaîne de caractères908
Exercices909
32.2 Algorithme de Rabin-Karp910
Exercices914
32.3 Recherche de chaîne de caractères au moyen d'automates finis915
Exercices921
32.4 Algorithme de Knuth-Morris-Pratt921
Exercices929
Problèmes
930
Chapitre 33 ¤ Géométrie algorithmique
933
33.1 Propriétés des segments de droite934
Exercices938
33.2 Déterminer si deux segments donnés se coupent940
Exercices945
33.3 Recherche de l'enveloppe convexe946
Exercices955
33.4 Recherche des deux points les plus rapprochés956
Exercices959
Problèmes
960
Chapitre 34 ¤ NP-complétude
965
34.1 Temps polynomial970
Exercices977
34.2 Vérification en temps polynomial977
Exercices980
34.3 NP-complétude et réductibilité982
Exercices991
34.4 Preuves de NP-complétude992
Exercices998
34.5 Problèmes NP-complets999
Exercices1012
Problèmes
1013
Chapitre 35 ¤ Algorithmes d'approximation
1017
35.1 Problème de la couverture de sommets1019
Exercices1022
35.2 Problème du voyageur de commerce1022
Exercices1027
35.3 Problème de la couverture d'ensemble1027
Exercices1032
35.4 Randomisation et programmation linéaire1032
Exercices1036
35.5 Problème de la somme de sous-ensemble1037
Exercices1042
Problèmes
1042
Annexes ¤ Éléments de mathématiques
Annexe A ¤ Sommes
1051
A.1 Formules et propriétés des sommes1051
Exercices1055
A.2 Bornes des sommes1055
Exercices1061
Problèmes
1061
Annexe B ¤ Ensembles, etc.
1063
B.1 Ensembles1063
Exercices1067
B.2 Relations1067
Exercices1069
B.3 Fonctions1070
Exercices1071
B.4 Graphes1072
Exercices1076
B.5 Arbres1076
Exercices1081
Problèmes
1082
Annexe C ¤ Dénombrement et probabilités
1085
C.1 Dénombrement1085
Exercices1089
C.2 Probabilités1091
Exercices1096
C.3 Variables aléatoires discrètes1097
Exercices1100
C.4 Distributions géométrique et binomiale1102
Exercices1106
C.5 Queues de la distribution binomiale1107
Exercices1113
Problèmes
1114
Annexe D ¤ Matrices
1115
D.1 Matrices et opérations matricielles1115
Exercices1120
D.2 Propriétés fondamentales des matrices1120
Exercices1123
Problèmes
1124
Bibliographie1127
Index1151