Algorithmique : cours avec 957 exercices et 158 problèmes

Résumé

Une introduction complète à l'algorithmique, du tri aux algorithmes parallèles. Des notions élémentaires aux thèmes plus pointus, étudiants et professionnels trouveront dans les exercices proposés, dans un code proche des langages Pascal, C et Fortan, des outils de compréhension simples.

Éditeur(s)
- Dunod
Date
- 2010
Langues
- Français
Description matérielle
- 1186 p. ; 24 x 19 cm
Collections
- Sciences sup
Sujet(s)
- Algorithmes
ISBN
- 978-2-10-054526-1
Indice
- 681.21(07) Algorithmes de programmation. Manuels
Quatrième de couverture
- Sciences sup
  Algorithmique
  Cet ouvrage s'est imposé comme une référence mondiale pour l'enseignement de l'algorithmique. Exhaustif et facile d'accès, c'est un outil de travail complet et indispensable pour les étudiants. Cette 3^e édition est entièrement révisée et mise à jour, avec deux nouveaux chapitres.
  L'éventail des algorithmes étudiés va des plus classiques, comme les algorithmes de tri et les fonctions de hachage, aux plus récents, comme ceux de la cryptographie, permettant ainsi de passer progressivement des notions élémentaires aux thèmes les plus pointus.
  Les algorithmes sont rédigés en français et dans un pseudo-code proche des langages Pascal, C et Java. Ils sont analysés en profondeur et complétés par des preuves mathématiques. De nombreux exemples, figures, études de cas et exercices de difficulté graduée complètent les explications. Au total, ce sont les énoncés de 957 exercices et 158 problèmes qui sont proposés, dont certains sont nouveaux dans cette 3^e édition. Les solutions de 80 d'entre eux sont accessibles en ligne sur le site www.dunod.com
  Le contenu : Bases mathématiques ¤ Tris et rangs ¤ Structures de données ¤ Tables de hachage ¤ Arbres ¤ Programmation dynamique ¤ Algorithmes gloutons ¤ Analyse amortie ¤ B-arbres ¤ Tas de Fibonacci ¤ Structures de données pour ensembles disjoints ¤ Algorithmes pour les graphes ¤ Plus courts chemins ¤ Flot maximum ¤ Algorithmes multithread ¤ Calcul matriciel ¤ Programmation linéaire ¤ Transformation de Fourier rapide ¤ Algorithmes de la théorie des nombres ¤ Géométrie algorithmique ¤ NP-complétude ¤ Algorithmes d'approximation.
Tables des matières
- - 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
Origine de la notice:
- Electre