Sistema numeral unário - Unary numeral system

O sistema de numeração unário é o sistema de numeração mais simples para representar números naturais : para representar um número N , um símbolo que representa 1 é repetido N vezes.

No sistema unário, o número 0 (zero) é representado pela string vazia , ou seja, a ausência de um símbolo. Os números 1, 2, 3, 4, 5, 6, ... são representados em unário como 1, 11, 111, 1111, 11111, 111111, ...

Na estrutura de notação posicional , o unário é o sistema numérico de base bijetiva - 1 . No entanto, como o valor de um dígito não depende de sua posição, pode-se argumentar que unário não é um sistema posicional.

O uso de marcas de contagem na contagem é uma aplicação do sistema numeral unário. Por exemplo, usando a marca de contagem | , o número 3 é representado como ||| . Nas culturas do Leste Asiático , o número 3 é representado como, um caractere desenhado com três traços. (Um e dois são representados de forma semelhante.) Na China e no Japão, o caractere 正, desenhado com 5 traços, às vezes é usado para representar 5 como uma contagem.

Os números unários devem ser diferenciados dos reencontros , que também são escritos como sequências de uns, mas têm sua interpretação numérica decimal usual .

Operações

Adição e subtração são particularmente simples no sistema unário, pois envolvem pouco mais do que concatenação de strings . A operação de contagem de população ou peso de Hamming que conta o número de bits diferentes de zero em uma sequência de valores binários também pode ser interpretada como uma conversão de números unários em binários . No entanto, a multiplicação é mais complicada e costuma ser usada como um caso de teste para o projeto de máquinas de Turing .

Complexidade

Comparado aos sistemas numéricos posicionais padrão , o sistema unário é inconveniente e, portanto, não é usado na prática para cálculos grandes. Ele ocorre em algumas descrições de problemas de decisão na ciência da computação teórica (por exemplo, alguns problemas P-complete ), onde é usado para diminuir "artificialmente" o tempo de execução ou os requisitos de espaço de um problema. Por exemplo, o problema da fatoração de inteiros é suspeito de exigir mais do que uma função polinomial do comprimento da entrada como tempo de execução se a entrada for dada em binário , mas só precisa de tempo de execução linear se a entrada for apresentada em unário. No entanto, isso é potencialmente enganoso. Usar uma entrada unária é mais lento para qualquer número, não mais rápido; a distinção é que uma entrada binária (ou base maior) é proporcional ao logaritmo da base 2 (ou base maior) do número, enquanto a entrada unária é proporcional ao próprio número. Portanto, embora o tempo de execução e os requisitos de espaço no unário pareçam melhores em função do tamanho da entrada, não representam uma solução mais eficiente.

Na teoria da complexidade computacional , a numeração unária é usada para distinguir problemas fortemente NP-completos de problemas que são NP-completos, mas não fortemente NP-completos. Um problema no qual a entrada inclui alguns parâmetros numéricos é fortemente NP-completo se permanecer NP-completo mesmo quando o tamanho da entrada é artificialmente maior, representando os parâmetros em unário. Para esse problema, existem instâncias rígidas para as quais todos os valores dos parâmetros são no máximo polinomialmente grandes.

Formulários

A numeração unária é usada como parte de alguns algoritmos de compactação de dados, como a codificação de Golomb . Ele também forma a base para os axiomas de Peano para formalizar a aritmética dentro da lógica matemática . Uma forma de notação unária chamada codificação Church é usada para representar números dentro do cálculo lambda .

Veja também

Referências

links externos