Hispanopedia Wiki
Articulo de referencia

Sistema de numeración unario

El sistema de numeración unario es el sistema de numeración más simple para representar números naturales : [ 1 ] para representar un número N , se repite N veces un símbolo que...

Hispanopedia WikiContenido en espanolLectura gratuita

El sistema de numeración unario es el sistema de numeración más simple para representar números naturales : [ 1 ] para representar un número N , se repite N veces un símbolo que representa el 1. [ 2 ]

En el sistema unario, el número 0 (cero) se representa mediante la cadena vacía , es decir, la ausencia de un símbolo. Los números 1, 2, 3, 4, 5, 6, ... se representan en el sistema unario como 1, 11, 111, 1111, 11111, 111111, ... [ 3 ]

El sistema unario es un sistema numérico biyectivo . Sin embargo, aunque a veces se le ha descrito como "base 1" [ 4 ] , difiere en algunos aspectos importantes de las notaciones posicionales , en las que el valor de un dígito depende de su posición dentro de un número. Por ejemplo, la forma unaria de un número puede ser exponencialmente más larga que su representación en otras bases [ 5 ] .

El uso de marcas de conteo en el conteo es una aplicación del sistema numérico unario. Por ejemplo, usando la marca de conteo | (𝍷), el número 3 se representa como | | | . En las culturas de Asia Oriental , el número 3 se representa como三, un carácter dibujado con tres trazos. [ 6 ] (El uno y el dos se representan de manera similar). En China y Japón, el carácter 正, dibujado con 5 trazos, se usa a veces para representar el 5 como una marca de conteo. [ 7 ] [ 8 ]

Los números unarios deben distinguirse de las repunidades , que también se escriben como secuencias de unos, pero tienen su interpretación numérica decimal habitual.

Operaciones

La suma y la resta son particularmente sencillas en el sistema unario, ya que implican poco más que la concatenación de cadenas . [ 9 ] La operación de peso de Hamming o de conteo de población, que cuenta el número de bits distintos de cero en una secuencia de valores binarios, también puede interpretarse como una conversión de números unarios a binarios . [ 10 ] Sin embargo, la multiplicación es más engorrosa y a menudo se ha utilizado como caso de prueba para el diseño de máquinas de Turing . [ 11 ] [ 12 ] [ 13 ]

Complejidad

En comparación con los sistemas de numeración posicional estándar , el sistema unario es inconveniente y, por lo tanto, no se utiliza en la práctica para cálculos grandes. Aparece en algunas descripciones de problemas de decisión en informática teórica (por ejemplo, algunos problemas P-completos ), donde se utiliza para disminuir "artificialmente" el tiempo de ejecución o los requisitos de espacio de un problema. Por ejemplo, se sospecha que el problema de factorización de enteros requiere más de una función polinómica de la longitud de la entrada como tiempo de ejecución si la entrada se da en binario , pero solo necesita un tiempo de ejecución lineal si la entrada se presenta en unario. [ 14 ] Sin embargo, esto puede ser engañoso. Usar una entrada unaria es más lento para cualquier número dado, no más rápido; la distinción es que una entrada binaria (o de base mayor) es proporcional al logaritmo en base 2 (o de base mayor) del número, mientras que una entrada unaria es proporcional al número mismo. Por lo tanto, si bien el tiempo de ejecución y los requisitos de espacio en unario parecen mejores en función del tamaño de la entrada, no representan una solución más eficiente. [ 15 ]

En la teoría de la complejidad computacional , la numeración unaria se utiliza para distinguir los problemas fuertemente NP-completos de aquellos que son NP-completos pero no fuertemente NP-completos. Un problema cuya entrada incluye algunos parámetros numéricos es fuertemente NP-completo si permanece NP-completo incluso cuando el tamaño de la entrada se incrementa artificialmente al representar los parámetros en unario. Para este tipo de problema, existen instancias difíciles en las que todos los valores de los parámetros son, como máximo, polinomialmente grandes. [ 16 ]

Aplicaciones

Además de su aplicación en marcas de conteo, la numeración unaria se utiliza como parte de algunos algoritmos de compresión de datos, como la codificación de Golomb . [ 17 ] También constituye la base de los axiomas de Peano para formalizar la aritmética dentro de la lógica matemática . [ 18 ] Una forma de notación unaria llamada codificación de Church se utiliza para representar números dentro del cálculo lambda . [ 19 ]

Algunos filtros de correo no deseado etiquetan los mensajes con una serie de asteriscos en el encabezado, como X-Spam-Bar o X-SPAM-LEVEL . Cuanto mayor sea el número, mayor será la probabilidad de que el correo se considere spam. El uso de una representación unaria en lugar de un número decimal permite al usuario buscar mensajes con una calificación determinada o superior. Por ejemplo, al buscar **** se obtienen mensajes con una calificación de al menos 4. [ 20 ]

Véase también

