Clasificación de dificultad de la canción

Clasificación de dificultad de la canción
información general
Autor	Donald Ervin Knuth
Nombre	inglés La complejidad de las canciones
Fecha de publicación	1977
Publicado en	Comunicaciones de la ACM
Volumen	27
Liberar	cuatro
Paginas	17–24
Licencia	propiedad
Identificadores
DOI	10.1145/358027.358042
Texto completo
¿ Información en Wikidata ?

" La complejidad de las canciones " es un artículo publicado por el teórico de la informática Donald Knuth en 1977 [1] , que es una " broma interna " relacionada con la teoría de la complejidad computacional . El tema principal del artículo es la tendencia en la evolución de la canción popular , asociada al tránsito de baladas largas y llenas de contenido a textos con un alto grado de repetición y poco (o nulo) contenido significativo [2] . El artículo señala que algunas canciones pueden alcanzar el nivel de complejidad correspondiente a la fórmula O ( log N ) , donde N es el número de palabras de la canción.

Contenido del artículo

Knuth afirma que "nuestros antepasados lejanos inventaron el concepto de coro " para reducir la complejidad espacial de las canciones, lo que se convierte en un factor importante cuando se debe memorizar una gran cantidad de canciones. El Lema 1 en el documento establece que si la duración de una canción se denota por N , entonces agregar un coro reduce la complejidad de la canción a cN , donde el coeficiente c < 1 [1] .

Knuth continúa demostrando una forma de construir canciones con complejidad O ( ), señalando que este enfoque "fue mejorado más tarde por un granjero escocés llamado S. McDonald " [1] . ${\ sqrt N}$

Un enfoque aún más complejo lo dan las canciones con complejidad O ( ). Esta es la clase de canciones conocidas como " m botellas de cerveza en la pared ". $\registro N$

Finalmente, a lo largo del siglo XX, el progreso, impulsado por el hecho de que "la proliferación de las drogas modernas ha llevado a la necesidad de un uso aún menor de la memoria", ha llevado a la aparición de canciones de longitud arbitraria con O(1) complejidad espacial, como la canción definida por: relación recursiva [1] :

S_0=\epsilon, S_k = V_kS_{k-1},\, k\ge 1,

V_k =

' Así es ', 'Me gusta' ,

tu

tu

\para todos

k\ge 1

tu =

'uh huh', 'uh huh'

Investigaciones posteriores

El profesor Kurt Eisemann de la Universidad de San Diego , en una carta a Communications of the ACM [3] , hace más mejoras a la última estimación aparentemente inmejorable, O(1). Comienza con la observación de que, en aplicaciones prácticas, el valor de la "constante oculta" c en la notación O grande puede ser crítico, trazando la línea entre aceptable e inaceptable: por ejemplo, un valor constante de 10 80 daría como resultado la cantidad de información que exceda la capacidad de cualquiera de los medios de almacenamiento de información conocidos por la ciencia. Señala además que ya en la Europa medieval se conocía una técnica mediante la cual el contenido textual de cualquier melodía arbitraria puede describirse mediante la relación de recurrencia , donde , que da el valor de la constante c igual a 2. Sin embargo, resultó que , otra cultura alcanzó el límite inferior absoluto de complejidad O(0)! El profesor Eisemann lo expresa de esta manera: $S_k = C_2S_{k-1}$ $C_2 = 'la'$

Cuando los viajeros del Mayflower desembarcaron en esta costa, los nativos americanos, orgullosos de sus logros en la teoría del almacenamiento y acceso a la información, al principio saludaron a los extraños con completo silencio. Este fue un medio para transmitir su logro más alto en la complejidad de la canción, es decir, para demostrar que el límite más bajo c = 0 es realmente alcanzable.

Texto original (inglés)[ mostrarocultar] Cuando los viajeros del Mayflower descendieron por primera vez a estas costas, los nativos americanos, orgullosos de sus logros en la teoría del almacenamiento y la recuperación de información, al principio dieron la bienvenida a los extraños con un completo silencio. Esto estaba destinado a transmitir su logro máximo en la complejidad de las canciones, es decir, la demostración de que un límite tan bajo como c = 0 es realmente obtenible.

Sin embargo, los europeos resultaron no estar preparados para la percepción de este concepto, y los líderes indios, con el fin de encontrar un terreno común para transferir sus logros, demostraron posteriormente el enfoque descrito por la relación de recurrencia , donde , con una complejidad subóptima, que da el valor c =1 [2] [3] . $S_k = C_1S_{k-1}$ $C_1 = 'yo'$

Notas

↑ 1 2 3 4
Knuth, D. "La complejidad de las canciones", SIGACT News , verano de 1977, 17-24.
- Reimpreso en: Knuth, D. "La Complejidad de las Canciones", Comunicaciones de la ACM , 1984, 27 (4) pp. 344-346.
↑ 1 2 Steven Krantz (2005) Mathematical Apocrypha Redux, ISBN 0-88385-554-2 , págs. 2, 3
↑ 1 2 Kurt Eisemann, "Resultados adicionales sobre la complejidad de las canciones", Comunicaciones de la ACM , vol 28 (1985), no. 3, pág. 235.

Enlaces

" La Complejidad de las Canciones ", Knuth, Donald E. (1984).
Artículo traducido Archivado el 26 de febrero de 2013 en Wayback Machine .

donald knuth
Publicaciones	El arte de programar " Puntaje de dificultad de la canción " Informática y composición tipográfica Matemáticas concretas números surrealistas Cosas de un informático Serie de artículos seleccionados
Software	Τ Ε Χ MIXAL ( MEZCLA MMIX GNU MDK )
fuentes	AMS Euler computadora moderna METAFUENTE
Programación competente	WEB CWEB
Algoritmos	Algoritmo X de Knuth Algoritmo de finalización de Knuth-Bendix Algoritmo de Knuth-Morris-Pratt barajar el látigo Correspondencia Robinson-Schensted-Knuth Algoritmo de Trabb Pardo-Knuth
Otro	Enlaces de baile Cheque de recompensa Knuth Premio Knut prueba de hombre o niño Cuarta base imaginaria -yllón sistema potrzebie de pesos y medidas