Arborescence 76749 27833749 2008-03-26T23:35:40Z 85.192.232.229 /* Notation */ {{ébauche|informatique}} Une '''arborescence''' permet d'organiser les données en mémoire ou sur disque, de manière logique et hiérarchisée. C'est un cas pratique d'utilisation de la structure algorithmique d'[[arbre (informatique)|arbre]]. Cette organisation rend plus efficaces la consultation et la manipulation des données stockées. Les usages les plus courants en sont : * l'[[Répertoire (informatique)|arborescence de fichiers]], qui est l'organisation [[hiérarchie|hiérarchique]] des [[Fichier (informatique)|fichier]]s sur une [[partition de disque dur|partition]], et dans certains cas de partitions entre elles, par exemple: partitions virtuelles (« lecteurs logiques ») dans des partitions réelles. * le [[tri arborescent]] en mémoire * les fichiers en mode [[séquentiel indexé]] ==Usage pour la gestion des disques== À la base d'une arborescence se trouve un [[Répertoire (informatique)|répertoire]] appelé la racine. Ce répertoire peut contenir des fichiers et des répertoires, qui eux-mêmes peuvent contenir la même chose. Si les fichiers et les répertoires sont placés de manière cohérente, la recherche de fichier est relativement aisé et rapide. ==Les différentes façons de linéariser une arborescence== Le gros problème est qu'une arborescence est souvent représentée sous la forme d'un arbre graphique et que le langage et l'écriture classique sont linéaires. Depuis longtemps, différents types de représentation co-existent, selon la méthode de parcours utilisée et le domaine d'application. ==Arité== Plus simplement, l'arité indique le nombre d'arguments ou d'enfants utiles ou nécessaires à une fonction ou un parent. Ainsi dans '''10+20''', l'addition (+) a besoin d'un terme à gauche (10) puis d'un autre à droite (20), son arité est donc de 2. Dans '''abs(mavar)''', la valeur absolue n'a besoin que d'un seul argument (mavar), son arité est est de 1. En [[Prolog]], la clause '''pere(alain,bernard).''' a une arité de 2 car la relation "pere" exige un parent et fatalement un enfant. L'arité peut être fixe comme elle peut être variable. Ainsi l'opérateur * est d'arité fixe à 2 dans 90% des langages informatiques, on écrit 2*3 pour exprimer un calcul. Par contre, en [[Lisp]], on peut écrire (* 2 3 4) pour exprimer 2*3*4 ou bien (* 2 3 4 5) ce qui est une arité variable. ==Types de parcours== ===Préfixe=== Dans ce mécanisme, le parent est mis en premier, puis suivent ses enfants. L'ordre/commande est par devant, les éléments complémentaires ensuite. Voir aussi l'exemple linguistique [[VSO]]. Exemple : + 2 3 Cette notation est simple à comprendre pour l'être humain et se programme facilement. ===Infixe=== Dans ce mécanisme, le parent est inséré entre ses enfants. Les Mathématiques et la logique humaine procèdent souvent ainsi. Sujet Verbe Complément. Exemple : 2 + 3 Le gros problème de l'infixe est l'ambiguïté et on doit souvent recourir à des parenthèses. Ainsi 10+20*30 doit-il s'analyser comme (10+20)*30 ou comme 10+(20*30) ? Pour lever une partie des difficultés, il existe une priorité des opérateurs dans bon nombre de langages. ===Suffixe=== Le parent est mis après ses enfants. Cette logique semble bien peu humaine mais elle est très utilisée en informatique, [[Pile (informatique)|pile]], [[Forth (langage)|Forth]], machine virtuelle [[Java (langage)|Java]], [[Postscript]] et autres. Exemple : 2 3 + Cette notation est ardue pour l'être humain mais très facile à mettre en place d'un point de vue informatique ou automate. ==Notation== ; Arité fixe * Préfixe, arité fixe ** + 2 3 ** père Alain Bernard ** mange chat souris * Infixe, arité fixe ** 2 + 3 ** Alain est_le_père_de Bernard ** chat mange souris * Suffixe, arité fixe ** 2 3 + ** Alain Bernard père ** chat souris mange ; Arité variable * Préfixe, arité variable ** (+ 2 3 4) ** add(2,3,4) ** printf("%d %d %s",n,m,t) ** begin ... end ** add:3 20 30 40 (on indique le nombre d'arguments) ** add 3 20 30 40 (le 1{{er}} argument indique l'arité utile) * Infixe, arité variable ** a-b (soustraction) -b (négatif) ** a*b (multiplication) *b (contenu du pointeur en langage C) * Suffixe, arité variable ** (2 3 4 +) ** marqueurpile 2 3 4 add ** 20 30 40 add:3 ** 20 30 40 3 add (le dernier argument indique l'arité utile) * Autre système ** <code>\</code> : descendre, indique le 1{{er}} enfant ** <code>/</code> : remonter, indique le dernier enfant ** <code>-</code> : rester sur le même niveau, les enfants intermédiaires, implicitement le 1{{er}} parent ** <code>|</code> : arité 1, descendre puis remonter (en cas d'enfant unique) ** Exemple : 2*3*4+5*6 → préfixage -add\mul\2-3/4\mul\5/6 ==Voir aussi== {{Wiktionnaire}} * [[Théorie des graphes]] {{Portail informatique}} [[Catégorie:Système de fichiers]] [[Catégorie:Arbre (structure de données)]] [[en:Tree view]] [[de:Baum (Widget)]]