Boinc - Equipe de la Science

Objectif :

Le but du projet est de trouver tous les systèmes de numération binaire généralisés jusqu’à la dimension 11. Au-dessous nous donnons une description courte du concept de système de numération et mentionnons quelques applications possibles.

Intro :

Soit n est un nombre entier plus grand que 1 Quand nous parlons des systèmes de numération dans le sens original, nous utilisons le fait que chaque nombre naturel z peut être écrit de façon unique sous la forme finie :

On dit que n est la base du système de numération, et les sont appelés les chiffres.

Si n = 2 alors nous parlons de système numérique binaire. Ces systèmes sont trop restreints pour représenter des nombres négatifs alors nous avons besoin d’un signe. Si nous permettons à la base d’être un entier négatif, une représentation de tous les entiers devient possible. Tel par exemple si nous utilisons la base -2, chaque entier a la forme :

Cela peut être généralisé pour les entiers algébriques d’une extension finie qui sont du domaine des nombres rationnels. Un simple exemple : tous les entiers Gaussiens (les nombres complexes de la forme x+yi, où x,y sont entiers) peuvent être écrit de façon unique dans la base (-1+i) comme suit :

(En)Utilisant l’algèbre linaire nous pouvons définir des systèmes de numération d’une façon plus générale encore. La base est maintenant une matrice et les chiffres sont des vecteurs. Nous pouvons reformuler l’exemple précédent. Chaque vecteur bidimensionnel a une représentation…

ou

et

Nous parlons d’un système binaire si le déterminant de M est ± 2. Dans ce cas il y a seulement 2 chiffres, 1 d’entre eux étant l’origine. Cela signifie que si nous avons un système de numération alors tous les vecteurs d’entier peuvent être représentés comme une série finie de 0 et de 1.

Toute matrice M ne peut être une base de système de numérations. Jusqu’à présent on n’a donné aucune caractérisation des bonnes matrices. Il y a des conditions suffisantes et d’autres nécessaires mais l’espace entre eux est trop grand. Il n’y a aucune méthode efficace connue pour traiter le matrice qui remplissent les conditions nécessaires mais échouent aux conditions suffisantes. Une chose à noter est que si nous fixons le déterminant et la dimension alors en général il y a seulement un nombre fini de matrices possibles.

Résultats attendus :

Le programme vise à trouver beaucoup de systèmes de numération binaire généralisés. Une recherche étendue est exécutée dans l’ensemble fini de matrices de la taille donnée remplissant quelques conditions nécessaires. La difficulté est que la taille de cet ensemble fini est une fonction exponentielle de la dimension. Il semble maintenant possible d’attaquer le cas des matrices 11*11. Pour vérifier encore d’autres conditions nécessaires le programme exécute beaucoup d’opérations à virgule flottante. Ainsi, beaucoup de temps- CPU est nécessaire. Heureusement, le parallelisation est possible et nous pouvons bénéficier de fonctionner sur plusieurs machines.

Le programme produit une liste de matrices (étant plus précis polynômes caractéristiques) qui sont susceptibles déjà d’être des bases de système de numération. Cette liste est traitée par un autre programme (qui n’a pas besoin tellement d’unité centrale de traitement). Le résultat final est alors liste (complète) de systèmes de numération binaire dans une dimension fixe.

Ensuite nous exécutons l’analyse théorique de l’information. Les systèmes de numération fournissent une représentation binaire des vecteurs de nombre entier. En utilisant des coordonnées nous avons une autre représentation (plus standard). Les deux représentations diffèrent habituellement dans la longueur. En outre, les vecteurs près l’un de l’autre dans l’espace peuvent avoir des représentations binaires d’aspect très différent .Ces observations suggèrent qu’on puisse appliquer des systèmes de numération dans le domaine de la compression, du codage ou de la cryptographie de données.

Les systèmes de numération sont intéressants d’un point de vue géométrique, aussi. Si nous permettons à des puissances négatives de M d’apparaître dans la représentation binaire nous obtenons une représentation probablement infinie de vrais vecteurs (nous pourrions dire que nous employons un emplacement de la virgule). La frontière de l’ensemble de vecteurs avec la représentation binaire contenant seulement des puissances négatives de M (l’ensemble H de nombres avec la pièce de nombre entier zéro) a la plupart du temps une dimension fractionnaire (c’est une "fractale"). Le rendement du programme peut être employé pour analyser ces ensembles. Ceci signifie l’analyse topologique, par exemple calcul de la dimension, de la connexité etc... Si nous employons la matrice M ci-dessus, nous obtenons l’ensemble suivant.

En conclusion, connaître toutes les matrices jusqu’à une dimension donnée a pu nous aider à un arrangement plus profond des mathématiques des systèmes de numération généralisés.

Lexique :

Binaire : Système de chiffrage composé des seul nombre 0 et 1.

Matrice : Vecteur de valeur à au moins 2 dimension.

Fractale : Équation pouvant représenté une image.