SZTAKI Desktop Grid

Trouver tous les systèmes de numération binaire généralisés jusqu'à la dimension 13 voir au delà

INSCRIPTION

Télécharger Boinc (tutorial)

URL du projet : http://szdg.lpds.sztaki.hu/szdg

Os supportées : Linux, Mac OS, Windows

Détails du Projet

Le projet BinSYS

Traduction de la page http://szdg.lpds.sztaki.hu/szdg/desc_numsys_es.php

Description du projet

But

Le but du projet est de trouver tous les systèmes de numération binaire généralisés jusqu'à la dimension 13 voir au delà. Ci-dessous nous décrirons brièvement le concept de système de numération et nous mentionnerons quelques applications possibles.

Introduction

Soit n un entier supérieur à 1. Lorsque nous parlons de systèmes de numération dans le sens original, nous considérons que chaque nombre naturel z peut uniquement être écrit sous sa forme finie
On dit que n est la base du système de numération, les étant appelés chiffres. Si n = 2 nous parlons de système de numération binaire. Ces systèmes sont trop "pauvres" pour représenter des nombres négatifs, nous avons donc besoin d'un signe.
Si nous permettions à la base d'être un entier négatif, une représentation de tous les entiers serait possible. Par exemple, si nous utilisons la base -2, chaque entier a la forme

On peut le généraliser pour les entiers algébriques d'une extension finie de l'ensemble des nombres rationnels. Un exemple simple : tous les entiers gaussiens (nombres complexes sous la forme x+yi, où x,y sont des entiers) ne peuvent être écrits dans la base (-1+i) comme suit


En utilisant l'algèbre linéaire nous pouvons définir des systèmes de numération d'une manière plus générale. La base est à présent une matrice et les chiffres sont des vecteurs. Nous pouvons reformuler l'exemple précédent. Chaque vecteur bi-dimensionel entier a une représentation en tant que somme finie , où et
Nous parlons d'un système binaire si le déterminant de M est ±2. Dans ce cas nous n'avons que deux chiffres, l'un d'entre eux étant l'origine. Cela signifie que si nous avons un système de numération chaque vecteur entier peut être représenté par une série finie de 0 et de 1.

Toute matrice M ne peut pas être la base d'un système de numération. Jusqu'à présent, aucune caractéristique de la "bonne" matrice n'a été donnée.

Il existe des conditions nécessaires et des conditions suffisantes mais les divergences entre elles sont trop importantes. A ce jour, il n'existe aucune méthode efficiente pour travailler avec des matrices qui remplissent les conditions nécessaires sans remplir les conditions suffisantes. Il est à noter que si nous fixons le déterminant et la dimension, on peut affirmer de manière triviale que le nombre de matrices possibles est fini.

Résultats attendus

Le programme a pour but de trouver des systèmes de numération binaires généralisés. Une recherche étendue est effectuée dans l'ensemble fini des matrices d'une taille donnée remplissant les conditions nécessaires. La difficulté réside dans le fait que la taille de cet ensemble fini de matrices est une fonction exponentielle par rapport à leur dimension. Il semble actuellement possible de s'attaquer au cas des matrices de dimension 11x11. Pour vérifier les conditions nécessaires supplémentaires, le programme effectue beaucoup d'opérations à virgule flottante. De ce fait, beaucoup de temps processeur est nécessaire. Heureusement, la parallélisation est possible et nous pouvons en bénéficier en utilisant plusieurs machines.

Le programme génère une liste de matrices (pour être plus précis des polynômes caractéristiques) qui sont susceptibles d'être des bases du système de numération. Cette liste est traitée par un autre programme (qui ne nécessite pas autant de puissance processeur). Le résultat final est alors une liste (complète) de systèmes de numération binaires dans une dimension fixée.
Ensuite nous effectuons l'analyse théorique de l'information. Les systèmes de numération fournissent une représentation binaire des vecteurs entiers. En utilisant des coordonnées nous avons une autre présentation (plus standard). Les deux représentations diffèrent habituellement en longueur.

En outre, les vecteurs proches les uns des autres dans l'espace peuvent avoir des représentations binaires qui paraissent très différentes.
Ces observations suggèrent que l'on pourrait appliquer les systèmes de numération dans la compression de données, le codage ou la cryptographie.

Les systèmes de numération sont intéressant d'un point de vue géométrique également. Si nous permettons l'apparition de puissances négatives pour M dans la représentation binaire, nous obtenons une représentation infinie de vecteurs réels (on pourrait dire que l'on utilise une "virgule" (radix point)). La frontière de l'ensemble de vecteurs avec représentation binaire contenant uniquement des puissances négatives de M (l'ensemble H de nombres sans partie entière) a la plupart du temps la dimension fractionnaire (elle est une "fractale"). Les résultats de l'exécution du programme peuvent être utilisés pour analyser ces ensembles. Il s'agit d'analyses topologiques (calculs de dimension, de connexion etc.). Si nous utilisons la matrice M ci-dessus, nous obtenons l'ensemble suivant.

En conclusion, le fait de connaître toutes les matrices jusqu'à une dimension donnée pourrait nous aider à comprendre plus en profondeur les mathématiques de systèmes de numération généralisés.

Pour des informations plus détaillées sur ce projet, visitez ce site.

Visitez la page du projet, hébergée par l'ELTE (Eötvös Loránd University).

SZTAKI Desktop Grid honlap

Article réalisé et/ou mis à jour par les membres du forum de l'équipe EST