Sistema de numeração unário

Origem: Wikipédia, a enciclopédia livre.
Parte da série sobre
sistemas de numeração

O sistema numeral unário é o sistema numeral mais simples para representar números naturais:[1] para representar um número N, um símbolo que representa 1 é repetido N vezes.[2]

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

Unário é um sistema numérico bijetivo. No entanto, porque o valor de um dígito não depende da sua posição, não é uma forma de notação posicional, e não está claro se seria apropriado dizer que tem uma base (ou "raiz") de 1, como ele se comporta de maneira diferente de todas as outras bases.

O uso de marcas de contagem na contagem é uma aplicação do sistema numérico unário. Por exemplo, usando a marca de registro | (𝍷), o número 3 é representado como |||. Nas culturas da Ásia Oriental, o número 3 é representado como 三, um caractere desenhado com três traços.[4] (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.[5][6]

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

Operações[editar | editar código-fonte]

Adição e subtração são particularmente simples no sistema unário, pois envolvem pouco mais do que concatenação de cadeias.[7] A operação de peso de Hamming ou de contagem de população 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 para binários.[8] No entanto, a multiplicação é mais complicada e tem sido frequentemente usada como caso de teste para o projeto de máquinas de Turing.[9][10][11]

Complexidade[editar | editar código-fonte]

Comparado aos sistemas numéricos posicionais padrão, o sistema unário é inconveniente e, portanto, não é usado na prática para grandes cálculos. Ocorre em algumas descrições de problemas de decisão na ciência da computação teórica (por exemplo, alguns problemas P-completos), onde é usado para diminuir "artificialmente" o tempo de execução ou os requisitos de espaço de um problema. Por exemplo, suspeita-se que o problema de fatoração de inteiros exija 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.[12][13] 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 de base 2 (ou base maior) do número, enquanto a entrada unária é proporcional ao próprio número. Portanto, embora os requisitos de tempo e espaço de execução em unário pareçam melhores em função do tamanho da entrada, eles não representam uma solução mais eficiente.[14]

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 é aumentado artificialmente pela representação dos parâmetros em unário. Para tal problema, existem instâncias difíceis para as quais todos os valores dos parâmetros são, no máximo, polinomialmente grandes.[15]

Aplicações[editar | editar código-fonte]

Além da aplicação em marcas de contagem, a numeração unária é usada como parte de alguns algoritmos de compressão de dados, como a codificação de Golomb.[16] Também constitui a base para os axiomas de Peano para formalizar a aritmética dentro da lógica matemática.[17] Uma forma de notação unária chamada codificação de Church é usada para representar números no cálculo lambda.[18]

Alguns filtros de spam de e-mail marcam as mensagens com vários asteriscos no cabeçalho do e-mail, como X-Spam-Bar ou X-SPAM-LEVEL. Quanto maior o número, maior a probabilidade de o e-mail ser considerado spam. Usar uma representação unária em vez de um número decimal permite que o usuário pesquise mensagens com uma determinada classificação ou superior. Por exemplo, pesquisar por **** gera mensagens com uma classificação de pelo menos 4.[19]

Ver também[editar | editar código-fonte]

Referências

  1. ↑ Hodges, Andrew (2009). One to Nine: The Inner Life of Numbers. [S.l.]: Anchor Canada. p. 14. ISBN 9780385672665 .
  2. ↑ Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science. Col: Computer Science and Scientific Computing 2nd ed. [S.l.]: Academic Press. p. 117. ISBN 9780122063824 .
  3. ↑ Hext, Jan (1990). Programming Structures: Machines and Programs. 1. [S.l.]: Prentice Hall. p. 33. ISBN 9780724809400 .
  4. ↑ Woodruff, Charles E. (1909). «The Evolution of Modern Numerals from Ancient Tally Marks». American Mathematical Monthly]]. 16 (8–9): 125–33. JSTOR 2970818. doi:10.2307/2970818 .
  5. ↑ Hsieh, Hui-Kuang (1981). «Chinese Tally Mark». The American Statistician. 35 (3): 174. JSTOR 2683999. doi:10.2307/2683999 
  6. ↑ Lunde, Ken; Miura, Daisuke (27 de janeiro de 2016), «Proposal to Encode Five Ideographic Tally Marks», Unicode Consortium (PDF), Proposal L2/16-046 
  7. ↑ Sazonov, Vladimir Yu. (1995), «On feasible numbers», Logic and computational complexity (Indianapolis, IN, 1994), ISBN 978-3-540-60178-4, Lecture Notes in Comput. Sci., 960, Springer, Berlin, pp. 30–51, MR 1449655, doi:10.1007/3-540-60178-3_78 . See in particular p.  48.
  8. ↑ Blaxell, David (1978), «Record linkage by bit pattern matching», in: Hogben, David; Fife, Dennis W., Computer Science and Statistics--Tenth Annual Symposium on the Interface, NBS Special Publication, 503, U.S. Department of Commerce / National Bureau of Standards, pp. 146–156 .
  9. ↑ Hopcroft, John E.; Ullman, Jeffrey D. (1979), Introduction to Automata Theory, Languages, and Computation, ISBN 978-0-201-02988-8, Addison Wesley, Example 7.7, pp. 158–159 .
  10. ↑ Dewdney, A. K. (1989), The New Turing Omnibus: Sixty-Six Excursions in Computer Science, ISBN 9780805071665, Computer Science Press, p. 209 .
  11. ↑ Rendell, Paul (2015), «5.3 Larger Example TM: Unary Multiplication», Turing Machine Universality of the Game of Life, ISBN 9783319198422, Emergence, Complexity and Computation, 18, Springer, pp. 83–86 .
  12. ↑ Arora, Sanjeev; Barak, Boaz (2007), «The computational model —and why it doesn't matter» (PDF), Computational Complexity: A Modern Approach January 2007 draft ed. , Cambridge University Press, §17, pp. 32–33 .
  13. ↑ Feigenbaum, Joan (2012), CPSC 468/568 HW1 Solution Set (PDF), Computer Science Department, Yale University 
  14. ↑ Moore, Cristopher; Mertens, Stephan (2011), The Nature of Computation, ISBN 9780199233212, Oxford University Press, p. 29 .
  15. ↑ Garey, M. R.; Johnson, D. S. (1978), «'Strong' NP-completeness results: Motivation, examples, and implications», Journal of the ACM, 25 (3): 499–508, MR 478747, doi:10.1145/322077.322090 .
  16. ↑ Golomb, S.W. (1966), «Run-length encodings», IEEE Transactions on Information Theory, IT-12 (3): 399–401, doi:10.1109/TIT.1966.1053907 .
  17. ↑ Magaud, Nicolas; Bertot, Yves (2002), «Changing data structures in type theory: a study of natural numbers», Types for proofs and programs (Durham, 2000), ISBN 978-3-540-43287-6, Lecture Notes in Comput. Sci., 2277, Springer, Berlin, pp. 181–196, MR 2044538, doi:10.1007/3-540-45842-5_12 .
  18. ↑ Jansen, Jan Martin (2013), «Programming in the λ-calculus: from Church to Scott and back», The Beauty of Functional Code, ISBN 978-3-642-40354-5, Lecture Notes in Computer Science, 8106, Springer-Verlag, pp. 168–180, doi:10.1007/978-3-642-40355-2_12 .
  19. ↑ [1]

Ligações externas[editar | editar código-fonte]

Commons
Commons
O Commons possui imagens e outros ficheiros sobre Unary numeral system
Obtida de "https://pt.wikipedia.org/w/index.php?title=Sistema_de_numeração_unário&oldid=67681734"