Algorithmique et Programmation Michael Griffith.pdf

(2076 KB) Pobierz
collection Informat
Table des matières
1 . Introduction.. ..............................................................................
1 .l. Quelques mots sur l’environnement ...............................................
1.2. Notes
bibliographiques sommaires.. ..............................................
1.3. Remerciements.. ........................................................................
1.4. Le choix de programmes .............................................................
2 . Des programmes pour commencer.. ...........................................
2.1. Le mode d’un vecteur ..................................................................
2.1.1. Construction de la première version du programme ..................
2.1.2. Remarques méthodologiques ...............................................
2.2. Recherche d’un objet.. ................................................................
2.2.1. Recherche linéaire.. ...........................................................
2.2.2. Un piège.. .......................................................................
2.2.3. La dichotomie.. ................................................................
2.3. De la complexité des algorithmes.. ................................................
2.4. Résumé des principes introduits.. ..................................................
2.4.1. Un apparte sur les preuves de programmes.. ...........................
2.4.2. Le style d’écriture .............................................................
2.5.
Adressage dispersé......................................................................
2.5.1. Algorithme avec chaînage.. .................................................
2.5.2. Autant de cl& que de cases.. ................................................
2.5.3. Choix de clé et efficacité ....................................................
2.6. Exercices ..................................................................................
3.
Les tris .......................................................................................
3.1. Recherche du plus petit élément.. ..................................................
13
16
17
17
18
21
21
21
23
24
25
28
29
34
35
36
37
37
38
40
42
43
45
46
@ Hermbs, Paris, 1992
Éditions Hermès
34, rue Eugène Plachat
75017 Paris
ISBN
2-86601-323-g
ALGO~Q~IE
m PROGRAmION
3.2. Tri par insertion ........................................................................
3.3. Tri par bulles.. ..........................................................................
3.4. Diviser pour
&gner
....................................................................
3.4.1. Diviser pour rkgner avec partition ........................................
3.4.2. Solution sans appel r&rsif.. ..............................................
3.4.3. Quelques commentaires sur la nkursivité ...............................
3.4.4. Deux pivots.. ...................................................................
3.4.5. Tri par fusion.. .................................................................
3.5. F&umé de la complexite des algorithmes .......................................
3.6. Exercices.. ................................................................................
Des
4.1.
4.2.
4.3.
structures de données.. ........................................................
Les piles.. ................................................................................
Les files ...................................................................................
Les arbres.. ...............................................................................
4.3.1. Arbres binaires et arbres n-aires ...........................................
4.3.2. Représentation des arbres ....................................................
4.3.3. Parcours d’arbres ...............................................................
4.3.4. Parcours préfixé et post-fixé................................................
Les treillis.. ..............................................................................
Les graphes ..............................................................................
4.5.1. Algorithme de Schorr-Waite ................................................
4.5.2. Amélioration de l’algorithme de Schorr-Waite.. .......................
4.5.3. Représentation d’un graphe sur une matrice booléenne.. ............
4.5.4. Fermeture transitive ..........................................................
Ordres partiels et totaux ..............................................................
Exercices.. ................................................................................
48
51
54
54
57
59
61
63
66
66
67 ’
67
68
70
71
72
73
74
78
79
80
84
87
88
89
90
93
93
96
97
99
100
101
105
105
108
109
111
111
114
6.1.2. Marche arriere, arbres et graphes ..........................................
6.2. Les huits reines .........................................................................
6.2.1. Une version améliorée .......................................................
6.2.2. Une deuxieme approche ......................................................
6.3. Exercices ..................................................................................
7.
‘lkansformation de programmes.. ................................................
7.1. Revenons sur le mode vecteur ......................................................
7.2. La multiplication des gitans .........................................................
7.3. Exercices ..................................................................................
8 .
Quelques structures de données particulières.. ..........................
8.1. Les arbres ordonnés.. ..................................................................
8.2. Les arbres équilibrés ...................................................................
8.2.1. Algorithmes de manipulation d’arbres équilibrés.. ....................
8.3. Les B-arbres.. ............................................................................
8.4. Exercices ..................................................................................
Bibliographie e t références.. ...........................................................
Glossaire .........................................................................................
Solutions
de certains
exercices.. ....................................................
115
116
118
119
122
125
126
128
131
133
133
135
137
138
143
145
148
151
4.4.
4.5.
4.6.
4.7.
5. Récurrence et récursivité ...........................................................
5.1. L’exemple type . Les tours d’Hanoi ...............................................
5.1.1. Coût de l’algorithme ..........................................................
5.1.2. Une analyse plus poussée.. .................................................
5.2. Des permutations.......................................................................
5.2.1. Permutations par échanges de voisins ...................................
5.2.2. Le programme ..................................................................
5.2.3. Relation avec les tours d’Hanoi ............................................
5.2.4. Une variante ....................................................................
5.2.5. Une version récursive ........................................................
5.3. Exercices ..................................................................................
6. La marche arrière ........................................................................
6.1. La souris et le fromage ...............................................................
6.1.1. Version t+cursive ..............................................................
6
I
7
Tables et figures
2.1. Comparaison entre la recherche I&%re et la dichotomie (02.3)
2.2. Table pour l’adressage dispersé avec chaînage ($25.1)
2.3. Table sans zone de débordement ($2.52)
3.1. Appels après parution (83.4.3)
3.2. Vecteur en cours de partition (93.4.4)
4.1. Arbre du tri diviser pour régner (94.3)
4.2. Transformation d’arbre n-aire en arbre binaire (§4.3.1)
4.3. Représentation de l’arbre de la figure 4.2 ($4.3.2)
4.4. Parcours en profondeur d’abord (ordre prefixé) ($4.3.4)
4.5. Parcours en largeur d’abord ($4.3.4)
4.6. Triple visite des nœuds d’un arbre ($4.3.4)
4.7. Parcours en ordre infixé ($4.3.4)
4.8. Parcours en ordre post-fixé ($4.3.4)
4.9. Un treillis (94.4)
4.10. Etats dans Schorr-Waite ($4.52)
4.11. Etats dans Schorr-Waite amélioré ($4.5.2)
4.12. Un graphe ($4.5.3)
4.13. Représentation sur une matrice binaire ($4.5.3)
4.14. Fermeture transitive du graphe de la figure 4.13 ($4.5.4)
4.15. Fermeture transitive, une ligne (94.5.4)
4.16. Arbre binaire simple ($4.6)
5.1. Position de départ des tours d’Hanoi ($5.1)
5.2. Arbre d’appels pour trois disques (§5.1)
5.3. Permutations de quatre entiers ($5.2.1)
5.4. Valeurs de i et du pivot dans permutations(4) ($5.2.2)
5.5. Nouvelles permutations de quatre objets ($5.2.4)
ALGORITHMIQUE
JZ P R O G R A M M A T I O N
6.1. Arbre de possibilites pour la souris ($6.1.2)
7.1. Multiplication de deux entiers ($7.2)
8.1. Un arbre binaire ordonne ($8.1)
8.2. Arbre ordonné inefficace ($8.2)
8.3. Equilibrage de l’arbre de la figure 8.1 ($8.2)
8.4. Avec deux nœuds en plus ($8.2)
8.5. Rééquilibrage de l’arbre de la figure 8.4 ($8.2)
8.6. Un B-arbre complet avec d=l ($8.3)
8.7. Apres lecture de 1 et 2 ($8.3)
8.8. Apres lecture du 3 ($8.3)
8.9. Apres lecture du 5 ($8.3)
8.10. Apres lecture du 7 ($8.3)
8.11. Reorganisation pour éviter d’introduire un niveau ($8.3)
Les programmes
2.1. Le mode d’un vecteur ($2.1.1)
2.2. Recherche d’un objet dans un vecteur ($2.2.1)
2.3. Recherche par dichotomie (82.2.3)
2.4. Dichotomie, version 2 ($2.2.3)
2.5. Dichotomie, version 3 ($2.2.3)
2.6. Adressage dispersé ($2.5.1)
2.7. Adressage dispersé, version 2 ($2.5.2)
3.1. Schéma du tri par recherche du plus petit élement (93.1)
3.2. Boucle interne (83.1)
3.3. Programme complet ($3.1)
3.4. Tri par insertion ($3.2)
3.5. Version avec ETPUIS ($3.2)
3.6. Tri par bulles primitif ($3.3)
3.7. Tri par bulles normal ($3.3)
3.8. Partition d’un vecteur ($3.4.1)
3.9. Insertion dans une proc&lure nkursive (93.4.1)
3.10. Version avec pile ($3.4.2)
3.11. Diviser pour régner avec deux pivots ($3.4.4)
3.12. Tri par fusion ($3.4.5)
4.1. Miseen œuvre d’unepile ($4.1)
(y’ 4.2. Une file discutable ($4.2)
g 4.3. Une file circulaire (84.2)
4.4. Parcours d’un arbre binaire ($4.3.3)
4.5. Utilisation d’une butée ($4.3.3)
J- 4.6. Parcours avec pife ($4.3.3)
4.7. Triple visite d’un nœud (44.3.4)
10

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin