Algorithmique

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. Dela 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. Adressagedispersé……………………………………………………………. 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é……………………………………………