G. HUNAULT  Angers, 1998

Mini-Projet en Algorithmique et Programmation :

Adressages de segments d’arbres topologiques

(Licence MASS)

1. Position du problème

Un arbre réel se compose d’un tronc et de branches. L’équivalent topologique se compose d’un axe principal (”tronc”) et d’axes nommés secondaires ou latéraux (”branches”) obtenus par ramification binaire. Chaque axe est découpé en segments nommés, comme en botanique, entrenoeuds. Le terme topologique signifie que les longueurs des entrenoeuds et les angles de ramification sont arbitraires. Si une représentation graphique comme celle de la figure 1 est possible et utile, les longueurs et les angles en sont totalement arbitraires.

[figure]

Figure 1 : Deux représentations d’un même arbre topologique Pour décrire des arbres topologiques, on associe une adresse à chaque segment. De nombreux adressages (ou ”systèmes d’adresses”) sont possibles. Nous retiendrons les 3 suivants pour le mini-projet : l’adressage AF, l’adressage LEX et l’adressage BM. L’adressage AF consiste à définir le chemin qui va de la racine au segment considéré. A signifie ”axe” et F ”feuille” car chaque segment est susceptible de supporter une feuile. Notant A1F1 le premier segment, chaque segment a une adresse unique. L’adressage LEX utilise les symboles 1 et 2 pour définir les adresses. 1 indique un segment, 2 indique qu’on change d’axe. L’adressage BM vient, quant à lui, utiliser les numéros de l’arbre binaire maximal sous-jacent où le segment i se prolonge en les segments 2i et 2i + 1. Nous montrons sur la figure 2 un même arbre topologique avec ses différentes adresses.

2. Travail demandé

On veut convertir une adresse d’un système en un autre système. Pour cela, on propose de réaliser les fonctions de conversion suivantes :

CnvAfBm du système AF vers le système BM
CnvBmLex du système BM vers le système LEX
CnvLexAf du système LEX vers le système AF

Vous devrez expliciter ces fonctions de conversion sous forme d’algorithmes en utilisant la syntaxe vue en cours (module, paramètres, locales, globales...). Ensuite, vous viendrez traduire ces fonctions en Apl et en Rexx. On ajoutera un programme principal qui utilise (pour Apl) un vecteur d’adresses BM ou (pour Rexx) un fichier qui contient des adresses AF (à raison d’une adresse par ligne).

Ce miniprojet est à rédiger seul(e). Vous avez certainement à effectuer une recherche bibliographique simple (indiquez vos sources). Vous m’enverrez en attaché par mail un fichier .zip qui contient tout votre travail, à savoir : une zone de travail Apl (Workspace), un fichier texte du programme Rexx, ainsi qu’un document au sens de Word pour Windows ou de LateX qui contiendra les algorithmes, la documentation et vos commentaires.

Ces fichiers auront pour nom vos initiales : Jomes Band fournira donc JB.WS, JB.REX et JB.DOC le tout dans JB.ZIP ; par contre Nona Higane rendra NH.WS, NH.REX et NH.DOC.

Ce travail de recherche, programmation et rédaction est à rendre pour le mardi 08 décembre (aucun retard ne sera toléré).

Il vaut mieux rendre un travail incomplet que de ne rien rendre. La qualité des algorithmes, en particulier leur simplicité et leur lisibilité sera appréciée.

Indiquez clairement vos choix : si un terme vous parait ambigu, précisez sa définition pour vous. Justifiez vos modes de programmation ; récursivité ou linéarité, appel d’opérateurs, de fonctions prédéfinies ou écriture de boucles explicites. Nommez distinctement vos variables (en particulier, vous utiliserez systématiquement au moins 3 lettres par identificateur). N’hésitez pas à commenter sans dépasser toutefois un commentaire toutes les 8 lignes en moyenne (sauf pour l’en-tête).

Vous n’êtes pas obligé(e) de tout tester dans tous les sens. Effectuez donc des tests élémentaires. L’affichage des résultats à l’écran devra être très propre, très soigné. Ainsi en cas d’affichage numérique multi-lignes, on mettra bien les unités sous les unités, les dizaines sous les dizaines etc. Soignez aussi la rédaction, l’orthographe...

[figure: A1F1; A1F2; A1F3 A2F3; A1F3 A2F2 A3F1; A1F3; A1F4; A1F2 A2F1; 1; 2; 3; 7; 36; 37; 6; 4; 8; 5; 1; 11; 111211; 111212; 111; 1111; 112; Figure 2 : Différentes adresses pour un même arbre topologique]