Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

collection http://dzdelphi.blogspot.com/ @ Hermbs, Paris, 1992 Éditions Hermès

collection http://dzdelphi.blogspot.com/ @ Hermbs, Paris, 1992 Éditions Hermès 34, rue Eugène Plachat 75017 Paris ISBN 2-86601-323-g 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 ....................................................................................... 45 3.1. Recherche du plus petit élément.. .................................................. 46 13 16 17 17 18 21 21 21 23 24 25 28 29 34 35 36 37 37 38 40 42 43 http://dzdelphi.blogspot.com/ ALGO~Q~IE m PROGRAmION 3.2. Tri par insertion ........................................................................ 48 3.3. Tri par bulles............................................................................ 51 3.4. Diviser pour &gner .................................................................... 54 3.4.1. Diviser pour rkgner avec partition ........................................ 54 3.4.2. Solution sans appel r&rsif.. .............................................. 57 3.4.3. Quelques commentaires sur la nkursivité............................... 59 3.4.4. Deux pivots.. ................................................................... 61 3.4.5. Tri par fusion.. ................................................................. 63 3.5. F&umé de la complexite des algorithmes ....................................... 66 3.6. Exercices.. ................................................................................ 66 Des structures de données.. ........................................................ 67 ’ 4.1. Les piles.. ................................................................................ 67 4.2. Les files................................................................................... 68 4.3. Les arbres.. ............................................................................... 70 4.3.1. Arbres binaires et arbres n-aires ........................................... 71 4.3.2. Représentation des arbres.................................................... 72 4.3.3. Parcours d’arbres............................................................... 73 4.3.4. Parcours préfixé et post-fixé................................................ 74 4.4. Les treillis.. .............................................................................. 78 4.5. Les graphes .............................................................................. 79 4.5.1. Algorithme de Schorr-Waite ................................................ 80 4.5.2. Amélioration de l’algorithme de Schorr-Waite......................... 84 4.5.3. Représentation d’un graphe sur une matrice booléenne.............. 87 4.5.4. Fermeture transitive .......................................................... 88 4.6. Ordres partiels et totaux .............................................................. 89 4.7. Exercices.. ................................................................................ 90 5. Récurrence et récursivité ........................................................... 93 5.1. L’exemple type . Les tours d’Hanoi ............................................... 93 5.1.1. Coût de l’algorithme .......................................................... 96 5.1.2. Une analyse plus poussée.. ................................................. 97 5.2. Des permutations....................................................................... 99 5.2.1. Permutations par échanges de voisins ................................... 100 5.2.2. Le programme.................................................................. 101 5.2.3. Relation avec les tours d’Hanoi ............................................ 105 5.2.4. Une variante .................................................................... 105 5.2.5. Une version récursive ........................................................ 108 5.3. Exercices .................................................................................. 109 6. La marche arrière ........................................................................ 111 6.1. La souris et le fromage ............................................................... 111 6.1.1. Version t+cursive .............................................................. 114 6 7. 8 . 6.1.2. Marche arriere, arbres et graphes .......................................... 115 6.2. Les huits reines......................................................................... 116 6.2.1. Une version améliorée ....................................................... 118 6.2.2. Une deuxieme approche ...................................................... 119 6.3. Exercices .................................................................................. 122 ‘lkansformation de programmes.. ................................................ 125 7.1. Revenons sur le mode vecteur ...................................................... 126 7.2. La multiplication des gitans ......................................................... 128 7.3. Exercices.................................................................................. 131 Quelques structures de données particulières.. .......................... 133 8.1. Les arbres ordonnés.................................................................... 133 8.2. Les arbres équilibrés ................................................................... 135 8.2.1. Algorithmes de manipulation d’arbres équilibrés...................... 137 8.3. Les B-arbres.............................................................................. 138 8.4. Exercices.................................................................................. 143 I 7 Bibliographie e t références.. ........................................................... 145 Glossaire ......................................................................................... 148 Solutions de certains exercices.. .................................................... 151 http://dzdelphi.blogspot.com/ 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) http://dzdelphi.blogspot.com/ A L G O R I T H M I Q U E 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) 1 0 http://dzdelphi.blogspot.com/ ALGORITHMIQIJE ET ~m~bmmf.mo~ 4.8. Visite d’un graphe ($4.5) 4.9. Marquage avec trois valeurs (94.51) 4.10. Version sans récursivité ($4.51) 4.11. Mise en œuvre du prédécesseur (§4.5.1) 4.12. Schorr-Waite améliore ($4.5.2) 4.13. Version condensée ($4.5.2) 5.1. Tours d’Hanoi, version de base ($5.1) 5.2. Calcul du pivot (§5.2.2) 5.3. Permutations par échanges (95.2.2) 5.4. Permutations par échanges, version 2 (55.2.2) 5.5. Encore les tours d’Hanoi ($5.2.3) 5.6. Traversée unidirectionnelle ($5.2.4) 5.7. Version rkursive (45.2.5) 6.1. La souris et le fromage ($6.1) 6.2. Forme récursive (96.1.1) 6.3. Les huit reines ($6.2) 6.4. Les huit reines, version 2 ($6.2) ~6.5. Suppression d’une pile ($6.2.1) 6.6. Avec un compteur octal ($6.2.2) 6.7. Avec des permutations ($6.2.2) 6.8. Avec permutations et marche arrière ($6.2.2) 7.1. Encore le mode d’un vecteur (97.1) 7.2. Le mode amélioré ($7.1) 7.3. Multiplication avec n%.trsivité ($7.2) 7.4. Suppression de la récursivité ($7.2) 7.5. Version avec décalages ($7.2) 8.1. Arbre ordonné ($8.1) 8.2. Arbre Cquilibré (48.2.1) 8.3. B-arbres ($8.3) 12 Chapitre 1 Introduction Depuis de nombreuses années, dans différents pays, les informaticiens ayant quelques prétentions académiques ont lutté pour établir leur discipline de manière indépendante. Sans vouloir dire que la lutte est terminée (certains n’ayant pas encore accepté que la terre n’est pas plate), on peut constater que, dans les universités respectées, il existe des laboratoires d’informatique independants, des diplômes spkialisés, et *les enseignants et/ou chercheurs en informatique sont désormais considér& comme des scientifiques a part entière. Pourquoi cette lutte ? Et pourquoi en parler dans un livre sur l’algorithmique ? Le fait est que les informaticiens ont représenté - et représentent toujours - un enjeu économique. Comme cet enjeu a été concrétisé par des moyens matériels et financiers mis a la disposition des enseignants et des chercheurs en informatique, tout un chacun a éprouvé le besoin de réclamer l’etiquette. Le tri entre les “vrais” et “faux” informaticiens n’est pas terminé. D’ailleurs, à notre avis il ne le sera jamais, et c’est peut-être heureux ainsi. Malheureusement, en voulant affirmer leur indépendance par rapport aux autres disciplines, les informaticiens ont perdu une partie de l’essentiel. En se concentrant sur les techniques non-numériques (importantes et indispensables), ils ont perdu jusqu’à la notion de l’existence des nombret réels. De même, un peu en singeant les mathématiciens, qui ont montré la voie vers la tour d’ivoire, le besoin scientifique mais aussi psychologique de la construction dune (ou de plusieurs) théorie(s) a fait perdre la vraie justification de notre existence : l’écriture de programmes qui sont utiles. On est donc en présence de plusieurs guerres, numérique contre non- numerique, théorie contre application, utilisateurs contre spécialistes, vendeurs de vent contre professionnels sérieux. Si certaines guerres peuvent être utiles et salutaires, d’autres resteront toujours stériles. http://dzdelphi.blogspot.com/ Ce livre ne saurait bien sûr en corriger les écarts. Mais nous voulons témoigner de notre foi dans l’existence de l’informatique en tant que discipline indépendante, mais surtout utile. L’informaticien comme le mathématicien - même si ce dernier l’a peut-être oublié - est un esclave des autres. Sa raison d’être est de rendre service, c’est-à-dire résoudre des problbmes d’application. Il n’y a pas d’informatique académique différente de celle de l’application numérique ou de gestion. uploads/Litterature/ algorithmique-et-programmation.pdf