Brevet FR2829598A1 — publié le 20030314

Descriptif /-') Avant-propos, explicatif. Le brevet porte sur une l'architecture d'éléments inscrit dans une mémoire informatique de type RAM (Random access Memory), qui rend possible un dénombrement en temps réel Au sens mathématique : 1 - Soit E un ensemble non vide fini, soit f une application qui pour tout i de E donne un autre ensemble (Bi). Avec Card Bi Soit g une application qui pour tout x de Bi donne des sous-ensembles Dx. Avec Card Dx 2-Soit U un ensemble non vide fini, soit g une application qui pour tout j de U donne un autre ensemble (Cj). Avec Card Cj Soit h une application qui pour tout y de Cj donne des sous-ensembles Fx. Avec Card Xx L'objectif est de déterminer, dans les deux cas, l'occurrence des sous-ensembles de la famille Dx et Fx en temps réel quand Card (f (i)) ou Card (h (x)) ne sont pas connues, et peuvent tendrent vers les limites informatiques habituelles 2exp32 ou 10exp31 (occurrences), sans matériel ou logiciel spécifique, et sans être dépendant au niveau temps des cardinalités. Au sens Littéraire : J'entends par élément une suite de, valeurs distinctes ou non, entre elles ex : A, B, C, D A, A, C, B suite de 4 lettres de l'alphabet ou par exemple 1,3, 5,7, l1. Ce qui est équivalent au sens informatique. Pour poursuivre avec l'exemple de l'alphabet, un calcul mathématique nous donne le nombre des éléments possibles de 4 lettres soit 14950 éléments ou combinaisons. Notre objectif est de déterminer le nombre d'occurrences, en temps réel, de tous les sous-éléments d'une instance donnée parmi l'ensemble des éléments fournis et chargé en mémoire. Ex, nombre d'occurrences pour AB, pour AD, pour ABD.... (ABCD) L'ensemble des éléments fournis n'est pas numériquement déterminé à l'avance. Si chaque lettre est codée sur un octet, la mémoire requise pour enregistrer 14950 éléments est de 14950*4 = 59800 octets. Mais nous pouvons avoir X fois un même élément. Ceci sans tenir compte d'aucun calcul. Un nombre non déterminé d'éléments nous donne une mémoire non déterminée sans une organisation particulière des données. Une simple lecture mémoire des combinaisons est donc exclue. Il existe aux échecs une tournure de jeu qui se nomme le Gambit. Il s'agit de sacrifier une pièce pour obtenir des avantages par la suite. Pour arriver à obtenir une mémoire fixe, quel que soit le nombre d'éléments fournis et calculer les occurrences en temps réel, nous allons utiliser un principe philosophique similaire. 1 Eléments Distinct entre eux : Descriptif détaillé de l'architecture On considèrera chaque sous-ensemble individuellement. A, puis B, puis C, puis D, et dans un premier temps avec des éléments distinct entre eux. Un octet est suffisant pour le codage de chaque l'individu. A chaque sous-ensemble est associé son occurrence. L'occurrence, codée sur 4 octets nous donne déjà 2exp32 possibilités. Chaque élément (ou combinaison ABCD) pourra donc être considéré grâce à ces 4 octets plus de 4 milliards de fois. Si cela n'était pas suffisant un codage décimal permet d'aller, sans modifications de fond, jusqu'à 10exp30, on peut parler d'infini au sens informatique. Il faut ensuite lier ses sous-ensembles entre eux. Et les organiser. Le lien nécessite deux adresses actuellement codées sur les ordinateurs courant sur 4 octets. Chaque sous-ensemble utilise individuellement dans cet exemple 1 +4+2*4 = 1 3 octets. Nous appellerons NODE chaque entité composée de la sorte. Reste à les organier. Un arbre classique binaire ne donnera pas de résultat. Il faut une autre méthode. L'apparence visuelle rappel celle des fractals. Pour bien comprendre vous devez considérer le schéma par ligne et colonne L'architecture de la mémoire pour l'élément ABCD sera la suivante : 4 ss- { C (). t'ü. c. JÚ La redondance et ici surprenante, c'est notre gambit , l'occurrence de chaque node est ici de 1. On remarque que tous les sous-éléments figure dans cette organisation. Si l'on part d'en haut à gauche et que l'on recherche l'occurrence de BCD, en parcourant de gauche à droite on trouve la première position B, puis en parcourant une fois de haut en bas on trouve C, et ainsi de suite, en troisième position en parcourant une fois de plus de haut en bas D. Nous venons de trouver l'occurrence de BCD en 1 parcours d'arbre. Admettons que l'élément suivant soit identique au premier, Il n'y aura aucune création de node, mais l'occurrence de chaque node passe à 2. (I) La recherche de BCD, de la même manière que précédemment, donnera le résultat 2 avec le même parcours et donc sans augmentation de temps de recherche. Ajoutons l'élément suivant ABCE. c Ajout de L'élément FGHI L'arbre crée s'étend dans sa partie droite. Le maximum de node du premier niveau (Première ligne sera égale au nombre de sous-ensembles unitaires distincts N). Le nombre maximum de node de la deuxième ligne du premier node de la première ligne sera égale à N- 1 Dans l'absolu, lorsqu'un exemplaire de chaque élément sera chargé en mémoire, il n'y aura par la suite pour chaque ajout de nouvel élément, qu'une modification de l'occurrence. La mémoire nécessaire dans ce cas de figure peut être déterminée par simulation. Elle est de 17901 * 13 pour notre exemple. 1 Eléments avec redondances. Un nouveau problème pose avec l'utilisation de l'organisation précédente, pour les éléments comprenant un sous-ensemble identique entre eux. L' (''ccture de base ne change pas, mais il faut ajouter une troisième adresse, pour être informatiquement él, t, ou un champ supplémentaire. Une architecture en trois dimensions sera retenue. Il faut ajouter au parcours la recherche de la position, et ne pas oublier que la recherche est ordonnée AB # BA # .. AB #. AB. (Ou le point représente une lettre). On notera que le nombre d'éléments est maintenant de 456976 (26), soit environ 30 fois le nombre d'éléments sans redondance, et que le nombre de node utiles sera multiplié par environ 10. L'architecture pour l'élément AABC (C"1 Il í'1 ' i y t 'L'aiout de l'élément BACA nous doti'i'P architecture suivante : /J. M 191 Il 4 6 Les applications possibles sont considc j' : cs. Peut être le Génome sous réserve d'information supplémentaire, Recherches contextuelle sur de très go, \'s volumes, tout ce qui nécessite un dénombrement sur de grand volume de données, l'automobile, l'aéronat L'intérêt nous le rappelons est la rapi, l, la non-dépendance du volume de mémoire nécessaire et du temps par rapport au volume d'éléments à traiter. Un applicatiffonctionnel de démons, ;'11 à été fourni à la société Française des Jeux pour le calcul du nombre de combinaisons gagnantes. Revendications Procédé générique d'architecture d'éléments informatiques en mémoire de type (RAM) - 1 Permet le dénombrement informatique en temps réel* de l'occurrence d'un groupe et de ses sous-groupes, parmi un ensemble défini de groupes et sous-groupes redondant dont le nombre d'occurrences n'est pas défini. (On entend par groupe, tout ensembles définissables) - 2 Le temps de recherche des occurrences n'est pas dépendant du volume à traiter - 3 Le volume (en octet) de mémoire requise n'est pas dépendant du nombre d'occurrences au sein de l'ensemble défini. - 4 La mémoire requise (en octet) est quantifiable. * Matériellement et logicièlement dépendant, de l'ordre de 1/100 de sec sur un matériel grand publique actuel et un logiciel correctement conçu.