Arborescence

Arborescence

En mathématiques, plus précisément dans la théorie des graphes, une arborescence est un arbre comportant un sommet particulier r, nommé racine de l'arborescence à partir duquel il existe un chemin unique vers tous les autres sommets[1].

En informatique, cette notion désigne souvent celle d'arbre de la théorie des graphes[1]. Une arborescence désigne alors généralement une organisation des données en mémoire, de manière logique et hiérarchisée utilisant une structure algorithmique d'arbre. Cette organisation rend plus efficace la consultation et la manipulation des données stockées. Les usages les plus courants en sont :

La logique générale de l'arborescence coïncide avec le modèle relationnel du SQL : 1 vers N et réciproquement 1 vers 1. Un nœud peut posséder N feuilles, mais chaque feuille ne possède qu'un seul nœud.

Sommaire

Usage pour la gestion des disques

À la base d'une arborescence se trouve un 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 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 la plupart 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, Forth, machine virtuelle 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. Le langage des sourds-muets possède une syntaxe assez proche de ce type de notation : il plante le décor avant, positionne les acteurs puis indique l'action en dernier.

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 1er 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 - Arbo graphique
    • \ : descendre, indique le 1er enfant
    • / : remonter, indique le dernier enfant
    • - : rester sur le même niveau, les enfants intermédiaires, implicitement le 1er parent
    • | : 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
  • Autre système - Taaluketti (langue artificielle; ce système est très proche du précédent dans sa logique)
    • Mécanisme suffixé, avec des suffixes pour indiquer l'arité.
    • aucun suffixe : élément seul
    • -s : élément le plus à gauche et non unique
    • -n : élément le plus à droite et non unique
    • -k : élément médiant, ni le plus à gauche, ni le plus à droite
    • ba be → (ba)be • bas ben bi → (ba be)bi • bas bek bin bo → (ba be bi)bo • bas bek bik bon bu → (ba be bi bo)bu
  • Autre système - Infixe+niveau
    • On ajoute le numéro de niveau avant ou après
    • 0 signifie que c'est une feuille ou un symbole terminal
    • deux plus trois → deux0 plus1 trois0
    • deux plus (trois fois quatre) → deux0 plus2 trois0 fois1 quatre
    • (deux plus trois) fois quatre → deux0 plus1 trois0 fois2 quatre0

Notes et références

  1. a et b Robert Faure, Bernard Lemaire et Christophe Picouleau (ill. digital vision), Précis de recherche opérationnelle : Méthodes et exercices d'application, Paris, Dunod, 2009, 6e éd., 572 p. (ISBN 978-2-10-052652-9) 

Voir aussi

Sur les autres projets Wikimedia :


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Arborescence de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • arborescence — [ arbɔresɑ̃s ] n. f. • 1838; de arborescent 1 ♦ Bot. État d un végétal arborescent. Partie arborescente d une plante. 2 ♦ Par anal. Forme arborescente. Les arborescences du givre. ⇒ arborisation. Arborescence respiratoire. 3 ♦ Didact. Graphe en… …   Encyclopédie Universelle

  • Arborescence — can refer to multiple topics:* A word; see * Arborescence (graph theory): a type of directed graph * Arborescence (album): an album by Ozric Tentacles …   Wikipedia

  • Arborescence — Ar bo*res cence, n. The state of being arborescent; the resemblance to a tree in minerals, or crystallizations, or groups of crystals in that form; as, the arborescence produced by precipitating silver. [1913 Webster] …   The Collaborative International Dictionary of English

  • arborescence — ● n. f. ►TYPE Voir arbre (arborescence en est généralement une variante un tantinet pédante) …   Dictionnaire d'informatique francophone

  • arborescence — From the French word for flowchart. Commonly used among Montreal web designers. Hey, did you finish the arborescence yet? I need an arbo before I start working on the interface …   Dictionary of american slang

  • arborescence — From the French word for flowchart. Commonly used among Montreal web designers. Hey, did you finish the arborescence yet? I need an arbo before I start working on the interface …   Dictionary of american slang

  • arborescence — medžio struktūra statusas T sritis automatika atitikmenys: angl. tree structure vok. baumförmige Struktur, f; Baumstruktur, f rus. древовидная структура, f pranc. arborescence, f; structure arborescente, f …   Automatikos terminų žodynas

  • Arborescence (informatique) — Arborescence 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. Cette organisation rend plus efficaces la… …   Wikipédia en Français

  • Arborescence (album) — Infobox Album Name = Arborescence Type = Album Longtype = Artist = Ozric Tentacles Released = 1994 Recorded = 1993 1994 Genre = Psychedelic rock Space Rock Length = 49:17 Label = Dovetail Records Producer = Reviews = * Allmusic Rating|4|5… …   Wikipedia

  • Arborescence (graph theory) — In graph theory, an arborescence is a directed graph in which, for a vertex v called the root and any other vertex u, there is exactly one directed path from v to u. In other words, an arborescence is a directed, rooted tree in which all edges… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”