Un semi-groupe est un ensemble muni d'une loi de composition associative, appelé produit, que l'on note par absence de symbole, juste en juxtaposant les arguments, tel que `ab` pour le produit de `a` et de `b`.
Le semi-groupe est un monoïde s'il contient un élément neutre, que l'on note `1`. Notez qu'il est toujours possible d'ajouter un élément neutre pour transformer un semi-groupe en un monoïde.
La notion de semi-groupe est lié à la notion d'application. Quelque soit un ensemble `E`, tout ensemble d'applications de `E"→"E` que l'on clos par composition forme un semi-groupe. Et réciproquement tout semi-groupe et isomorphe à un ensemble d'applications de `E"→"E` clos par composition. On démontre cette réciproque en faisant agire le semi-groupe `S` sur lui-même par translation gauche. Chaque élément `s "∈" S` possède ainsi un deuxième rôle qui est une translation gauche :
`s |-> (x"↦"sx)`
Et en constatant qu'il est toujours possible d'ajouter dans un semi-groupe un nouvel élément neutre sans changer la loi de composition des éléments préexisant, on en déduit qu'il est toujours possible de choisir un tel second rôle vérifiant que si deux élements `a,b` ont même second rôle, c'est à dire si `AAx, ax"="bx`, alors nécessairement `a"="b`. On dira dans ce cas que `S` agit sur lui-même de façon fidèle. Autrement dit l'application qui associe chaque élément `s "∈" S` à l'application `(x"↦"sx) "∈" (S"→"S)` est injective. Cette condition permet de pouvoir identifier les éléments de `S` à leur second rôle de translation gauche. Puis, l'élément neutre correspond à l'application identité `(x"↦"x)` qu'il est toujours possible d'ajouter si elle n'est pas déjà présente pour former un monoide.
Le semi-groupe se présente alors comme un ensemble d'applications sur lui-même muni de la loi de composition :
`S ⊂ (S"→"(S"→"S))`
Si les applications sont inversibles alors ce sont des bijections, le semi-groupe devient un groupe et on obtient le théorème de Caylet. Tout groupe se présente comme un ensemble de bijections sur lui-même muni de la loi de composition :
`G"⊂"frS_G`
Le monoïde est dit bigène s'il est engendré par deux éléments `a,b` dits générateurs et par l'élément neutre `1` qui fait parti des opérateurs prédisposés par la structure de monoïde. Dans ce cas, on le représente en un graphe orienté binaire. C'est un graphe où chaque noeud possède deux arcs sortants labélisés `a` et `b`. Chaque élément `x` du monoïde est un noeud du graphe. Les arcs labélisés `a` et `b`, partant de `x`, arrive respectivement sur les produits `xa` et `xb`. L'élément `xa` est appelé le fils `a` de `x`. L'élément `xb` est appelé le fils `b` de `x`.
Le monoïde bigène libre est un arbre binaire qui se développe sans fin, avec l'élément `1` comme racine et les éléments `a` et `b` comme générateurs. Chaque élément `x` du monoïde libre est un noeud de l'arbre qui possède `2` fils qui correspondent aux produits `xa` et `xb`.
Un produit quelconque de `a` et de `b` constitue un cheminement tel que par exemple `ab aab b a`. Ce cheminement peut être appliqué à n'importe quel élément `x` du monoïde pour aboutir à l'élément `xab aab ba`.
On construit des sous-monoïdes obtenus à partir de règles d'égalités entre mots, ce qui revient à complèter la théorie du monoïde en ajoutant par exemple les 3 équations suivantes :
`ab = ba`
`aa = 1`
`bbb = 1`
On déclare un tel monoïde en présentant ses générateurs et ses équations comme suit :
`"<" a, b | aa"="1, b b b"="1, ab"="ba ">"`
Chaque équation est une égalité entre deux cheminements et va fusionner des noeuds de cet arbre et le transformer en un graphe binaire, où chaque noeud possède deux arêtes sortantes labélisée `a` et `b`.
Le monoïde bigène est mémorisé sous forme d'un graphe orienté binaire. Les noeuds du graphe correspondent aux éléments du monoïde. Chaque noeuds `x` possède exactement `2` arcs sortants labélisés `a` et `b` et allant sur ses noeuds fils correspondant aux éléments produits `xa` et `xb` du monoïde. Chaque nouvelle règle d'égalité définie une relation d'équivalence dans le monoïde. On obtient la structure quotient, en fusionnant les noeuds équivalents selon les règles d'égalité déclarées. Et pour cela il suffit d'appliquer un principe de relativité affirmant que des cheminements égaux partant d'un même noeuds quelconque aboutissent à un même noeud. Ce principe traduit les équations en règles de fusionnement de noeuds.
Il est alors possible d'exploiter la puissance néguentropique d'un tel graphe pour accroître les connaissances d'égalités entre éléments du monoïde, et obtenir trés rapidement la connaissance complète si le monoïde s'avère fini.
Cette tâche est faite par un programme informatique. On choisi le langage Golang (Go), un langage proche de la machine autant que le langage C, et plus simple à maitriser, qui est adapté pour des développements agiles.
Le graphe, qui représente un monoïde en construction, peut passer par des phases où il atteint de trés grandes tailles pouvant occuper jusqu'à 1 teraoctet. On le mémorise dans un tableau dynamique G. Notez que tout l'espace mémoire de ce tableau n'est pas réservé, il s'agrandira progressivement au cours de son utilisation. La gestion de la mémoire par Go est à la fois plus souple et plus performante. Et de plus nous gérerons nous-même, la mémoire de cette immense tableau.
L'indexe dans ce tableau tient sur un entier de 5 octets.
Pour éviter le débordement de la pile d'appel, qui est limité à 1 Go, on ne programmera pas de fonctions récurcives.
La gestion des pointeurs et de la mémoire correspondante dans Go est simplifiée par la présence d'un ramasse-miette. C'est un système de gestion de mémoire intégrée qui libére les mémoires occupées lorsqu'elle sont rendues inaccessibles. Cela nous permet de pouvoir programmer des algorithmes avec les pointeurs sans avoir à nous préoccuper de libérer les mémoires perdues.
On développe un framework, un ensemble de procédures pour manipuler ce tableau G hebergeant le graphe. On utilise un système d'exploitation Linux, l'éditeur de texte gedit, le compilateur go, et pour le confort bien que cela ne soit pas indispensable la plate forme de développement LiteIDE. Pour l'installation de go, LiteIDE, voir Le langage Go
Pour afficher les graphes ou les portions de graphe, on utilise le paquet graphviz, la commande dot -Tsvg qui permet de convertir la description texte d'un graphe en une imag svg. Et on utilise la commande lximage-qt pour visionner l'image svg.
Quelle est la structure de donnée la plus adaptée pour définir un noeud ? On définie un immence tableau G de cellules qui mémorisera ces noeuds. Ce tableau est suceptible d'occuper toute la mémoire disponnible. Ayant installé une barrette mémoire de 32 Go, je définie la constante MEM = 32 000 000 000. Ce qui me permettra à partir de la taille d'une cellule, de calculer la taille Nmax du tableau G.
La cellule est soit un noeud ou soit une cellule vide. C'est un objet à deux faces. La première face est un noeud intégré dans la gestion du graphe. La seconde face est une cellule libre intégré dans gestion de la mémoire libre de G. Cette seconde face est aussi importante que la première. Les neurologues la comparent à la période nécessaire de rêve (qui s'impose à tout ếtre vivant possédant un cerveau) pendant laquelle la mémoire est rangée.
On déclare G comme suit :
| var G []Cell = make([]Cell, Nmax) var R *Cell = newNoeud() const Nmax = SizeRAM/unsafe.Sizeof(*R) const SizeRAM uintptr = 32000000000 |
G : Tableau de cellules hébergeant le graphe. R : Racine du graphe. Nmax : taille du tableau G en nombre de cellules. SizeRAM : Qantité de mémoire RAM en octets. |
La cellule étant assez vaste, l'index utilisé est un entier de type uint32 tenant sur 4 octets.
La structure du noeud possède à minima, deux index a et b désignant ses fils. Le graphe est le plus souvent incomplet. Les noeuds inconnus correspondent à l'index 0 qui joue le rôle du nil. La première cellule G[0] est donc utilisé à autre chose. Elle contiendra des données propre au graphe tout entier et à sa mémoire libre. Le premier noeud est le noeud racine correspondant à l'élément neutre du monoïde.
Le graphe représente la partie explorée du monoïde. Tout noeud du graphe est accessible à partir de la racine par un chemin. Nous allons programmer un ensemble de procédure qui permettra de construire et de modifier un tel graphe. Dans le processus de construction, le premier noeud devant être construit est la racine, puis ses fils, puis les fils de ses fils, etc., degrés par degrés. On ajoute donc dans le noeud un attribut d indiquant la profondeur. Puis on ajoute un autre attribut L pour désigner un lien vers un autre noeud :
| type Cell struct { | Cell : Type des Cell. |
| a uint32 b uint32 d uint32 L uint32 u int8 } |
a : Noeud fils n°1. b : Noeud fils n°2. d : Profondeur. L : Lien. u : 8 flags. |
Le graphe est un immense tableau de cellules. La mémoire libre dans ce tableau sera gérer par le programme lui-même. La cellule vide possède la même structure mais appliquée pour l'autre face, pour la gestion de la mémoire libre. La signification des attributs change d'une face à l'autre, et c'est le flag `u0` dont la signification est commune au deux faces, qui détermine si c'est un noeud ou une cellule vide :
| type Cell struct { | Cell : Type des Cell. |
| a uint32 b uint32 d uint32 L uint32 u int8 } |
a : Prochaine dernière ou première cellule vide. b : Lien réciproque. d : non utilisé. L : non utilisé. u : 8 flags. |
Lorsque le flag u0 est égale à 1 cela indique que la cellule n'est pas vide et qu'elle constitue un noeud. Les opérations de bits à bits permettent de tester et modifier les bits isolément de x.u qui regroupe ainsi 8 flags dénommés: u0,u1,u2,u3,u4,u5,u7. Nous utilisons le jeu d'instructions suivant :
Description |
.
Bit u0 |
Teste si le bit n°0 dans u est à 1. |
u & 1 == 1 |
| Teste si le bit n°0 dans u est à 0. | u & 1 == 0 |
| Met bit n°0 dans u à 1. | u = u | 1 |
| Met bit n°0 dans u à 0. | u = u &^ 1 |
On définit les macro suivantes fonction de la variable muette u qui représente un uint8 :
|
|
Golang n'implémenta pas de macro. Le programmeur remplacera lui-même le code des macron.
Soit un noeud x. On définit un curseur correspondant au noeud x qui détermine ainsi une position. On utilise un flag de passage, le bit u1, pour mémoriser si on ait déjà passé par x.
Comme nous manipulons les cellules par un index, le noeud racine qui est désigné par la variable globale R est de type uint32. On considérera trois autres variables globales que sont le nombre de noeuds connus N, la liste des équations E, et l'indexe de la première cellule libre L .
| var N = uint32(1) var L = uint32(2) var E []Eq = nil |
N : Nombre de noeuds connues du graphe. L : La premier cellule libre. E : Liste d'équations contraignant le graphe. |
| type Eq struct { | Eq : Type des équations. |
| s1 string s2 string } |
s1 : Premier mot. s2 : second mots. |
En Go, l'instruction make dispose un tabbleau initialisé à zéro.
Au cours du programme des noeuds vont être détruit, transformant le tableau G en un guyère. Le noeud pouvant posséder de nombreux parents, on ne peut pas le déplacer sans passer en revue tous les autres noeuds pour refaire les liens de parenté. c'est pourquoi on ne le déplace pas mais on organise la mémoire libre autour. On gère la liste des noeuds vides, une listes ou les index sont toujors croissant. La variable globale L désigne la première cellule libre d'index le plus petit.
Puis lorsque plusieurs cellules vides se suivent, on mémorise dans la première cellule vide de la séquence, un lien vers la dernière cellule vide de la séquence, et on mémorise le lien réciproque dans la dernière cellule vide de la séquence. Ceci afin de pouvoir parcourir l'ensemble des noeuds sans perdre de temps à sauter sur chaque cellule vide d'une séquence par une succession d'adressage indirecte.
Pour chaque cellule vide, l'attribut L désigne la prochaine cellule vide d'indexe supérieur. L'attribut a vaut 0 si la cellule précédente est vide ou si la cellule suivante est un noeud. Parcontre si la cellule précédente est un noeud et que la cellule suivante est vide alors l'attribut a désigne la dernière cellule vide de la séquence, et un lien reciproque est mémorisé dans cette cellule. La variable globale L désigne la première cellule libre d'index le plus petit.
La création d'un noeud du graphe G se fait en appelant la fonction newNoeud().
| func newNoeud() uint32 { | newNoeud(x) : Créer un nouveau noeud et le retourne. |
x:=L
|
La cellule vide isolée est entourée de noeuds c'est à dire qu'une cellule vide x désignée par son index est dite isolée si x-1 et x+1 sont des noeuds. La cellule vide de début suit un noeud et précède une cellule vide, la cellule vide de fin suit une cellule vide et précède un noeud, et la cellule intermédiaire est entourée de cellules vides.
Le flag u2 indique si la cellule précédente est un noeud.
Le flag u3 indique si la cellule suivante est un noeud.
La fonction a, appliquée à un noeud x va retourner son fils n°1 xa, en le créant s'il n'existe pas. Et la fonction b, appliquée à x va retourner son fils n°2 xb, en le créant s'il n'existe pas :
| func a(x *Noeud) *Noeud { | a(x) : Retourne le premier fils de x et le crée s'il n'existre pas. |
| if x.a != nil {return x.a} a := new(Noeud) N+=1 a.d = x.d+1 x.a = a return a } |
Si x possède un fils n°1 alors retourner-le. On crée un nouveau noeud isolé a. On incrémente N. La profondeur du noeud est celle de x augmentée de 1. Le fils n°1 de x est a. Retourne le noeud a. |
| func B(x *Noeud) *Noeud { | b(x) : Retourne le second fils de x et le crée s'il n'existre pas. |
| if x.b == nil {return x.b} b := new(Noeud) N+=1 b.d = x.d+1 x.b = b return b } |
Si x possède un fils n°2 alors retourner-le. On crée un nouveau noeud isolé b. On incrémente N. La profondeur du noeud est celle de x augmentée de 1. Le fils n°2 de x est b. Retourne le noeud b. |
Ainsi en utilisant le noeud racine R prédéfini, l'instruction x = a(a(b(a(R)))) va retourner le noeud Rabaa en créant les noeud Ra, Rab, Raba, Rabaa s'ils n'existaient pas.
Dans le cas ou G est un tableau de Noeuds de taille variable. Une initialisation va enchainer tous les espaces libres de G.
for _,v
| func a(x *Noeud) *Noeud { | a(x) : Retourne le premier fils de x et le crée s'il n'existre pas. |
| if x.a != nil {return x.a} a := new(Noeud) N+=1 a.d = x.d+1 x.a = a return a } |
Si x possède un fils n°1 alors retourner-le. On crée un nouveau noeud isolé a. On incrémente N. La profondeur du noeud est celle de x augmentée de 1. Le fils n°1 de x est a. Retourne le noeud a. |
| func B(x *Noeud) *Noeud { | b(x) : Retourne le second fils de x et le crée s'il n'existre pas. |
| if x.b == nil {return x.b} b := new(Noeud) N+=1 b.d = x.d+1 x.b = b return b } |
Si x possède un fils n°2 alors retourner-le. On crée un nouveau noeud isolé b. On incrémente N. La profondeur du noeud est celle de x augmentée de 1. Le fils n°2 de x est b. Retourne le noeud b. |