Introduction aux Algorithmes et Structures
Transféré par
ScribdTranslationsIntroduction aux Algorithmes et Structures
Transféré par
ScribdTranslationsAlgorithmes
Richard Johnsonbaugh
Marcus Schaefer
UNIVERSITÉ DEPAUL
PEARSON
Prentice Hall
Éducation Pearson
Rivière Upper Saddle, New Jersey 07458
Contenu
Préface ix
1 Présentation 1
1.1 Algorithmes 1
1.2 Pseudo-code pour les algorithmes 4
1.3 Le présent 10
1.4 Le futur 12
Notes 14
Exercices du chapitre 14
2 Mathématiques pour les algorithmes 17
2.1 Définitions, notation et résultats de base 17
2.2 Induction mathématique 32
2.3 Analyse des algorithmes 41
2.4 Relations de récurrence 5 5
2.5 Graphiques 68
2.6 Arbres 86
Notes 94
Exercices du chapitre 94
3 Structures de données 99
3.1 Types de données abstraites 99
3.2 Piles et files d'attente 101
3.3 Listes chaînées 111
3.4 Arbres binaires 120
3.5 Files d'attente prioritaires, tas binaires et tri par tas 133
3.6 Ensembles disjoints 150
Notes 162
Exercices du chapitre 162
VI Contenu
4 Recherche 165
4.1 Recherche binaire 165
4.2 Recherche en profondeur 172
4.3 Recherche en largeur 181
4.4 Tri topologique 188
4.5 Retour en arrière 195
Notes 209
Exercices du chapitre 209
5 Diviser pour mieux régner 213
5.1 Problème ATiling 213
5.2 Tri par fusion 219
5.3 Trouver la paire de points la plus proche 225
5.4 Algorithme du produit matriciel de Strassen 232
Notes 236
Exercices du chapitre 236
6 Tri et sélection 239
6.1 Tri par insertion 239
6.2 Tri rapide 243
6.3 Une limite inférieure pour le problème de tri 254
6.4 Tri par comptage et tri par base 257
6.5 Sélection 262
Notes 268
Exercices du chapitre 268
7 algorithmes gourmands 271
7.1 Change de pièces 271
7.2 Algorithme de Kruskal 275
7.3 Algorithme de Prim 284
7.4 Algorithme de Dijkstra 295
7.5 Codes Huffman 302
7.6 Le problème du sac à dos continu 313
Notes 319
Exercices du chapitre 319
Contenu vii
8 Programmation dynamique 323
8.1 Calcul des nombres de Fibonacci 323
8.2 Le changement de monnaie revisité 328
8.3 Multiplication de matrices 336
8.4 Problème de la plus longue sous-séquence commune 342
8.5 Les algorithmes de Floyd et Warshall 350
Notes 361
Exercices du chapitre 361
9 Recherche de texte 367
9.1 Recherche de texte simple 368
9.2 L'algorithme de Rabin-Karp 371
9.3 L'algorithme Knuth-Morris-Pratt 379
9.4 L'algorithme de Boyer-Moore-Horspool 392
9.5 Correspondance approximative des motifs 398
9.6 Correspondance d'expression régulière 408
Notes 422
Exercices du chapitre 423
10 P et NP 429
10.1 Temps polynomial 429
10.2 Algorithmes non déterministes et NP 437
10.3 Réductibilité et NP-Complétude 452
10.4 Problèmes NP-Complet 466
10.5 En savoir plus sur NP-Completeness 474
Notes 481
Exercices du chapitre 482
11 Faire face à la complétude du NP 493
11.1 Force brute 495
11.2 Aléatoire 504
11.3 Approximation 511
11.4 Paramétrage 526
11.5 Heuristique 541
Notes 551
Exercices du chapitre 552
viii Contenu
12 Algorithmes parallèles et distribués 559
12.1 Présentation 559
12.2 La machine à accès aléatoire parallèle (PRAM) 563
12.3 Réseaux de tri 587
12.4 Architectures parallèles 604
12.5 Algorithmes distribués 626
Notes 639
Exercices du chapitre 640
Références 645
Solutions aux exercices sélectionnés 651
Index 735
