Un semi-groupe est un ensemble muni d'une loi de composition associative, appelé produit, que l'on note par absence de symbole, en juxtaposant les arguments, tel que `ab` pour le produit de `a` par `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ée à 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 est 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 l'application suivante et qui est une translation gauche :
`(x"↦"sx)`
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, en ajoutant cet élément neutre si nécessaire, 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. C'est à dire que le second rôle identifie l'élément. Autrement dit, l'application `s |-> (x"↦"sx)` 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 seul second rôle, leur rôle d'application qui est une translation gauche. Et l'élément neutre correspond à l'application identité `(x"↦"x)` qu'il est toujours possible d'ajouter pour former un monoide.
Chaque élément `s "∈" S` est identifié à l'application `(x"↦"sx)` qui est une translation gauche. Et `S` est identifié à une sous-structure de semi-groupe incluse dans la structure de semi-groupe qu'est l'ensemble des applications de `S` vers `S` muni de la loi de composition. On note l'inclusion de structure à l'aide du symbole `"ᑖ"` :
`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 et qui est interne. On note `frS_G` le groupe des bijections de `G` sur `G`.
`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 et qui n'engendre aucun élément autre que lui-même. Dans ce cas, on peut le représenter par 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 éléments produits `xa` et `xb` qui sont appelés les fils 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 éléments produits `xa` et `xb`.
Un produit quelconque de `a` et de `b` constitue un cheminement tel que par exemple `ab aab b a` et qui est appelé aussi un mot de `{a,b}"*"`. 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`
`b b b = 1`
On déclare un tel monoïde en présentant ses générateurs et ses équations sous forme d'un quotient :
`("<"a,b">") / ({aa"="1, b b b"="1, ab"="ba})`
Où sous forme condensée :
`"<" a, b | aa"="1, b b b"="1, ab"="ba ">"`
Chaque équation est une égalité entre deux cheminements (c-à-d entre deux mots) et va fusionner des noeuds de cet arbre et le transformer en un graphe orienté binaire, où chaque noeud possède deux arêtes sortantes labélisée `a` et `b`.
Le monoïde bigène est ainsi 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 nécessairement à 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, plus simple à maitriser et qui est adapté aux développements rapides et peu verbeux.
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'à `2^32` cellules et on s'en tiendra là. L'index dans ce tableau peut donc tenir sur un entier de 4 octets.
Le graphe est ainsi mémorisé dans un tableau dynamique G. Notez que tout l'espace mémoire de ce tableau n'est pas réservé, il s'agrandira progressivement par morceaux au cours de son utilisation. De telle sorte que l'on peut en définir plusieurs utilisant potentiellement la même mémoire.
La gestion de la mémoire en Golang est plus simple et souple car une grande partie de sa gestion est assurée par le système. Il n'est pas nécessaire de s'occuper de la libération de la mémoire, un ramasse miette est mis en oeuvre par le système pour libérer toutes les mémoires rendues inaccessibles.
Néanmoins les pointeurs sont trops gourments en mémoire. Ils occupent 8 octets, alors que nos indexes n'occupent que 4 octets. C'est pourquoi nous n'utiliserons pas les pointeurs mais nos indexes en gérant nous-même la mémoire de ces tableaux potentiellement immenses.
Pour éviter le débordement de la pile d'appel, qui est limité à 1 Go, on ne programmera pas de fonctions récurcives.
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.
On définit un immense tableau G de cellules qui contiendra les noeuds du graphe. Golang ne réserve pas la mémoire du tableaux, elle ne reserve que des blocs mémoires utilisée en écriture. Et on pourra donc définir plusieurs tels graphes.
Un tel tableau est suceptible d'occuper toute la mémoire disponnible. Ayant installé deux barrettes mémoires de 32 Go, et laissant 8 Go de mémoire vives pour le système, je définis la valeur SizeRAM = 56 000 000 000. Ce qui me permettra à partir de la taille d'une cellule, de calculer la taille maximale Nmax en nombre de cellules que peut enmagasiner un tableau G.
| var cell Cell2 Nmax = uint32(memory.FreeMemory() / uint64(unsafe.Sizeof(cell))) |
unsafe.Sizeof(cell) retourne la taille d'une cellule. memory.FreeMemory() retourne la taille de la mémoire libre. Il est commode d'utiliser un index tenant sur `4` octets permettant de compter `2^32` cellules. L'index sera donc de type uint32. La taille des cellules qui en Golang doit être un multiple de 4 octets, peut atteindre sans nous imposer de nouvelles contraintes, la valeur de `3*4` octets. Mais pour pouvoir implémenter nos algorithmes assez simplement on retiendra une taille de cellule de `4*4` octets ou davanage de `5*4` octets. Autrement-dit, la cellule comprendra `4` attributs de type uint32 que l'on nomme `{a,b,p,L}` ou bien comprendra `5` attributs de type uint32 que l'on nomme `{a,b,p,L,M}`
La strutcture d'un noeud comprend deux attributs a et b désignant ses fils, et elle possède deux autres attributs, l'attribut `p` qui contiendra les flags et la profondeur, et l'attibut `L` capable de désigner une autre cellule, puis dans le cas large, l'attibut `M` capable de désigner une autre cellule.
Nous désignons les cellules par leur index, un entier compris entre `0` et `2^32-1`, les index sont de type uint32.
Les expressions suivantes sont équivalentes :
La cellule d'indexe `x` dans le graphe `G`
La cellule n°`x` dans le graphe `G`
La cellule `x` dans le graphe `G`
La cellule `G[x]`
Et si la cellule correspond à un noeud, un sommet du graphe, les expressions suivantes sont équivalentes :
Le noeud ou l'élément ou le sommet d'indexe `x` dans le graphe `G`
Le noeud ou l'élément ou le sommet n°`x` dans le graphe `G`
Le noeud ou l'élément ou le sommet `x` dans le graphe `G`
Le noeud ou l'élément ou le sommet `G[x]`
On dira dans les commentaires, que l'indexe est de type →Noeud ou de type →Cellule.
Le graphe est le plus souvent incomplet. Les noeuds inconnus sont désignés par l'index 0 qui joue le rôle du nil. La première cellule G[0] n'est donc pas utilisé.
Le noeud racine qui correspond à l'élément neutre du monoïde, est désigné par l'index R qui est un attribut du graphe. Ainsi l'élément neutre du monoïde est le noeud G[R].
La cellule est soit un noeud ou soit une cellule vide. C'est un objet à deux faces. La première face est un noeud du graphe. La seconde face est une cellule libre. 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. Il existe toujours une dernière cellule vide après laquelle toutes les cellules sont vides. C'est la borne, elle est caractérisée par son attribut `a` qui vaut zéro.
| type Cell2 struct { a uint32 b uint32 p uint32 L uint32 } |
La cellule n'est pas vide
a : →Noeud fils n°1.b : →Noeud fils n°2. p : Profondeur et flags. L : →Noeud. |
La cellule est vide
a : Non utiliséb : Non utilisé p : Non utilisé L : {→Cellule libre suivante, `0`: Borne} |
La structure de graphe comprend sept attributs que sont : le tableau G mémorisant les sommets du graphe, le nombre maximum de cellules Nmax, l'indexe de la racine du graphe R, le nombre N de noeuds connus, l'index de la première cellule libre L, la liste des équations E. On adopte comme stratégie de gestion de mémoire d'utiliser toujours les cellules d'index les plus petits.
| type Graphe2 struct { |
Graphe orienté binaire |
| G []Cell2 Nmax uint32 R uint32 N uint32 L uint32 E []Eq |
G : Tableau de cellules hébergeant le graphe. Nmax : Nombre maximum de cellules. R : →Noeud racine du graphe. N : Nombre de noeuds connues du graphe. L : →Première 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. |
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 de tels graphes. Le premier noeud à construire est le noeud racine qu'est l'élément neutre du monoïde, puis ses fils, puis les fils de ses fils, etc., degrés par degrés. On utilise l'attribut p pour mémoriser la profondeur de l'élément. Le graphe est un immense tableau pouvant contenir jusqu'à 3 milliards de cellules. La mémoire libre dans ce tableau sera gérer par nous et nécessite d'utiliser des attributs supplémentaires, 4 bits de données appelés flags. Or, l'ajout ne fusse que d'un octet dans la structure Cell va augmenter sa taille de 4 octets. Pour éviter ce gaspillage de mémoire, on limite la profondeur à `2^28` soit 268 millions de cellules, et donc les 4 derniers bits de point fort de la variable p peuvent être utilisé à autre chose et donc peuvent mémoriser 4 flags notés : p0, p1, p2, p3.
La limitation de la profondeur est pertinente si on n'utilise pas d'algorithme de parcourt du graphe en profondeur d'abord. Et c'est bien le cas, car nous évitons le recours intensifà la pile d'appel et aux fonctions récurcives. Le parcours du graphe se fera en largeur d'abord.
La cellule vide possède la même structure mais est 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 dernier bit, le flag p3, dont la signification est commune au deux faces, qui détermine si c'est un noeud ou une cellule vide. Lorsque le flag p3 est égale à 1, alors cela indique que la cellule n'est pas vide et qu'elle constitue un noeud, un sommet du graphe, un élément du monoïde.
Les opérations de bits à bits, de shift et de masquage, permettent de lire et de modifier les 4 bits de poid fort de p dénommés: p0, p1, p2, p3, et permettent de lire et de modifier les 28 bits de poids faible de p dénommé la profondeur. Nous utilisons 5 masques :
const ma0 = uint32(1 << 28)
const ma1 = uint32(1 << 29)
const ma2 = uint32(1 << 30)
const ma3 = uint32(1 << 31)
const maX = ma0 + ma1 + ma2 + ma3
Les opérations bit-à-bits sur la variable p :
Retourne la profondeur. p &^ maX Teste si le bit n°3 est à 1. p & ma3 == 1 Teste si le bit n°3 est à 0. p & ma3 == 0 Fixe la profondeur à q. p = p&maX + q Met le bit n°3 à 1. p = p | ma3 Met le bit n°3 à 0. p = p &^ ma3 Inverse le bit n°3. p = p ^ ma3
On peut mettre ces opérations sous forme de fonction inligne mais cela n'apporte pas vraiment de notation plus simple.
Retourne la profondeur. Teste si le bit n°3 est à 1. Fixe la profondeur à q. Met le bit n°3 à 1. Met le bit n°3 à 0. Inverse le bit n°3.
Pour lire et modifier l'attribut profondeur :
func getP(p uint32) uint32 { return p &^maX }
func putP(p *uint32, q uint32) { *p = *p&maX + q }
Pour lire et modifier les attributs p0, p1, p2, p3 :
func get0(p uint32) bool { return p&ma0 == 1 }
func get1(p uint32) bool { return p&ma1 == 1 }
func get2(p uint32) bool { return p&ma2 == 1 }
func get3(p uint32) bool { return p&ma3 == 1 }
func in0(p *uint32) { *p = *p | ma0 }
func in1(p *uint32) { *p = *p | ma1 }
func in2(p *uint32) { *p = *p | ma2 }
func in3(p *uint32) { *p = *p | ma3 }
func off0(p *uint32) { *p = *p &^ ma0 }
func off1(p *uint32) { *p = *p &^ ma1 }
func off2(p *uint32) { *p = *p &^ ma2 }
func off3(p *uint32) { *p = *p &^ ma3 }
func inv0(p *uint32) { *p = *p ^ ma0 }
func inv1(p *uint32) { *p = *p ^ ma1 }
func inv2(p *uint32) { *p = *p ^ ma2 }
func inv3(p *uint32) { *p = *p ^ ma3 }
Le compilateur compile ces fonctions inlignes, remplaçant directement l'appel de la fonction par le corps de la fonction.
Par exemple, étant donné l'attribut p d'une cellule :
En Go, l'instruction make dispose un tableau initialisé à zéro. Mais il ne réserve pas la mémoire tant que l'on n'accède pas en écriture. Et il reserve la mémoire du tableau partiellement par morceau. Il nous faut un outils permettant de calculer la mémoire total de l'ordinateur ainsi que la mémoire libre restante. On ajoute au projet le package "github.com/pbnjay/memory " qui contient les deux fonctions TotalMemory() qui retourne la quantité de mémoire totale, et FreeMemory() qui retroune la quantité de mémoire libre.
Vous faites dans LiteIDE, new | "Go1 package project" que vous nommer memory. Vous téléchargez sur le site https://github.com/pbnjay/memory, Bouton Code en vert | Download ZIP. Vous décompressez ce dossier memory-master que vous renommer memory. Et vous recopier tous ce qu'il y a à l'intértieur pour le coller en remplaçant tous ce qu'il y a dans le dossier du projet de package nouvellement créé /home/dmabboux/go/src/memory. Ainsi vous avez importé un package en local. En allant sur la fenêtre "7.Signets", vous pouvez développer l'arborescence /home/dmabboux/go | pkg | memory. Puis vous pouvez fermer le répertoire memory.
Il faudra insérer dans le code l'instruction suivante import ( "memory" ) pour pouvoir utiliser ces fonctions memory.TotalMemory() et memory.FreeMemory()
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 les cellules vides pour toujours garder un moyen simple pour accéder à la cellule libérée la plus anciennement. La variable globale `L` désigne la plus ancienne cellule libre. Et dans une cellule libre, l'attribut `L` désigne la cellule libérée la plus ancienne après celle-ci, ou bien vaut zéro pour indiquer que tous les cellules suivantes sont libres.
Le flag p3 précise si la cellule est un noeud. Il vaut 1 si c'est un noeud, zéro sinon. L'initialisation du graphe consiste à créer un tableau de cellules en nombre maximum avec un noeud racine.
| func (A Graphe2) new() { | Méthode créant un graphe. |
| var cell Cell2 A.Nmax = uint32(memory.FreeMemory() / uint64(unsafe.Sizeof(cell))) A.G = make([]Cell2, Nmax) A.R = 1 in3(&A.G[1].p) A.N = 1 A.L = 2 A.E = nil } |
A.Nmax : le nombre maximal de cellules. Crée un tableau A.G de taille potentiel de A.Nmax cellules. La racine est 1. Met le flag p3 à 1. "Cette cellule est un noeud". Le nombre de noeud est 1. La première cellule libre est 2. La liste des équations est vide. |
---- 25 décembre 2023 ----
| func newNoeud() uint32 { | x=newNoeud() : Créer un nouveau noeud et le retourne. |
|
Le noeud sera la première cellule vide
|
La destruction d'un noeud du graphe G se fait en appelant la fonction deleteNoeud().
| func newNoeud() uint32 { | newNoeud(x) : Créer un nouveau noeud et le retourne. |
x:=L
|
import (
"errors"
"fmt"
"syscall"
"time"
"unsafe"
)
func totalMemory() uint64 {
in := &syscall.Sysinfo_t{}
err := syscall.Sysinfo(in)
if err != nil {
return 0
}
return uint64(in.Totalram) * uint64(in.Unit)
}
func freeMemory() uint64 {
in := &syscall.Sysinfo_t{}
err := syscall.Sysinfo(in)
if err != nil {
return 0
}
return uint64(in.Freeram) * uint64(in.Unit)
}
func main() {
fmt.Println("Hello World!")
var A Graphe2
A.Init()
fmt.Println(A.G[1].p, " ", 1<<(31))
fmt.Println(A.G[1].a)
fmt.Println(A.G[1].b)
fmt.Println(A.G[1].L)
A.G[2000000000].a = 521
A.G[1000000000].a = 484
s := uint32(0)
for i := uint32(0); i < Nmax; i++ {
s = s + A.G[i].a
}
// fmt.Println(A.G[2000000000].a)
fmt.Println("s=", s)
fmt.Println(freeMemory())
fmt.Println(totalMemory())
time.Sleep(8 * time.Second)
}
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.
Voir : Mathématique/Monoide.html
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.
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. |