monoïde

L'utilisation de l'IA pour programmer nous libère d'une tache fastidieuse qu'est l'application de la syntaxe de programmation, et nous permet de nous concentrer sur les algorithmes et les structures mises en oeuvre.

Elle permet d'entreprendre facilement des recherches mathématiques empiriques. De telles recherches s'accompagnent de la création de frameworks et de bibliothèques spécialisées, autrement-dit, d'une implémentation de structures et d'algorithmes, dont la pertinence peut égaler voir dépasser les objets mathématiques qu'elles veulent sonder. L'IA change donc d'une certaine façon notre vision des mathématiques, donnant davantage de pertinence aux constructions intermédiaires qu'aux l'objets finaux.

On l'expérimente dans l'étude des monoïdes bis-gènes de façon empirique en utilisant le langage de programmation Python. On représente le monoïde engendré par deux éléments `a,b`, par un graphe orienté où les sommets sont les éléments du monoïde. Chaque sommet possède deux arrètes partantes libéllées `a` et `b`. Le sommet racine est l'élément neutre du monoïde. Et pour chaque sommet `x`, l'arrête libéllée `a` partant de `x` arrive sur le sommet `x"*"a`, et l'arrête libéllée `b` partant de `x` arrive sur le sommet `x"*"b`, où `"*"` est la loi du monoïde.

2) Installation spécifique de python dans un dossier (environnement virtuel)

Créer un dossier Python1 et exécuter la commande : python -m venv env1
Une foix créée. Pour activer l'environnement virtuel : source env1/bin/activate
Pour desactiver l'environnement virtuel : deactivate
Pour installer le module python numpy dans l'environnement virtuel, activez-le et exécuter : pip install numpy

Pour lister les modules installés : pip list.
Pour lancer Python : python

Pour exécuter un script python a.py et ouvrir l'interpéteur qui l'a exécuté : python -i a.py

Pour exécuter le code python (qui contient le bloc if __name__ == "__main__":) :

3) L'arbre du monoïde bis-gènes libre

L'IA progresse par les analogies qu'elle tisse. C'est pourquoi on commence par solliciter ses compètences sur le domaine concerné ce qui nous renseigne sur le langage qu'utilise l'IA :

Puis on fait remarquer une autre analogie où les éléments générateurs correspondent à des voies (des transitions) possibles à partir de chaque élément. Indiquer cette analogie est importante. Elle permet à l'IA de prolonger cette analogie presque naturellement.

