Le calcul formel qui constitue la base de l'informatique s'implémente dans des structures de données que sont les graphes orientés, avec une racine où on entend par racine, un sommet du graphe à partir duquel on peut atteindre tous les autres sommets. Il existe un moyen commode en javascript pour créer de telles structures de données qui consiste à perfectionner la classe des Array. On fixe ainsi quelques principes généraux qui vont simplifier la programmation :
Les sommets du graphe sont des noeuds c-à-d des listes programmées en javascript sous forme d'Array avec des attributs supplémentaires et des méthodes supplémentaires :
Les arguments de la liste sont undefined ou bien ont pour valeur un autre noeud ce qui constitue un arbre. Et ces emboitements de noeuds peuvent être récurcifs ce qui transforme l'arbre en un graphe orienté. Les noeuds d'arité nulle correspondent aux feuilles. Chaque feuille comme chaque noeud est identifié par son attribut id. Cette structure de base est utilisée dans de multiple contexte. Lorsqu'elle est utilisée pour mémoriser un terme d'un langage terminologique, le noeud désigne alors un terme ou un sous-terme, et nous avons les conventions suivantes :
Notez que l'opérateur peut lui-même être un noeud d'arité non nulle, ce qui permet d'implémenter un langage terminologique plus riche appelé langage alpha.
On définit la classe Noeud qui hérite de la classe Array. Le constructeur Noeud(n) crée un noeud d'arité n en initialisant ses arguments à undefined.
class Noeud extends Array { Cela crée la classe Noeud qui hérite de la classe Array. static get [Symbol.species]() {return Array} Les méthodes d'Array appliqué à un Noeud retournerons des Array.
(Voir https://fr.javascript.info/extend-natives)static N = 0 Attribut de classe initialisé à zéro (Compteur). id Attribut d'objet identifiant l'objet. p=false
LAttributs d'objet : Flag de passage.
Attributs d'objet : Lien vers un autre noeud.constructor(n) { Constructeur d'objet. super(n) Appelle le constructeur d'Array. this.id=Noeud.N Initialise l'attribut id de l'objet créé à l'attribut de classe N. Noeud.N++ Incrémente l'attribut de classe N. }
}
Nous ne faisons pas de distinction entre noeud et feuille. Cela va simplifier la programmation en posant des règles générales s'appliquant aussi bien aux feuilles qu'aux noeuds. Une feuille est un noeud d'arité nulle. Et souvant, nous désignerons par noeud un noeud d'arité non nulle.
Chaque noeud d'arité n offre n voies numérotées de 0 à n-1. La méthode A(v) appliquée à un noeud, avance sur la voie numéro v du noeud, et si l'arité du noeud est plus petite que v+1 alors on augmente son arité jusqu'à v+1, et si la destination n'est pas encore créée alors on y crée un noeud d'arité zéro. Puis on retourne le noeud d'arrivé.
Dans un tel graphe, un chemin partant d'un noeud est une suite de numéro de voie. Par exemple considérons le chemin S = [v1,v2,v3...]. La méthode C(S) appliquée à un noeud M, avance à partir du noeud M selon le chemin et retourne le noeud d'arrivé. Ainsi M.C([v1,v2,v3]) correspondra à l'instruction M.A(v1).A(v2).A(v3)
Notez que javascript peut changer la taille des Array sans avoir besoin de modifier l'adresse d'entrée de l'Array faisant que les liens allant vers cette Array ne sont pas détruit.
Les méthodes A(v), C(v), se programment dans la classe Noeud comme suit :
class Noeud extends Array { A(v) { ... } C(v) { ... } }
A(v) { Ce déplace sur le fils n°v et le crée s'il n'existe pas. if (v<this.length) { if (this[v]==undefined) { Si le noeud de destination n'est pas définie,
on le crée
et on le retourne.this[v]=new Noeud(0) return this[v] } else { let r=this[v] Si le noeud de destination est lié vers un autre noeud,
on retourne le noeud final de la chaine des liens.while (r.L!=undefined){r=r.L;} return this[v] } } else { this.length=v+1 Si le noeud source n'a pas une taille assez grande,
alors on augmente la taille du noeud
et on crée le noeud destination
que l'on retourne.this[v]=new Noeud(0) return this[v] }
}C(L){ Se déplace selon le chemin L. let r=this for(let x in L){ r=r.A(L[x])} return r }
La méthode aff() affiche le noeud comme suit : elle produit une chaine de caractères contenant l'identifiant du noeud suivi d'une liste d'identifiant ou de "." si le noeud fils n'existe pas, séparés par des virgules.
aff(){
let s=""
Retourne le noeud sous forme d'une chaine de caractère.
Par exemple "12(4,.,23,.)"
if (this.length==0) {return this.id}
s=s+this.id + "("
Si c'est une feuille,
affichez son numéros.let b=true
for(let x of this) {
if (b) {
b=false
flag indiquant le début de la boucle for
Pour chaque fils.
Si c'est le premier fils
if (x==undefined) {
s=s + "."
}
S'il est undefined,
affichez "."
else {
let y=x
while(y.L!=undefined){y=y.L;}
s = s + y.id;
}
Sinon,
si le noeud fils est lié vers un autre noeud,
on considère le noeud final de la chaine des liens.
et on affiche son id
}
else {
if (x==undefined) {
s=s + ",."
} else {
let y=x
while(y.L!=undefined){y=y.L;}
s = s + "," + y.id
}
}
}
s=s+")"
return s
}
Répétition du progrmme pour éviter l'affichage d'une virgule comme préfixe.
Si le noeud fils n'existe pas
affichez ",."
Sinon,
si le noeud fils est lié vers un autre noeud,
on considère le noeud final de la chaine des liens.
et on affiche son id après ue virgule
La méthode affG() parcours le graphe accessible à partir du noeud. Il affiche la liste de tous les noeuds atteignables à partir du noeud appelant, sous forme d'une chaine de caractères contenant la listes des noeuds séparés par des caractères blancs. Pour parcourir le graphe sans répéter les boucles indéfiniement, on utilise le flag de passage pour marquer les noeuds qui ont été visités et ainsi ne pas se répéter. Puis il faut après avoir parcouru le graphe, refaire le parcours pour remettre les flag de passage à false. Cela nécessite de définir dans la méthode affG() deux fonctions locales affG0(x) et p0(x). La première affiche le graphe atteignable à partir du noeud x, et la seconde fonction remet à false les flag de passages atteignable à partir du noeud x.
affG(){
var s=""
var n=0
var f=0Retourne le graphe accessible à partir du noeud,
sous forme d'une liste de chaines de caractères séparé par des blancs.
Par exemple : "2(1,.,3,.) 1(.) 3(4,2) 4 2(3,3,.)"function affG0(M) {
Parcours le graphe à partir du noeud en profondeur d'abord. while (M.L!=undefined){M=M.L;}
M.p=true
Aspect : toujours se placer à la fin de la chaine des liens.
Flag de passage misà vrai.if (M.length>0) {n++} else {f++} Comptage des noeuds et des feuilles. s= s + M.aff() + " "
On affiche le noeud en cours M et un espace. for(let x of M){
if (x !=undefined){Pour chaque fils.
Si le fils existe,let y=x
while (y.L!=undefined){y=y.L;}
Aspect : toujours se placer à la fin de la chaine des liens.if (!y.p) {
affG0(y)
}Si on est pas déjà passé par ce noeud y,
Alors afficher le graphe accessible à partir de ce noeud y.
(ajouter à la chaine de caractère s)}
}
}function p0(M) {
M.p=falseParcourt le graphe accessible à partir du noeud,
pour remettre à false les flag de passage.for(let x of M){
if (x !=undefined){Pour chaque fils.
Si le fils existe,let y=x
while (y.L!=undefined){y=y.L;}Aspect : toujours se placer à la fin de la chaine des liens.
Flag de passage mis à vrai.if (y.p){
p0(y)
}Si le flag est vrai,
alors lancer la procédure pour ce fils.}
}
}affG0(this)
p0(this)
s="Graphe "+n+" noeuds et "+f+" feuilles :\n" + s
return [s,n,f]Retourne le graphe sous forme de chaines de caractère s.
Remet les flag de passage à false.
Indique d'abord le nombre de noeuds et de feuilles.
Retourne s.
Un algorithme amusant que l'on peut facilement programmer consiste à découvrir le monoïde fini définie par des égalités de mots. Chaque lettre correspond à un déplacement d'un noeud. Chaque mot correspond à un chemin. Par exemple aaa=1, bbb=1, ab=ba où le chemin 1 correspond au chemin vide, va définir une structure engendrée par a et b et une opération de produit, qui sera constituée de 9 éléments, comme (Z/3Z)^2. Pour démontrer cela empiriquement on construit un graphe où chaque noeud possède deux fils. Il existe deux voies, la multiplication par a ou la multiplication par b. Puis on fusionne les noeuds finaux des chemins selon les trois égalités et en partant de chaque noeud.
La fusion de deux noeuds nécessite de parcourir tous le graphes pour rétablir les liens ce qui est d'une complexité plus grande. Il est possible de retrouver une complexité d'ordre linéaire en procédant en différé. On marque le Noeud devant être fusionnée avec un lien vers le noeud avec lequel il fusionne, et on reporte dans un aspect, la tâche d'établir les raccourcis lors de chaque passage.
fusion(x) {
let a=thisFusionne le noeud avec le noeud x. while (a.L!=undefined){a=a.L;}
while (x.L!=undefined){x=x.L;}Aspect : toujours se placer à la fin de la chaine des liens. f (a!=x){
a.L=x
if (a.length>x.length) {x.length=a.length} else {a.length= x.length}Si a différent de x,
alors lier a à x,
et si arité de a plus petit que celle de x,
alors fixer l'arité de a à celle de xfor(let i=0;i<a.length;i++){ Pour chaque numéro de voie i if (a[i]==undefined) {
a[i]=x[i]
continue
}Si a[i] undéfini,
alors x[i]=a[i] et continuer la boucle en iif (x[i]==undefined) {
x[i]=a[i]
continue
}Si x[i] undéfini,
alors a[i]=x[i] et continuer la boucle en ilet y=a[i]
let z=x[i]
while (y.L!=undefined){y=y.L;}
while (z.L!=undefined){z=z.L;}
y.fusion(z)
}
}
}Sinon
Aspect : toujours se placer à la fin de la chaine des liens.
et lancer l'appel recurcif
(inutile d'utiliser le flag de passage car une fois passé,
les noeuds sont égaux et closent la récursion)
On programme un aspect dont la mission est d'établir les raccourcis lors de chaque parcours d'une succession de liens. L'aspect remplace les instructions de la forme while (x.L!=undefined){x=x.L;} par les instructions suivantes :
let q=[]
while (x.L!=undefined){q.push(x);x=x.L}
for (let i=0;i<q.length-1;i++) {q[i].L=x}
L'automate doit pouvoir lire par exemple "abacb=1, aca=1, bab=bc, cc=1", numéroter les lettres utilisées (a,1), (b,2), (c,3) et traduire par les fusions correspondantes M.fusion(M.C[1,2,1,3,2]), M.fusion(M.C[1,3,1]), M.C([2,1,2]).fusion(M.C[2,3]), M.fusion(M.C[3,3]).
On ajoute aux noeuds un attribut R supplémentaire qui pointe un autre noeud. Ainsi L et R désignent deux fonctions de E sur E, où E est l'ensemble des noeuds ou sommets du graphe. On accède à l'image L(x) par l'instruction x.L, et de même on obtient l'image R(x) par l'instruction x.R :
Lorsqu'une fonction f n'est pas définie pour x alors f(x)==undefined qui peut être considéré comme un élément spécial. On dira qu'une fonction f est injective, ou qu'elle est plongeante, ou qu'elle est inversible, si et seulement si quelque soit deux éléments distincts x et y, si leur image par f sont définies alors leurs images f(x) et f(y) sont distinctes, ce qui permet de définir leur images inverse, la fonction inverse notée `f^-1` et qui n'est définie que sur `f(E)`.
Etant donné un tel graphe avec une racine, on définit sur l'ensemble des sommets du graphes la loi `"*"` de composition induite par la concaténation des chemins, comme suit : Chaque sommet peut être désigné par un chemin qui permet d'y accéder à partir de la racine. La composition de deux sommets s'obtient en concaténant un chemin allant de la racine au premier sommet suivant par un chemin allant de la racine jusqu'au second sommet, et en retournant le sommet d'arrivé. S'il y a plusieurs chemins possibles, il faut qu'ils aboutissent tous sur le mêm sommets, ce que l'on obtient en fusionnant les sommets devant être égaux.
Dans un tel graphe, chaque sommet correspond à un déplacement dans le graphe. Si le graphe est n-aire, c'est à dire si chaque noeuds à n fils, alors Il forme une structure `(E,"*")` engendré par n élément.
La fonction f respecte la composition
Si le graphe n-aire représente une structure mathématique engendré par n éléments où chaque numéro de voie des noeuds correspond à la composition par respectivement un des n éléments générateurs, alors elle doit être symétrique : chaque noeuds doit pouvoir devenir le noeud racine, une bijection respectant la composition doit exister entre le graphe et n'importe qu'elle sous-graphe.
On propose un algorithme pour construire cette bijection entre le graphe de racine x et le graphe de racine 1. Au dépard les fonctions L et R sont définies nul part. On construit L en même temps que l'on construit la fonction inverse R.
On commence par associé les noeuds racines x.L=1 et 1.R=x, puis on associe chaque fils de x respectivemenent à chaque fils de 1 d'une façon récurcive en rappellant cet algorithme. Mais à chaque fois que l'on crée un lien y.L, si l'image inverse n'existe pas on la crée y.L.R=y, et si elle existe on vérifie que c'est bien égale y.L.R==y et sinon on fusionne les deux noeuds y et y.L.R.
Ainsi on construit une bijection en fusionnant les noeuds qui sont contraint à l'égalité par l'exigence de symétrie.
---- 9 mai 2024 ----
---- 26 avril 2024 ----