Des arbres binaires pour le contrôle de tirages pseudo-aléatoires

Cette application permet de construire des arborescences binaires. Les arbres peuvent ensuite être utilisés pour orienter les chances de tirage de valeurs aléatoires.

Après avoir chargé les fichiers Cours-Smalltalk-Arbres.st et Cours-Smalltalk-Courbes.st, pour construire un arbre, on lance l'aplication avec l'expression : (VLArbreApplication on: (VLArbin new)) open

Apparaît alors une fenêtre avec un seul noeud, la racine de l'arbre, représenté par un carré centré en haut de la vue.

Pour construire un fils gauche, on clique sur le noeud et on glisse la souris vers la gauche.

Si on donne un coup de souris partant d'un noeud et allant vers la droite (respectivement à gauche), deux cas ce présentent :

L'échelle de visualisation change au fur et à mesure de la construction pour que la totalité de l'arbre tienne dans la fenêtre.

Si l'arbre devient trop dense, on peut ouvrir une nouvelle fenêtre sur un sous-arbre par un clic sur un noeud avec le bouton jaune (celui du milieu).

 

1/ Le modèle

Chaque noeud de l'arbre possède un fils gauche et un fils droit. Generateur est une variable de classe pointant vers une instance de la classe Random.


Model subclass: #VLArbin

instanceVariableNames: 'gauche droite '

classVariableNames: 'Generateur '

poolDictionaries: ''

category: 'Cours-Smalltalk-Arbres'

 


 

De façon à mettre à jour automatiquement les différentes fenêtre portant sur les mêmes noeuds, les noeuds sont definis comme des instances d'une sous-classe de Model, et chaque noeud est rendu dépendant de ses fils. Ainsi, quand on modifie un noeud, son père étant dépendant reçoit un message de mise à jour #update:. S'il est la racine d'un arbre, il est le modèle d'une vue, et c'est la vue qui reçoit le message de mise à jour. S'il n'est pas la racine, le message de mise à jour est retransmis au père, etc... jusqu'à la racine.

 


VLArbin [accessing]


droite: foo

"Le même sous-arbre peut apparaitre dans des vues différentes.

en rendant un arbre dépendant de ses fils, en signalant un changement

si une branche est modifiée et en transformant tout message #update: en #changed (voir

le protocol [updating] ).

Le message de mise à jour et retransmi jusqu'a la racine dont le dependant est la vue.

Toutes les vues concernées par une modification seront remises à jour."

 

droite notNil ifTrue: [ droite removeDependent: self ].

droite := foo.

foo notNil ifTrue: [ foo addDependent: self ].

self changed


La méthode de mise à jour #update: ce contente de retransmettre le message aux dépendants. 


VLArbin [updating]


update: aSymbol

"Un de mes fils à changé, donc j'ai changé.

Je previens mes dépendants"

self changed


 

VLArbin est sous-classe de Model pour que l'implémentation des dépendances soit faite par une variable d'instance. Si VLArbin était sous-classe de la classe Object, les dépendances seraient implémentées par un dictionnaire. L'inconvénient de l'implémentation par dictionnaire est le risque de conserver des instances inutilement en mémoire. Il faut impérativement envoyer un message #release à tout objet devenu inutile, ce qui impose de savoir quand un objet devient inutile.

 

Aléatoire

 

Dans le protocole [aleatoire] nous avons crée trois méthodes :

La première #randomIntegerBetween:and: délivre une valeur pseudo-aléatoire entière comprise entre deux bornes données avec une chance équivalente pour chaque valeur.


VLArbin [aleatoire]


 

randomIntegerBetween: value1 and: value2

"Ramène un entier pseudoaléatoire compris entre value1 et value2 incluses.

value1 et value2 doivent être entières.

La répartition est en principe équiprobable."

 

"Exemples :

| b |

b := VLArbin new.

((1 to: 1000) collect: [:i | b randomIntegerBetween: 1 and: 100 ]) asBag

 

| b |

b := VLArbin new.

((1 to: 1000) collect: [:i | b randomIntegerBetween: 100 and: 1 ]) asBag

 

"

^ value1 > value2

ifTrue: [ (Generateur next * (value2 - value1 - 1)) asInteger + value1 ]

ifFalse: [ (Generateur next * (value2 - value1 + 1)) asInteger + value1 ]


La seconde méthode, #entre:et: utilise l'arborescence binaire pour choisir les bornes des choix aléatoires.

Si le noeud recevant le message n'a pas de fils gauche, la valeur v1 est utilisée comme borne par contre, si le noeud a un fils gauche, c'est le résultat du message retransmis au fils gauche qui sera utilisé comme borne. De même pour la borne v2 et le fils droit.

Ceci revient à considérer l'arbre comme un arbre d'appel de fonction.

Un noeud sans fils est équivalent à l'appel : f(v1, v2)

Un noeud avec un fils gauche est équivalent à l'appel : f(f(v1, v2), v2)

 


VLArbin [aleatoire]


 entre: v1 et: v2

| g d |

g := gauche isNil ifTrue: [ v1 ] ifFalse: [ gauche entre: v1 et: v2 ].

d := droite isNil ifTrue: [ v2 ] ifFalse: [ droite entre: v1 et: v2 ].

^ self randomIntegerBetween: g and: d

 


 

 La méthode #histogramme: enfin construit un histogramme à partir de n tirages aléatoires entre 1 et 100.

L'application VLHistogrammeApplication permet de le visualiser.

 

 

 

Pour ouvrir l'histogramme correspondant à un noeud, on fait un shift-clic avec le bouton rouge sur le noeud.

 

 (à suivre)

 


Mise à jour le 26/5/1997

v i @ a i . u n i v - p a r i s 8 . f r