A partir d'un élément quelconque `x`, si on empreinte une voix `a`, alors on arrive sur l'élément `xa`, produit de `x` par `a` selon la loi du monoïde. Ainsi la combinaison finie (par l'opération) telle que par exemple `aaba`, désigne un chemin précis partant de `1` pour aboutire à l'élément `aaba`

On reprend la terminologie utilisé par l'IA. On définit la structure de données. C'est une immense liste de cellules, et chaque cellule contient 4 index et 16 flags. On choisit comme index des nombres entiers non-signés tenant sur 4 octets. La cellule occupe donc 18 octets. On utilise ChatGPT pour faire la programmation :

Le monoïde est mémorisé sous forme d'un graphe. Chaque sommet possède deux arêtes partantes libellées `a` et `b`. Le sommet racine est l'élément neutre du monoïde. Et pour chaque sommet `x`, l'arête libellée `a` partant de `x` arrive sur le sommet `x"*"a`, et l'arête libellée `b` partant de `x` arrive sur le sommet `x"*"b`, où `"*"` est la loi du monoïde.

On commence par étape un programme en python qui aura pour but de construire ce graphe en mémoire.

On utilise le module numpy qui permet de manipuler des tableaux de façon efficace. On définit le type cellule, structuré comme suit, et qui doit être de taille minimale :

`{`
    `a " uint"32`      # Noeud fille selon la voie a
    `b " uint"32`      # Noeud fille selon la voie b
    `d " uint"32`      # Profondeur du noeud
    `L " uint"32`      # Pointeur
    `u" uint"16"`     # 16 flags
`}`

On crée un tableau `M` uni-dimensionnel de 100_000 cellules libres initialisées comme suit :

Chaque cellule est désignée par son Indexe dans `M`. La cellule `M[0]` n'est pas utilisée. L'index `0` qui est la valeur minimal représente le rien.

Pour chaque cellule libre, l'attribut `L` contient l'indexe de la cellule libre suivante, et la dernière cellule contient comme attribut `L` la valeur `0` qui représente le rien.

La variable globale `L=1` désigne la première cellule vide du tableau `M`.

On crée le premier noeud qui correspond à l'élément neutre du monoïde en `M[1]`.
La variable `L` est alors modifiée comme suit : `L = M[L]"."L` afin de désigner la première cellule vide dans `M`.

`M[1]"."L= 0 `
`M[1]"."a = 0`
`M[1]"."b = 0`
`M[1]"."u0 = 1` # Marque la cellule comme occupée (c'est un noeud)

Les enfants `M[1]"."a` et `M[1]"."b` n'étant pas encore définit, ils ont la valeur `0`.

Les cellules occupées sont appelées des nœuds, et correspondent au sommet du graphe, et correspondent aux éléments du monoïde.

Parfait, tu as déjà posé les bases très précisément. Voici l’implémentation Python correspondant à cette première étape de la construction du graphe du monoïde bis-gène :

import numpy as np
# Définition du type structuré 'cellule' minimal
cellule_dtype = np.dtype([
    ('a', np.uint32), # Fille selon a
    ('b', np.uint32), # Fille selon b
    ('d', np.uint32), # Profondeur
    ('L', np.uint32), # Pointeur vers cellule libre suivante
    ('u', np.uint16) # Flags (u0 = 1 pour cellule occupée)
])

# Taille maximale du graphe
N = 100_000

# Création du tableau M avec N cellules
M = np.zeros(N, dtype=cellule_dtype)

# Initialisation de la liste chaînée de cellules libres
for i in range(1, N - 1):
    M[i]['L'] = i + 1
M[N - 1]['L'] = 0 # La dernière cellule libre pointe vers rien

# La cellule M[0] n'est jamais utilisée
# L est le pointeur vers la première cellule libre
L = 1

# Création de l'élément neutre en M[1]
e = L # L'ancien pointeur libre devient le neutre
L = M[L]['L'] # Mise à jour de L vers la prochaine cellule libre

M[e]['L'] = 0 # L'élément neutre ne fait plus partie de la liste libre
M[e]['a'] = 0 # Fille a non définie
M[e]['b'] = 0 # Fille b non définie
M[e]['d'] = 0 # Profondeur = 0
M[e]['u'] = 1 # Flag u0 = 1 → cellule occupée

# Vérification : afficher l'état de M[1]
print(f"Neutre (M[1]) : a={M[1]['a']} b={M[1]['b']} d={M[1]['d']} L={M[1]['L']} u={M[1]['u']}")
print(f"Prochaine cellule libre : L={L}")

Résumé :

Le tableau `M` contient 100 000 cellules initialisées comme cellules libres chaînées via `L`.
La cellule `M[1]` est allouée comme élément neutre.
L’attribut `L` pointe maintenant vers la prochaine cellule libre.
La cellule `M[0]` est inutilisée et l’index `0` représente l’absence de cellule (null).

Souhaites-tu que l’on continue avec l’étape suivante, c’est-à-dire l’ajout dynamique de nouveaux nœuds à partir du neutre en suivant les générateurs `a` et `b` ?

Programme la fonctions `"get_u"(x,i)` qui retourne la valeur du `i` ième bit du champ `u` de la cellule `M[x]`

Voici la fonction `"get_u"(x, i)` en Python, qui retourne la valeur du `i`ᵉ bit du champ `u` de la cellule `M[x]` :

def get_u(x, i):
"""Retourne le i-ème bit (0-indexé) du champ 'u' de la cellule M[x]."""
return (M[x]['u'] >> i) & 1

Détails :

Le décalage à droite >> `i` place le bit d’indice `i` en position de poids faible.
Le & `1` isole ce bit.
Les indices commencent à `0` (bit de poids faible), donc `"get_u"(x, 0)` donne `u`₀, `"get_u"(x, 1)` donne `u`₁, etc.

Exemple d’utilisation :

if get_u(1, 0):
print("La cellule M[1] est occupée.")

Souhaites-tu que je code aussi la fonction complémentaire `"set_u"(x, i, "value")` pour modifier un bit ?

Oui

Voici la fonction `"set_u"(x, i, "value")` qui modifie le `i`ᵉ bit du champ `u` de la cellule `M[x]`, selon que `"value"` vaut `0` ou `1` :

def set_u(x, i, value):
    """Modifie le i-ème bit du champ 'u' de la cellule M[x].
    Si value = 1, le bit est mis à 1.
    Si value = 0, le bit est mis à 0.
    """
    if value:
        M[x]['u'] |= (1 << i) # Mettre à 1 le iᵉ bit
    else:
        M[x]['u'] &= ~(1 << i) # Mettre à 0 le iᵉ bit

Exemple d’utilisation :

set_u(1, 0, 1) # Marque la cellule M[1] comme occupée
set_u(1, 3, 0) # Met le bit 3 à zéro dans M[1]['u']

Souhaites-tu une fonction pour basculer (inverser) un bit (toggle_u) aussi ?

Oui

Voici la fonction toggle_u`(x, i)` qui inverse (bascule) le `i`ᵉ bit du champ `u` de la cellule `M[x]` :

def toggle_u(x, i):
"""Inverse le i-ème bit du champ 'u' de la cellule M[x]."""
M[x]['u'] ^= (1 << i)

Exemple d’utilisation :

toggle_u(1, 0) # Si u₀ valait 1, il devient 0, et inversement

Tu as maintenant un trio de fonctions pour manipuler efficacement les flags dans le champ `u` :

get_u`(x, i)`→ lire le bit
set_u`(x, i, "value")` → forcer un bit à 0 ou 1
toggle_u`(x, i)` → inverser un bit

Souhaites-tu maintenant ajouter une fonction pour allouer dynamiquement un nouveau nœud (c’est-à-dire sortir une cellule de la liste libre et l’initialiser) ?

Oui

Voici la fonction alloc() qui alloue dynamiquement un nouveau nœud (cellule) depuis la liste libre, l’initialise, et met à jour la variable globale `L` :

def alloc():
    """Alloue une cellule libre depuis la liste chaînée, l'initialise, et retourne son index.
    Retourne 0 si plus aucune cellule n'est disponible.
    """
    global L
    if L == 0:
        return 0 # Plus de cellules disponibles

    x = L # Index de la cellule à allouer
    L = M[x]['L'] # Mise à jour de L vers la prochaine cellule libre

# Initialisation de la cellule allouée
    M[x]['a'] = 0
    M[x]['b'] = 0
    M[x]['d'] = 0
    M[x]['L'] = 0 # N'est plus dans la liste libre
    M[x]['u'] = 0
    set_u(x, 0, 1) # Marquer la cellule comme occupée (u₀ = 1)

    return x

Exemple d’utilisation :

n = alloc()
if n != 0:
print(f"Nouvelle cellule allouée à l'index {n}")
else:
print("Plus de cellules disponibles")

Résumé des effets :

L’ancienne cellule libre `L` devient un nœud (occupée).
Le pointeur `L` est avancé.
Tous les champs de la cellule sont remis à zéro, sauf `u`₀ mis à 1.

Souhaites-tu que je code aussi la fonction free`(x)` pour libérer une cellule (la remettre dans la liste libre) ?

Oui

Voici la fonction free`(x)` qui libère une cellule occupée (nœud) et la remet en tête de la liste chaînée des cellules libres :

def free(x):
    """Libère la cellule M[x] et la remet dans la liste des cellules libres."""
    global L

    # Nettoyage des champs
    M[x]['a'] = 0
    M[x]['b'] = 0
    M[x]['d'] = 0
    M[x]['u'] = 0 # Tous les flags remis à zéro

    # Réinsertion dans la liste libre
    M[x]['L'] = L
    L = x

Exemple d’utilisation :

free(42) # Libère la cellule M[42]

Résumé :

Les pointeurs, profondeur et flags sont remis à zéro.
La cellule est réinsérée en tête de la liste libre.
La variable `L` est mise à jour.

Souhaites-tu maintenant une fonction pour créer un fils `x"*"a` ou `x"*"b` depuis un nœud existant `x` si ce fils n’existe pas encore ?

La génération de code par petites étapes, permet à l'IA de générer une description détaillée qui peut être enrichie d'analogies. Ainsi nous l'encourageons à causer. Cela nous permet de désigner nos souhaits de développement en utilisant les bons mots, ceux utilisés par l'IA, pour établir la correspondance et désigner les bonnes analogies.

On crée une fonction pour se déplacer dans le graphe à partir d'un noeud `x`, et en choisissant une voie `a` ou `b`

On crée une fonction pour se déplacer dans le graphe à partir d'un noeud `x`, et en choisissant une voie `a` ou `b`, et si le noeud n'existe pas on le crée.

Voici la fonction move(`x`, label) qui permet de se déplacer dans le graphe à partir d’un nœud `x` selon la voie 'a' ou 'b', et de créer dynamiquement le nœud destination si nécessaire :

def move(x, label):
    """
    Depuis le nœud M[x], suit l’arête 'a' ou 'b'.
    Si le nœud destination n’existe pas encore, il est créé.
    Retourne l’index du nœud destination.
    """
if label not in ('a', 'b'):
raise ValueError("label doit être 'a' ou 'b'")

dest = M[x][label]

    if dest == 0:
        # Le nœud fils n'existe pas encore → on l'alloue
        y = alloc()
        if y == 0:
            raise RuntimeError("Plus de cellules libres disponibles")

        M[x][label] = y
        M[y]['d'] = M[x]['d'] + 1 # Propriété utile : profondeur = +1
        return y
    else:
        # Le nœud existe déjà
        return dest

Exemple d’utilisation :

x = 1 # Neutre
y = move(x, 'a') # Crée M[1].a si nécessaire et retourne son index
z = move(y, 'b') # Crée M[y].b si nécessaire et retourne son index

Comportement :

Si `M[x].a` ou `M[x].b` est `0`, un nouveau nœud est alloué et relié.
La profondeur est automatiquement calculée (utile pour les parcours).
L’opération est déterministe : on construit le monoïde au fur et à mesure.

Souhaites-tu maintenant une fonction pour construire automatiquement tous les éléments du monoïde jusqu’à une certaine profondeur ?

Crée une fonction générique qui prend un nœud `x` de départ et un mot complet (ex: `abaab`) et construit le chemin correspondant dans le graphe partant du nœud `x`

Voici la fonction build_path(`x`, mot) qui, à partir d’un nœud de départ `x` et d’un mot sur les lettres 'a' et 'b', construit (si nécessaire) et retourne l’index du nœud d’arrivée après avoir suivi ce mot dans le graphe :

def build_path(x, word):
    """
    Construit (si nécessaire) et suit un chemin depuis M[x] selon le mot donné.
    Le mot est une chaîne comme 'abaab', chaque lettre étant 'a' ou 'b'.
    Retourne l’index du nœud d’arrivée.
    """
    for c in word:
        if c not in ('a', 'b'):
            raise ValueError("Le mot ne doit contenir que les lettres 'a' et 'b'")
        x = move(x, c)
    return x

Exemple d’utilisation :

# Depuis le neutre M[1], construire le chemin correspondant à 'abaab'
final_node = build_path(1, 'abaab')
print(f"Le nœud d’arrivée pour 'abaab' est M[{final_node}]")

Ce que fait la fonction :

Elle enchaîne les déplacements dans le graphe à partir du nœud `x`.
Elle crée dynamiquement les nœuds manquants sur le chemin.
Elle renvoie l’index du nœud final correspondant à l’élément du monoïde.

Souhaites-tu ajouter une fonction inverse, pour retrouver le mot menant à un nœud donné à partir du neutre (si le graphe est construit jusque-là) ?

Construction de monoïdes bigènes

1) Introduction

2) Installation spécifique de python dans un dossier (environnement virtuel)

3) L'arbre du monoïde bis-gènes libre

Résumé :

Détails :

Exemple d’utilisation :

Exemple d’utilisation :

Exemple d’utilisation :

Résumé des effets :

Exemple d’utilisation :

Résumé :

Exemple d’utilisation :

Comportement :

Exemple d’utilisation :

Ce que fait la fonction :