The Complexity of Songs
The Complexity of Songs ( en , de : About the complexity of songs ) is a scientific joke publishedin 1977 by the computer scientist Donald Ervin Knuth . In it he analyzes the length of songs depending on the text to be learned using the methods of complexity theory . The article also polemicizes an alleged tendency in popular music from complex ballads to strongly repetitive texts or triviality . It was first published in 1977 in SIGACT News , and in 1984 the article wasreprintedin the Communications of the ACM .
Summary
Knuth's article opens with the observation that singing most songs of length requires learning the lyrics of length . As the number of songs increases, this property strains the storage capacity of the memory . As a simple concept for managing memory more efficiently, he introduces the concept of the refrain . In a first lemma he uses an elementary calculation to prove that this concept can reduce the required storage capacity by a constant factor .
Immediately afterwards he analyzes a concept that further improves this result: Using the song Echad Mi Yodea ( he : אחד מי יודע, ji : ver ken zogn ver ken redn ) he proves the existence of songs with asymptotic storage complexity of . He cites the song Green Grow the Rushes, O , (also The Dilly Song ) Alouette , Isn't that a Schnitzelbank and other songs with this structure as conceptually comparable . As an improvement in the coefficient , he discusses the structure of the song Old McDonald had a Farm at length in a lemma.
In a study of Zählreimen the example based on 99 Bottles of Beer constructed he songs with logarithmic memory requirements, so . For this he looks at the scheme with the verses . he sets
It is
is the concatenation of strings and an embedding of the natural number in the English language. Due to the logarithmic number representation of the decimal system , an embedding can be constructed with logarithmic memory expenditure. Obviously, the recursively declared songs with , the empty song , and have a logarithmic complexity for large .
This result has proven to be more than sufficient in all situations that require a generation of songs with limited storage space. He sees a structure that cannot be further optimized in the song That's the Way (I Like It) by the American band KC and the Sunshine Band . He sees the development of this structure as the necessity of larger song instances with minimal storage space due to the progress of modern drug technology. In a short argument he proves its constant complexity ( ) and closes his paper with a reference to the open problem of studying non- deterministic song structures. (see aleatoric )
Receptions
In a letter to the editor to the ACM, Kurt Eisemann ( San Diego State University ) pointed out a well-known improvement in the complexity estimation by considering it as above. If you implement , you have an improvement on the method proposed by Knuth . A complexity of can be achieved through the use of silent data structures . Darrah Chavey took Knuth's idea seriously to develop a didactic approach to explain computer science methods.
Remarks
- ↑ For the notation see Landau symbol .
- ↑ Original wording : However, the advent of modern drugs has led to demands for still less memory space.
Individual evidence
- ^ Steven Krantz: Mathematical Apocrypha Redux . 2005, ISBN 0-88385-554-2 , pp. 2, 3.
-
^ Donald E. Knuth : The complexity of songs . ( Memento of the original from December 26, 2005 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (PDF) In: SIGACT News , Summer 1977, pp. 17–24. Reprint in Commun. ACM , 27, no. 4 (1984), pp. 344-346, doi: 10.1145 / 358027.358042
- ↑ Green Grow the Rushes, O ( Wikisource )
- ^ K. Eisemann, Letter: Further Results on The Complexity of Songs , Comm. ACM, 1985, 28 (3), 235.
- ↑ Darrah Chavey: Songs and the analysis of algorithms . In: Proceedings of the twenty-seventh SIGCSE technical symposium on Computer science education (Philadelphia PA, United States: ACM, 1996), pp. 4-8, doi: 10.1145 / 236452.236475