Sistema de numeração unário: diferenças entre revisões

Origem: Wikipédia, a enciclopédia livre.
Ver a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
MathexBR (discussão | contribs)
9 262 edições
nova página: {{Sistemas numéricos}} O '''sistema numeral unário''' é o sistema numeral mais simples para representar números naturais:<ref>{{citar livro|título=One to Nine: The Inner Life of Numbers|primeiro=Andrew|último=Hodges|publicado=Anchor Canada|ano=2009|isbn=9780385672665|página=14|url=https://books.google.com/books?id=UCuwrtBax7AC&pg=PA14}}.</ref> para representar um número N, um símbolo que representa 1 é repetido N vezes.<ref>{{citar livro|título=C...
(Sem diferenças)

Revisão das 22h52min de 5 de março de 2024

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

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

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

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

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). «Unicode Consortium» (PDF). Proposal L2/16-046  |contribuição= ignorado (ajuda)
  7. ↑ Sazonov, Vladimir Yu. (1995). «Logic and computational complexity (Indianapolis, IN, 1994)». Lecture Notes in Comput. Sci. Springer, Berlin. pp. 30–51. ISBN 978-3-540-60178-4. MR 1449655. doi:10.1007/3-540-60178-3_78  |contribuição= ignorado (ajuda). See in particular p.  48.
  8. ↑ Blaxell, David (1978). Hogben, David; Fife, Dennis W., eds. «Computer Science and Statistics--Tenth Annual Symposium on the Interface». NBS Special Publication. U.S. Department of Commerce / National Bureau of Standards. pp. 146–156  |contribuição= ignorado (ajuda).
  9. ↑ Hopcroft, John E.; Ullman, Jeffrey D. (1979). «Introduction to Automata Theory, Languages, and Computation». Addison Wesley. Example 7.7, pp. 158–159. ISBN 978-0-201-02988-8 .
  10. ↑ Dewdney, A. K. (1989). «The New Turing Omnibus: Sixty-Six Excursions in Computer Science». Computer Science Press. p. 209. ISBN 9780805071665 .
  11. ↑ Rendell, Paul (2015). «Turing Machine Universality of the Game of Life». Emergence, Complexity and Computation. Springer. pp. 83–86. ISBN 9783319198422  |contribuição= ignorado (ajuda).
  12. ↑ Arora, Sanjeev; Barak, Boaz (2007). «Computational Complexity: A Modern Approach» January 2007 draft ed. Cambridge University Press. §17, pp. 32–33  |capítulo= ignorado (ajuda).
  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». Oxford University Press. p. 29. ISBN 9780199233212 .
  15. ↑ Garey, M. R.; Johnson, D. S. (1978). «'Strong' NP-completeness results: Motivation, examples, and implications». Journal of the ACM. pp. 499–508. MR 478747. doi:10.1145/322077.322090  .
  16. ↑ Golomb, S.W. (1966). «Run-length encodings». IEEE Transactions on Information Theory. pp. 399–401. doi:10.1109/TIT.1966.1053907 .
  17. ↑ Magaud, Nicolas; Bertot, Yves (2002). «Types for proofs and programs (Durham, 2000)». Lecture Notes in Comput. Sci. Springer, Berlin. pp. 181–196. ISBN 978-3-540-43287-6. MR 2044538. doi:10.1007/3-540-45842-5_12  |contribuição= ignorado (ajuda).
  18. ↑ Jansen, Jan Martin (2013). «The Beauty of Functional Code». Lecture Notes in Computer Science. Springer-Verlag. pp. 168–180. ISBN 978-3-642-40354-5. doi:10.1007/978-3-642-40355-2_12  |contribuição= ignorado (ajuda).
  19. ↑ http://answers.uillinois.edu/illinois/page.php?id=49002

Ligações externas

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=67582457"