Supposons que j'attribue à chaque élément d'un ensemble un nombre premier. En informatique j'aurais pour chaque clef qui identifie une ligne de table SQL un nombre premier unique attribué.
Maintenant pour identifier le contenu de l'ensemble ou de la table je créer un nombre qui est le produit de tout les nombre premiers attribués à chaque éléments de cet ensemble. Ce produit est attribué à l'ensemble et contient la liste des ces élément: sa décomposition en nombre premiers.
Si j'ai deux ensembles identifiés par un produit de nombre premiers:
- je peux trouver l'intersection de cet ensemble en calculant le PGCD de ces deux nombres.
- je peux trouver facilement un nombre identifiant l'union des ces deux ensembles multipliant ces deux nombres.
- il faut que j'étudie les autres opérations.
Bien sur en cas de gros ensemble les nombres identifiant chaque ensemble seront très grand. Je n'ai pas fait d'étude de faisabilité pour l'instant.
Donc il m'est difficile d'évaluer l'utilité pratique d'une telle méthode.
Elle pourrait quand même être utile d'un point de vue théorique.
En espérant que ce poste aura des répercussions utiles ........ si cette méthode n'existe pas déjà.
Cette méthode pourrait être très utile dans le cas ou l'on enchaine des opérations sur les ensemble sans avoir immédiatement besoin d'en connaitre le résultat: il faut en effet faire une décomposition en nombre premier du nombre résultat des opérations pour connaitre le contenu de l'ensemble résultat.
Remarquez que avec les capacités mémoire que l'on a aujourd'hui on pourrait peut-être utiliser si le nombre de nombres premier nécessaires n'est pas trop grand une liste comportant pour chaque nombre sa décomposition en nombre premiers.
Il est même possible que de nouvelles méthode puissent être utilisée pour analyser des expression logiques complexes en attribuant à chaque proposition P un nombre premier p:
A=P1 ou (P2 et P3) <==> a=p1 * (pgcd(p2,p3)
<==> Si A est vide (a=1) alors A est toujours fausse sinon A est vraie.
?????? juste un premier jet.
Supposon que pour ajouter un élément à un ensemble je multiplie le nombre premier qui caractérise l'ensemble par le nombre premier qui caractérise l'élément sans contrôler si cet élément s'y trouve déjà: je vais me trouver avec nombre comportant des facteur à une puissance supérieur à un.
Exemple: 3^2,5,7,23.
Comment puis-je controller l'égalité de deux ensembles dans ce cas?
j'ai construit un algorithme pour cela (qui existe peut-être déjà!) dont j'expose le principe:
je détermine le PGCD des deux nombre caractérisant les ensembles:
A : 3^2 * 5 * 11^3 B:3^3 * 5 * 11^2
P0 = PGCD(A,B) = 3^2 * 11^2
j'extrait les facteur dans A et B qui ne sont pas dans le PGCD
A1= A/P0 = 5 * 11 et B1 = B/P0 = 3 * 5
je calcule le PGCD A1 et P0 puis le PGCD de B1,P0
PA1 = PGCD(A1, P0) = 11 et PB1= PGCD(B1,P0) = 3
j'extrait dans A1 et B1 les facteurs qui ne sont pas dans le PGCD de A et B:
A2 = A1/PA1 = 5 et B2= B1/PB1= 5
je calcule le PGCD de A2 et P0 puis de B2 et P0
PA2= PGCD(A2,P0) = 5 et PB2= PGCD(B2,P0) = 5
j'extrait dans A2 et B2 les facteurs qui ne sont pas dans le PGCD de A et B:
A3 = A2 /PA2 = 1 et B3 = B2/PA2 =1
Il n'y a pas dans A3 et B3 de facteur qui ne soient pas dans le PGCD de A et B
Les deux étant = 1 à un cela veut dire que A et B sont basés sur la même liste de nombre premiers.
A = P1^m * P2^n * ......* Pk^q et B = P1^r * P2^s * ......* Pk^v avec Pi nombre premier quelconque.
Les ensembles sont donc égaux .
Si a un moment les PGCD PXn=PGCD(PXn-1, P0) est égal à un pour A ou B cela veut dire qu'il existe un facteur premier non commun entre A et B et que les ensembles sont différents.
Je présente une ébauche non testée de cet algorithme en python:
#! /usr/bin/python
# -*- coding: utf-8 -*-
#--------------------------------------------------
'''
verfify if two number are based on the same set of primes
exemple a=3*3*3*2*2 and b=3*3*2*2*2*2 are besed on the same primes
peut être utilisé dans le cadre
'''
def gcd(a,b):
"""
The Euclidean Algorithm
"""
a = abs(a)
b = abs(b)
while a:
a, b = b%a, a
return b
def sameclasse(a,b):
"""
are a and based on the same set of primes
"""
P=gcd(a,b)
a1=a/P
b1=b/P
if a1 == 1 and b1 == 1:
return True
return sameclasse2(a1,b1,P)
def sameclasse2(a,b,P):
Pa=gcd(a,P)
Pb=gcd(b,P)
a1=a/Pa
b1=b/Pb
if a1 == 1 and b1 == 1:
return True
if gcd(a1,P) == 1:
return False
if gcd(b1,P) == 1:
return False
return sameclasse2(a1,b1,P)
if __name__ == "__main__":
#print (gcd(3*3*3*3*2*2,3*3*2*2*2*2))
print(sameclasse(2*2*2*3*3*5*7,2*2*3*5))
Et peut être une petite bibliothèque python avec l'outil d'opération sur les ensembles avec des nombre premiers
Aucun commentaire:
Enregistrer un commentaire