Système de numération bijectif

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, un système de numération bijectif est un système de numération qui établit une bijection entre l'ensemble des entiers naturels et l'ensemble des chaînes finies de « chiffres », pris parmi un ensemble fini. En particulier, la numération bijective en base k représente un entier par une chaîne de chiffres de l'ensemble {1, 2..., k} (k ≥ 1), codant le développement de l'entier en puissances de k (bien qu'elle puisse prêter à confusion, cette description est celle qu'on trouve dans la littérature. La numération ordinaire en base k, apparemment bijective, ne répond pas à cette définition, à cause de l'absence de zéros de tête ; par exemple, il n'y a que 90 nombres de deux chiffres en base 10, au lieu des 102 qu'elle réclamerait. La numération bijective en base k est aussi appelée notation k-adique, à ne pas confondre avec le système des nombres p-adiques. En base 1, on parle de système unaire.

Définition[modifier | modifier le code]

Le système de numération k-adique utilise l'ensemble des chiffres {1, 2, ..., k} (k ≥ 1) pour représenter chaque entier de manière unique, comme ceci :

  • L'entier zéro est représenté par la chaîne vide.
  • L'entier représenté par la chaîne de chiffres non vide
anan−1 ... a1a0
est
an kn + an−1 kn−1 + ... + a1 k1 + a0 k0.
  • La chaîne représentant l'entier m > 0 est
anan−1 ... a1a0
a0 = mq0 k,   q0 = f(m/k);
a1 = q0q1 k,  q1 = f(q0/k);
a2 = q1q2 k,  q2 = f(q1/k);
...
an = qn−1 − 0 kqn = f(qn−1/k) = 0;
et
f(x) = pla(x) − 1,
pla(x) étant le plus petit entier non inférieur à x (la fonction plafond).

Propriétés des nombres écrits en base k[modifier | modifier le code]

Pour un k donné ≥ 1,

  • il y a exactement kn nombres k-adiques de longueur n ≥ 0;
  • si k > 1, le nombre de chiffres du nombre k-adique représentant un entier non négatif n est E(logk(n+1)), contrairement à E(logk(n)+1) (n > 0) pour la numération ordinaire en base k ; si k = 1 (donc en numération unaire), alors le nombre de chiffres est n ;
  • une liste de nombres k-adiques, classée dans l'ordre naturel des entiers représentés, est classée par ordre de longueur, puis, pour chaque longueur donnée, par ordre lexicographique. Voici le classement des premiers nombres 1-, 2-, 3-, and 10-adiques, où ε note la chaîne vide (les représentations binaires et décimales ont été ajoutées à fin de comparaison) :
représentation 1-adique : ε 1 11 111 1111 11111 ... (système unaire)
représentation 2-adique : ε 1 2 11 12 21 22 111 112 121 122 211 212 221 222 1111 1112 ...
représentation binaire : 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000 ...
représentation 3-adique : ε 1 2 3 11 12 13 21 22 23 31 32 33 111 112 113 121 ...
représentation 10-adique : ε 1 2 3 4 5 6 7 8 9 A 11 12 13 14 15 16 ...
représentation décimale : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...

Exemples[modifier | modifier le code]

(34152)cinq-adique = 3×54 + 4×53 + 1×52 + 5×51 + 2×50 = (2427)décimal.
(119A)-dix-adique = 1×103 + 1×102 + 9×101 + 10×100 = (1200)décimal.

Dans le second exemple, le chiffre "A" représente l'entier dix. Pour 10 ≤ k ≤ 35, on a l'habitude d'utiliser les lettres successives de l'alphabet pour désigner les chiffres suivant 9 ; par exemple, un système hexadécimal bijectif utiliserait les seize chiffres {1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G}.

Le système décimal sans zéro[modifier | modifier le code]

Le système bijectif en base 10 est aussi connu sous le nom de système décimal sans zéro ; comme on l'a dit, il utilise un chiffre supplémentaire, "A", pour représenter 10.

Comme dans le système décimal usuel, chaque position des chiffres représente une puissance de dix, et, par exemple, 123 est "une centaine, plus deux dizaines, plus trois unités". Tous les entiers positifs dont la représentation décimale ne comporte pas de zéros (tels que 123) ont la même représentation dans le système décimal sans zéro. Ceux qui contiennent un zéro doivent être réécrits, ainsi, 10 devient A, 20 devient 1A, 100 devient 9A, 101 devient A1, 302 devient 2A2, 1000 devient 99A, 1110 devient AAA, 2010 devient 19AA, et ainsi de suite.

L'addition et la multiplication en système décimal sans zéro utilisent essentiellement les mêmes règles que dans le système usuel, si ce n'est que les retenues se produisent quand un résultat dépasse dix, au lieu de neuf. Ainsi, pour calculer 643 + 759, il y a douze unités (on écrit 2 à droite et on retient 1), dix (9+1) dizaines (on pose A et on ne retient rien), treize centaines (on pose 3 et on retient 1), et un millier, d'où le résultat 13A2 plutôt que la notation conventionnelle 1402.

Le système bijectif en base 26[modifier | modifier le code]

Le système bijectif en base 26 est aussi connu sous le nom de base 26 sans zéro ; il utilise les « chiffres » de "A" à "Z" pour représenter les nombres de 1 à 26. La suite des nombres est A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB, BC, ... C'est de cette manière que beaucoup de tableurs tels que Microsoft Excel identifient les colonnes de leurs feuilles de calcul.

Chaque position de chiffre représente une puissance de vingt-six ; ainsi, par exemple, ABC est "une fois 26^2, plus deux fois 26^1, plus trois unités (26^0)" puisque "A" vaut un, "B" vaut deux, et "C" vaut trois. Dans cette représentation, le nombre WIKIPEDIA est :

23 * 26^8 + 9 * 26^7 + 11 * 26^6 + 9 * 26^5 + 16 * 26^4 + 5 * 26^3 + 4 * 26^2 + 9 * 26^1 + 1 * 26^0=4878821185187.

Numération systématique utilisant l'alphabet[modifier | modifier le code]

Le système précédent n'utilise jamais la chaîne vide, et commence donc à compter à partir de 1. Une variante de ce système est utilisée pour nommer les étoiles variables ; il peut plus généralement être utilisé chaque fois qu'on désire une nomenclature systématique utilisant des lettres, et les chaînes de caractères les plus courtes possible.

Notes historiques[modifier | modifier le code]

Le fait que tout entier naturel possède une représentation unique en numération bijective de base k (k ≥ 1) est un théorème du "folklore mathématique" qui a été redécouvert de nombreuses fois. On le trouve par exemple chez Smullyan (1961) pour le cas k = 2, et chez Böhm (1964) pour tous les k ≥ 1 (Böhm utilisait ces représentations pour effectuer des calculs dans le langage de programmation P′′ (en)). Knuth (1969) mentionne le cas particulier k = 10, et Salomaa (en) (1973) discute les cas k ≥ 2. Forslund (1995) estime que d'anciens systèmes de numération bijectifs auraient pu passer inaperçus dans les documents archéologiques, en raison du manque de familiarité avec eux ; ce dernier article est remarquable par le fait qu'il ne cite pas la littérature existante, mais semble réinventer cette notation de toutes pièces.

Notes et références[modifier | modifier le code]

Sources[modifier | modifier le code]

  • Böhm, C. "On a family of Turing machines and the related programming language", ICC Bulletin 3, p. 191, July 1964.
  • Knuth, D. E. The Art of Computer Programming, Vol. 2 : Seminumerical Algorithms, 1ère ed., Addison-Wesley, 1969. (discute le cas de la base 10 page 495)
  • Salomaa, A. (en) Formal Languages, Academic Press, 1973. (Note 9.1, pp. 90-91, discute la base k pour tout k ≥ 2.)
  • Smullyan, R. "Theory of Formal Systems", Annals of Mathematics Studies, Number 47, Princeton, 1961.

Liens externes[modifier | modifier le code]