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)]]