Bonjour,

Voilà j'ai un exercice dans une Unité d'enseignement à la fac intitulée "Réseaux Personnels". J'ai un problème dans cet exercice : je ne le comprends pas.
Si quelqu'un pourrait m'aider à comprendre ce serait génial !

Voici l'intitulé :
Un groupe de 2^(n) - 1 routeurs sont interconnectés par une arborescence binaire centralisée comportant un routeur par noeud. Le routeur i communique avec le routeur j en envoyant un message à la racine qui le transmet à ce dernier. Déduisez une expression approximative du nombre moyen de bonds par message pour une valeur n élevée, en partant du principe que toutes les paires de routeurs sont semblables.
Donc ce que je ne comprend pas, c'est :
- une arborescence binaire centralisée (qu'est-ce que ça signifie)
- la racine (à quoi correspond-elle ?)
- quel genre d'expression dois-je obtenir ? (mais je pense qu'avec juste les deux éléments ci-dessus je comprendrais déjà beaucoup plus)

J'ai hésité entre poster ce topic ici et dans le bistro, j'espère que ça ne dérange pas.

Merci d'avance !

FoxLegend
tu as séché le cours ?? 😉
Rapide réponse sur un coin de table, sans garantie ...

Une arborescence binaire est une arborescence dont chacun des noeuds a au plus deux enfants. Elle est centralisée lorsqu'elle me semble procéder d'un noeud et d'un seul ...

La racine est ainsi le plus haut noeud.

(2^n) - 1 noeuds. A chaque noeud correspond un routeur.

On compte les noeuds selon les niveaux:

* plus haut rang: 0 (la racine)
* rang de niveau 1 : 2^1
* rang de niveau 2: 2^2
* rang de niveau x-1: 2^(x-1)
* rang de niveau x = les noeuds sans fils

Par convention, on numérote les rangs à partir de 0. Les niveaux sont par commodité numérotés à partir de 1.

Chaque noeud possédant un fils au moins est un routeur. Les noeuds sans fils sont des extrêmités.

Nombre de niveaux d'arborescence compte tenu du nombre de routeurs (2^n) -1?

Prenons ne cas d'une arborescence à 4 niveaux, racine et extrêmités comprises. Le nombre de routeurs est : 1 + 2^1 + 2^2 = 7; en ce cas, n vaut 3. Pour une arborescence à 5 niveaux, Le nombre de routeurs devient: 1 + 2^1 + 2^2 + 2^3= 15; en ce cas, n vaut 4.

Un réseau en arborescence binaire de 2^n - 1 routeurs définit (n+1) niveaux (racine et extrêmités comprises), ou rangs. Un paquet transmis par une extrêmité A (située au niveau x, x <=n ) traversera (x-1) routeurs pour joindre la racine, traversée du routeur racine compris. Ce paquet, pour parvenir à l'extrêmité B (de rang y <=n), si le transit est bien opéré par la racine, traversera donc au total (x-1) + (y-2) routeurs. Si l'on considère qu'un bond est une traversée d'un routeur, il y aura donc (x-1) + (y-2) bonds.

L'énoncé demande "une expression approximative du nombre moyen de bonds par message pour une valeur n élevée", en considérant deux routeurs quelconques, i et j, situés dans l'arborescence.

Il faut donc calculer la moyenne de bonds en considérant les différents cas possibles de positionnement de routeurs selon les rangs de l'arborescence (calculer le nombre de bonds dans les différents cas possibles en faisant varier x et y, pour des valeurs > 1 et <= n et établir la moyenne).

Eddy33 et Pikachu_2014, vous qui êtes encore sous les auspices de l'enseignement (ou presque ...)?
Merci infiniment, c'est même beaucoup plus que je n'espérait !
J'ai bien compris maintenant le système d'arborescence et la racine (ça ressemble beaucoup aux arbres binaires en algorithmique). Je vois mieux l'architecture de la chose et donc l'énoncé me paraît énormément plus clair !

Encore merci herrib !