Micro Systèmes n°49 janvier 1985
Micro Systèmes n°49 janvier 1985
  • Prix facial : 24 F

  • Parution : n°49 de janvier 1985

  • Périodicité : mensuel

  • Editeur : Société Parisienne d'Edition

  • Format : (203 x 271) mm

  • Nombre de pages : 198

  • Taille du fichier PDF : 137 Mo

  • Dans ce numéro : dossier sur l'ordinateur biologique.

  • Prix de vente (PDF) : gratuit

Dans ce numéro...
< Pages précédentes
Pages : 128 - 129  |  Aller à la page   OK
Pages suivantes >
128 129
DES PARCOURS D L'arborescence est l'une des structures de données les plus employées en informatique. Ensemble d'éléments hiérarchisés, les arborescences (on dit aussi arbres) poussent vers le bas  : la racine se trouve au sommet, et les feuilles (les éléments terminaux) sont les plus basses de l'arbre. Ces structures permettent de représenter un grand nombre de situations ou de phénomènes  : décomposition d'un programme en sous-programmes, arbre d'évaluation d'un jeu de stratégie (échecs ou dames), syntaxe d'une expression arithmétique ou d'un langage de programmation. Mais l'utilisation des arborescences ne se limite pas à l'analyse des cas purement informatiques. Nombre d'informations ont une nature arborescente. En particulier, classer des éléments (animaux, plantes, activités humaines, etc.) revient souvent à décrire une structure arborescente où les concepts les plus généraux se trouvent au sommet de l'arbre et les plus particuliers à ses feuilles (fig. A). Plusieurs techniques peuvent être utilisées pour représenter, en Lisp, des structures arborescentes. L'une des plus simples à mettre en oeuvre consiste à décrire chaque noeud de l'arbre à l'aide d'une liste. L'information associée au noeud est placée dans le premier élément (le CAR de la liste), tandis que les éléments suivants de la liste décrivent les fils du noeud. La figure B montre la représentation interne d'une arborescence portant sur une classification de type « sciences naturelles ». La traduction d'une telle structure se fait aisément dans le langage  : il suffit de décrire la suite des éléments en utilisant les parenthèses pour délimiter les différents niveaux de la hiérarchie (fig. C). Une importante caractéristique des arbres est qu'ils puissent être « parcourus »  : il est possible de se déplacer le long de l'arborescence dans un certain ordre et de traiter les valeurs des noeuds au fur et à mesure de ce parcours. Les deux stratégies fondamentales de parcours reviennent à traiter les noeuds de l'arborescence en se déplaçant en profondeur ou en largeur. Dans la première, le programme ne cesse de monter et descendre dans l'arbre. A chaque niveau, un seul noeud est analysé. S'il possède des fils, la recherche se poursuit en examinant le premier de ses fils. La descente s'arrête lorsqu'on atteint une feuille de l'arbre. Dans ce cas, le système remonte d'un cran et analyse les fils suivants (fig. D-a). Cette démarche donne lieu à trois types de parcours qui se dénomment « préordre » (traiter un noeud d'abord et ses fils ensuite), « inordre » (traiter le fil gauche, un noeud puis les autres fils) et « postordre » (traiter les fils d'abord puis le noeud ensuite). Dans la seconde stratégie, l'arborescence est parcourue en largeur d'abord  : tous les noeuds situés à un niveau sont examinés avant de poursuivre la recherche au niveau suivant (fig. D-b). Par exemple, en étudiant successivement une arborescence d'expression arithmétique comme celle de la figure E, à l'aide des différents parcours, les noeuds sont traités dans l'ordre suivant  : En profondeur d'abord  : 4 Fig. A. - Classer des concepts selon une approche hiérarchique peut se représenter sous la forme d'une arborescence. A Plante A\Armnal A Naturel Arbre Fleur Insecte Reptile Mammifère Nuage Floche NN. 71 Pin Chêne Chien Si ge Erre humain Artlhoel VuOure Maison 4 Fig. B. - La représentation physique d'une arborescence en Lisp utilise un grand nombre de cellules de base. Fig.C. - Définir un arbre ne pose pas de problèmes en Lisp  : il suffit de faire attention au nombre des parenthèses.> Fig. F. - Toutes les fonctions de parcours d'un arbre. Il suffit de passer une fonction en argument pour traiter tous les noeuds de l'arborescence durant l'exploration.> Arbre MC nC 111C no Chose MC MC ta Etre vivant MC MC na Inanimé IIC ru no Plante Animal Naturel Artificiel MC MC na na 1 101 11111 NC ra V Arbre Fleur Insecte Reptile Mammifère Nuage Roche ra 10 la Jo Pin Chêne Chien Singe Etre humain loi 10 Ma I1C1 Voiture Maison Ordinateur 128 — MICRO-SYSTEMES Janvier 1985
ANS LES ARBRES Préordre  : + * 4 3 * 5 2 Inordre  : 4 * 3 + 5 * 2 Postordre  : 4 3 * 5 2 * + Largeur  : + * * 4 3 5 2 La figure F donne le listing de toutes les fonctions nécessaires à la réalisation de ces parcours. Le traitement effectué à chaque noeud est réalisé par une fonction passée en argument FN. Par exemple, si l'on désire imprimer les différentes valeurs des noeuds de l'arbre, il suffit de passer la fonction PRINT en argument. ? (setq a'(* (+ (12) (4)) (+ (5) (2)))) = (* (+ (12) (4)) (+ (5) (2))) ? (prof-preordre'print a) * 12 4 5 2 = () On peut aussi passer une lambda expression comme fonction de traitement. Par exemple, si l'on désire imprimer et incrémenter d'une unité toutes les valeurs numériques : ? (largeur (lambda (x) (if (numberp x) (print (addl x)) (print x))) a) * 13 5 6 3 = () Les fonctions qui parcourent l'arborescence en profondeur d'abord sont plus simples à écrire. En effet, dans ce cas, il suffit d'une pile qui va mémoriser le passage employé lors de la descente d'un niveau à un autre, de manière à pouvoir revenir au niveau précédent chaque fois que le besoin s'en fait sentir. La définition récursive de ces fonctions utilise la pile de l'interpréteur Lisp, ce qui simplifie grandement leur définition. En revanche, les parcours en largeur d'abord doivent être gérés explicitement au moyen d'une file d'attente (ou queue). Ces fonctions ont alors une structure itérative. (setq arbre'(chose (etre-vivant (plante (arbre (pin) (chene)) (fleur)) (animal (insecte) (reptile) (aammifere (chien) (singe) (etre -husain)))) (inanise (naturel (nuage)(roche)) (artificiel (voiture)(ma son)(ordinateur))))) (de prof-preordre (fn arb) (apply fn (car arb)) (mapcar (lambda (x) (prof-preordre fn x)) (cdr arb)) ()) (de prof-postordre (fn arb) (mapcar (lambda (a) (prof-poetordre fn x)) (cdr arb)) (apply fn (car arb)) O) (de prof-inordre (fn arb) (prof-inordre fn (cadr arb)) (apply fn (car arb)) (mapcar (lambda (x) (prof-inordre fn x)) (cddr arb)) ()) (de largeur (fn arb) (let ((queue (liet arb))) (while queue (setq queue (append queue (cdar queue))) (apply fn (cons (caar queue))) (next1 queue)))) jed„oe° 14%.%4/*\*A. 4 3 5 2 Fig. D. - Parcourir un arbre peut s'effectuer en profondeur d'abord (a), l'exploitation consistant à monter et descendre en suivant les branches de l'arbre, ou en largeur d'abord (b), où un niveau de l'arbre est complètement examiné avant de passer au suivant. 4 Fig. E. - Les arborescences servent à représenter des expressions arithmétiques. Janvier 1985 MICRO-SYSTEMES — 129



Autres parutions de ce magazine  voir tous les numéros


Liens vers cette page
Couverture seule :


Couverture avec texte parution au-dessus :


Couverture avec texte parution en dessous :


Micro Systèmes numéro 49 janvier 1985 Page 1Micro Systèmes numéro 49 janvier 1985 Page 2-3Micro Systèmes numéro 49 janvier 1985 Page 4-5Micro Systèmes numéro 49 janvier 1985 Page 6-7Micro Systèmes numéro 49 janvier 1985 Page 8-9Micro Systèmes numéro 49 janvier 1985 Page 10-11Micro Systèmes numéro 49 janvier 1985 Page 12-13Micro Systèmes numéro 49 janvier 1985 Page 14-15Micro Systèmes numéro 49 janvier 1985 Page 16-17Micro Systèmes numéro 49 janvier 1985 Page 18-19Micro Systèmes numéro 49 janvier 1985 Page 20-21Micro Systèmes numéro 49 janvier 1985 Page 22-23Micro Systèmes numéro 49 janvier 1985 Page 24-25Micro Systèmes numéro 49 janvier 1985 Page 26-27Micro Systèmes numéro 49 janvier 1985 Page 28-29Micro Systèmes numéro 49 janvier 1985 Page 30-31Micro Systèmes numéro 49 janvier 1985 Page 32-33Micro Systèmes numéro 49 janvier 1985 Page 34-35Micro Systèmes numéro 49 janvier 1985 Page 36-37Micro Systèmes numéro 49 janvier 1985 Page 38-39Micro Systèmes numéro 49 janvier 1985 Page 40-41Micro Systèmes numéro 49 janvier 1985 Page 42-43Micro Systèmes numéro 49 janvier 1985 Page 44-45Micro Systèmes numéro 49 janvier 1985 Page 46-47Micro Systèmes numéro 49 janvier 1985 Page 48-49Micro Systèmes numéro 49 janvier 1985 Page 50-51Micro Systèmes numéro 49 janvier 1985 Page 52-53Micro Systèmes numéro 49 janvier 1985 Page 54-55Micro Systèmes numéro 49 janvier 1985 Page 56-57Micro Systèmes numéro 49 janvier 1985 Page 58-59Micro Systèmes numéro 49 janvier 1985 Page 60-61Micro Systèmes numéro 49 janvier 1985 Page 62-63Micro Systèmes numéro 49 janvier 1985 Page 64-65Micro Systèmes numéro 49 janvier 1985 Page 66-67Micro Systèmes numéro 49 janvier 1985 Page 68-69Micro Systèmes numéro 49 janvier 1985 Page 70-71Micro Systèmes numéro 49 janvier 1985 Page 72-73Micro Systèmes numéro 49 janvier 1985 Page 74-75Micro Systèmes numéro 49 janvier 1985 Page 76-77Micro Systèmes numéro 49 janvier 1985 Page 78-79Micro Systèmes numéro 49 janvier 1985 Page 80-81Micro Systèmes numéro 49 janvier 1985 Page 82-83Micro Systèmes numéro 49 janvier 1985 Page 84-85Micro Systèmes numéro 49 janvier 1985 Page 86-87Micro Systèmes numéro 49 janvier 1985 Page 88-89Micro Systèmes numéro 49 janvier 1985 Page 90-91Micro Systèmes numéro 49 janvier 1985 Page 92-93Micro Systèmes numéro 49 janvier 1985 Page 94-95Micro Systèmes numéro 49 janvier 1985 Page 96-97Micro Systèmes numéro 49 janvier 1985 Page 98-99Micro Systèmes numéro 49 janvier 1985 Page 100-101Micro Systèmes numéro 49 janvier 1985 Page 102-103Micro Systèmes numéro 49 janvier 1985 Page 104-105Micro Systèmes numéro 49 janvier 1985 Page 106-107Micro Systèmes numéro 49 janvier 1985 Page 108-109Micro Systèmes numéro 49 janvier 1985 Page 110-111Micro Systèmes numéro 49 janvier 1985 Page 112-113Micro Systèmes numéro 49 janvier 1985 Page 114-115Micro Systèmes numéro 49 janvier 1985 Page 116-117Micro Systèmes numéro 49 janvier 1985 Page 118-119Micro Systèmes numéro 49 janvier 1985 Page 120-121Micro Systèmes numéro 49 janvier 1985 Page 122-123Micro Systèmes numéro 49 janvier 1985 Page 124-125Micro Systèmes numéro 49 janvier 1985 Page 126-127Micro Systèmes numéro 49 janvier 1985 Page 128-129Micro Systèmes numéro 49 janvier 1985 Page 130-131Micro Systèmes numéro 49 janvier 1985 Page 132-133Micro Systèmes numéro 49 janvier 1985 Page 134-135Micro Systèmes numéro 49 janvier 1985 Page 136-137Micro Systèmes numéro 49 janvier 1985 Page 138-139Micro Systèmes numéro 49 janvier 1985 Page 140-141Micro Systèmes numéro 49 janvier 1985 Page 142-143Micro Systèmes numéro 49 janvier 1985 Page 144-145Micro Systèmes numéro 49 janvier 1985 Page 146-147Micro Systèmes numéro 49 janvier 1985 Page 148-149Micro Systèmes numéro 49 janvier 1985 Page 150-151Micro Systèmes numéro 49 janvier 1985 Page 152-153Micro Systèmes numéro 49 janvier 1985 Page 154-155Micro Systèmes numéro 49 janvier 1985 Page 156-157Micro Systèmes numéro 49 janvier 1985 Page 158-159Micro Systèmes numéro 49 janvier 1985 Page 160-161Micro Systèmes numéro 49 janvier 1985 Page 162-163Micro Systèmes numéro 49 janvier 1985 Page 164-165Micro Systèmes numéro 49 janvier 1985 Page 166-167Micro Systèmes numéro 49 janvier 1985 Page 168-169Micro Systèmes numéro 49 janvier 1985 Page 170-171Micro Systèmes numéro 49 janvier 1985 Page 172-173Micro Systèmes numéro 49 janvier 1985 Page 174-175Micro Systèmes numéro 49 janvier 1985 Page 176-177Micro Systèmes numéro 49 janvier 1985 Page 178-179Micro Systèmes numéro 49 janvier 1985 Page 180-181Micro Systèmes numéro 49 janvier 1985 Page 182-183Micro Systèmes numéro 49 janvier 1985 Page 184-185Micro Systèmes numéro 49 janvier 1985 Page 186-187Micro Systèmes numéro 49 janvier 1985 Page 188-189Micro Systèmes numéro 49 janvier 1985 Page 190-191Micro Systèmes numéro 49 janvier 1985 Page 192-193Micro Systèmes numéro 49 janvier 1985 Page 194-195Micro Systèmes numéro 49 janvier 1985 Page 196-197Micro Systèmes numéro 49 janvier 1985 Page 198