Referencias

  1. ↑ Hodges, Andrew (2009), One to Nine: The Inner Life of Numbers , Anchor Canada, p.  14, ISBN 9780385672665.
  2. ↑ Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994), Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica , Informática y computación científica (2.ª ed.), Academic Press, pág. 117, ISBN   9780122063824.
  3. ↑ Hext, Jan (1990), Estructuras de programación: máquinas y programas , vol. 1, Prentice Hall, pág. 33, ISBN   9780724809400.
  4. ↑ Brian Hayes (2001), "Third Base" , American Scientist , 89 (6): 490, doi : 10.1511/2001.40.3268 , archivado del original el 11 de enero de 2014 , consultado el 28 de julio de 2013.
  5. ↑ Zdanowski, Konrad (2022), "Sobre la eficiencia de las notaciones para números naturales", Theoretical Computer Science , 915 : 1–10 , doi : 10.1016/j.tcs.2022.02.015 , MR 4410388 
  6. ↑ Woodruff, Charles E. (1909), "La evolución de los numerales modernos a partir de marcas de conteo antiguas" , American Mathematical Monthly , 16 ( 8–9 ): 125–33 , doi : 10.2307/2970818 , JSTOR 2970818 .
  7. ↑ Hsieh, Hui-Kuang (1981), "Marca de conteo china", The American Statistician , 35 (3): 174, doi : 10.2307/2683999 , JSTOR 2683999 
  8. ↑ Lunde, Ken; Miura, Daisuke (27 de enero de 2016), "Propuesta para codificar cinco marcas de conteo ideográficas", Consorcio Unicode (PDF) , Propuesta L2/16-046
  9. ↑ Sazonov, Vladimir Yu. (1995), "Sobre números factibles", Lógica y complejidad computacional (Indianapolis, IN, 1994) , Lecture Notes in Comput. Sci., vol. 960, Springer, Berlín, pp. 30–51 , doi : 10.1007/3-540-60178-3_78 , ISBN   978-3-540-60178-4, MR 1449655 Véase en particular la página 48.
  10. ↑ Blaxell, David (1978), "Enlace de registros mediante coincidencia de patrones de bits", en Hogben, David; Fife, Dennis W. (eds.), Ciencias de la Computación y Estadística: Décimo Simposio Anual sobre la Interfaz , Publicación Especial del NBS, vol. 503, Departamento de Comercio de EE. UU. / Oficina Nacional de Estándares, págs. 146–156  .
  11. ↑ Hopcroft, John E .; Ullman, Jeffrey D. (1979), Introducción a la teoría de autómatas, lenguajes y computación , Addison Wesley, Ejemplo 7.7, págs. 158–159 , ISBN 978-0-201-02988-8.
  12. ↑ Dewdney, AK (1989), The New Turing Omnibus: Sixty-Six Excursions in Computer Science , Computer Science Press, p. 209, ISBN  9780805071665.
  13. ↑ Rendell, Paul (2015), "5.3 Ejemplo más amplio TM: Multiplicación unaria", Universalidad de la máquina de Turing del juego de la vida , Emergence, Complexity and Computation, vol. 18, Springer, pp. 83–86 , ISBN   9783319198422.
  14. ↑ Arora, Sanjeev ; Barak, Boaz (2007), "El modelo computacional y por qué no importa" (PDF) , Complejidad computacional: un enfoque moderno ( edición preliminar de enero de 2007), Cambridge University Press, §17, pp. 32–33 , consultado el 10 de mayo de 2017 .  .
  15. ↑ Moore, Cristopher ; Mertens, Stephan (2011), La naturaleza de la computación , Oxford University Press, pág. 29, ISBN  9780199233212.
  16. ^ Garey, señor ; Johnson, DS (1978), "Resultados de NP-completitud "fuertes": motivación, ejemplos e implicaciones", Journal of the ACM , 25 (3): 499– 508, doi : 10.1145/322077.322090 , MR 0478747 , S2CID 18371269  .
  17. ↑ Golomb, SW (1966), "Codificaciones de longitud de ejecución" , IEEE Transactions on Information Theory , IT-12 (3): 399–401 , doi : 10.1109/TIT.1966.1053907.
  18. ↑ Magaud, Nicolas; Bertot, Yves (2002), "Changing data structures in type theory: a study of natural numbers", Types for proofs and programs (Durham, 2000) , Lecture Notes in Comput. Sci., vol. 2277, Springer, Berlín, pp. 181–196 , doi : 10.1007/3-540-45842-5_12 , ISBN   978-3-540-43287-6, MR 2044538 .
  19. ↑ Jansen, Jan Martin (2013), "Programación en el cálculo λ: de Church a Scott y viceversa", The Beauty of Functional Code , Lecture Notes in Computer Science, vol. 8106, Springer-Verlag, pp. 168–180 , doi : 10.1007/978-3-642-40355-2_12 , ISBN   978-3-642-40354-5.
  20. ↑ Correo electrónico, control de spam, cómo obtener servicio para servidores de correo electrónico departamentales
  • Secuencia OEIS A000042 (Representación unaria de números naturales)