Système de numération unaire - Unary numeral system

Le système de numération unaire est le système de numération le plus simple pour représenter les nombres naturels : pour représenter un nombre N , un symbole représentant 1 est répété N fois.

Dans le système unaire, le nombre 0 (zéro) est représenté par la chaîne vide , c'est-à-dire l'absence de symbole. Les nombres 1, 2, 3, 4, 5, 6, ... sont représentés en unaire par 1, 11, 111, 1111, 11111, 111111, ...

Dans le cadre de la notation positionnelle , l'unaire est le système de numération bijectif de base - 1 . Cependant, comme la valeur d'un chiffre ne dépend pas de sa position, on peut affirmer que l'unaire n'est pas un système positionnel.

L'utilisation de marques de pointage dans le comptage est une application du système de numération unaire. Par exemple, en utilisant la marque de pointage | , le nombre 3 est représenté par ||| . Dans les cultures d' Asie de l'Est , le chiffre 3 est représenté par, un caractère dessiné avec trois traits. (Un et deux sont représentés de la même manière.) En Chine et au Japon, le caractère 正, dessiné avec 5 traits, est parfois utilisé pour représenter 5 comme pointage.

Les nombres unaires doivent être distingués des repunits , qui sont également écrits sous forme de séquences de uns mais ont leur interprétation numérique décimale habituelle .

Opérations

L'addition et la soustraction sont particulièrement simples dans le système unaire, car elles n'impliquent guère plus que la concaténation de chaînes . L'opération de poids de Hamming ou de comptage de population qui compte le nombre de bits non nuls dans une séquence de valeurs binaires peut également être interprétée comme une conversion de nombres unaires en nombres binaires . Cependant, la multiplication est plus lourde et a souvent été utilisée comme cas de test pour la conception de machines de Turing .

Complexité

Comparé aux systèmes de numération positionnels standard , le système unaire est peu pratique et n'est donc pas utilisé dans la pratique pour les grands calculs. Il se produit dans certaines descriptions de problèmes de décision en informatique théorique (par exemple certains problèmes P-complets ), où il est utilisé pour réduire « artificiellement » le temps d'exécution ou les besoins en espace d'un problème. Par exemple, le problème de la factorisation d'entiers est suspecté de nécessiter plus qu'une fonction polynomiale de la longueur de l'entrée comme temps d'exécution si l'entrée est donnée en binaire , mais il n'a besoin que d'un temps d'exécution linéaire si l'entrée est présentée en unaire. Cependant, cela est potentiellement trompeur. L'utilisation d'une entrée unaire est plus lente pour un nombre donné, pas plus rapide ; la distinction est qu'une entrée binaire (ou plus grande base) est proportionnelle au logarithme de base 2 (ou plus grande base) du nombre tandis que l'entrée unaire est proportionnelle au nombre lui-même. Par conséquent, bien que le temps d'exécution et l'espace requis dans unaire semblent meilleurs en fonction de la taille de l'entrée, cela ne représente pas une solution plus efficace.

Dans la théorie de la complexité computationnelle , la numérotation unaire est utilisée pour distinguer les problèmes fortement NP-complets des problèmes qui sont NP-complets mais pas fortement NP-complets. Un problème dans lequel l'entrée comprend des paramètres numériques est fortement NP-complet s'il reste NP-complet même lorsque la taille de l'entrée est artificiellement agrandie en représentant les paramètres en unaire. Pour un tel problème, il existe des instances dures pour lesquelles toutes les valeurs de paramètre sont au plus polynomiales.

Applications

La numérotation unaire est utilisée dans le cadre de certains algorithmes de compression de données tels que le codage de Golomb . Il forme également la base des axiomes de Peano pour formaliser l'arithmétique dans la logique mathématique . Une forme de notation unaire appelée encodage Church est utilisée pour représenter les nombres dans le calcul lambda .

Voir également

Les références

Liens externes