91.137.29.180: Liedtitel von "Old MacDonald Had a Farm" korrigiert

2024-05-07T18:42:03Z

Liedtitel von "Old MacDonald Had a Farm" korrigiert

Neue Seite

'''{{lang|en|The Complexity of Songs}}''' ([[Englische Sprache|en]], [[Deutsche Sprache|de]]: ''Über die Komplexität von Liedern'') ist ein im Jahre 1977 von dem [[Informatik]]er [[Donald E. Knuth]] veröffentlichter Fachartikel und [[wissenschaftlicher Witz]]. Er analysiert darin die Länge von Liedern in Abhängigkeit vom zu lernenden Text mit den Methoden der [[Komplexitätstheorie]]. Der Artikel [[Polemik|polemisiert]] zudem eine angebliche Tendenz [[Populäre Musik|populärer Musik]] von komplexen Balladen hin zu stark [[Repetitio|repetitiven]] Texten beziehungsweise [[Trivialität]].<ref>Steven Krantz: ''Mathematical Apocrypha Redux''. 2005, ISBN 0-88385-554-2, S. 2, 3.</ref> Die Erstveröffentlichung erfolgte 1977 in ''[[SIGACT]] News'', 1984 wurde der Artikel in den ''[[Communications of the ACM]]'' nachgedruckt.<ref name="KNUTH">[[Donald E. Knuth]]: {{Webarchiv|url=http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf |wayback=20051226111159 |text=''The complexity of songs''. |archiv-bot=2019-05-17 22:19:48 InternetArchiveBot }} (PDF) In: ''SIGACT News'', Sommer 1977, S. 17–24.<br /> Reprint in ''Commun. [[Association for Computing Machinery|ACM]]'', 27, no. 4 (1984), S. 344–346, [[doi:10.1145/358027.358042]]</ref>

== Zusammenfassung ==
Knuths Artikel eröffnet mit der Beobachtung, dass das [[Gesang|Singen]] der meisten Lieder der Länge <math>n</math> das Lernen von Text der Länge <math>n</math> voraussetzt. Bei wachsender Liedzahl strapaziere diese Eigenschaft die [[Speicherkapazität]]en des [[Gedächtnis]]ses. Als ein einfaches Konzept zur effizienteren Verwaltung von Speicher führt er das Konzept des [[Refrain]]s ein. In einem ersten [[Hilfssatz|Lemma]] beweist er mit einer [[Grundrechenart|elementaren Rechnung]], dass dieses Konzept die benötigte Speicherkapazität um einen konstanten Faktor <math>c<1</math> reduzieren kann.

Im direkten Anschluss analysiert er ein Konzept, das dieses Resultat weiter verbessert: Anhand des Liedes ''[[Echad mi jodea]]'' ([[Hebräische Sprache|he]]: {{he|אחד מי יודע&lrm;}}, [[Jiddische Sprache|ji]]: ''ver ken zogn ver ken redn'') beweist er die Existenz von Liedern mit [[Platzkomplexität|asymptotischer Speicherkomplexität]] von <math>\mathcal{O}(\sqrt{n})</math>.<ref group="A">Zur Notation siehe [[Landau-Symbol]].</ref> Als konzeptuell vergleichbar nennt er das Lied ''{{lang|en|[[Green Grow the Rushes, O]]}}'',<ref>''[[s:en:Green Grow the Rushes, O|Green Grow the Rushes, O]]'' ([[Wikisource]])</ref> (auch ''{{lang|en|The Dilly Song}}'') ''[[Alouette (Lied)|Alouette]]'',<ref>[https://www.klingendebruecke.de/wp-content/uploads/2024/01/1465_Alouettegent_1_fra.pdf ''L’Alouette''] Liedblatt (Noten, Text, Übersetzung) der [[Klingende Brücke|Klingenden Brücke]]</ref> ''[[Ist das nicht ein Schnitzelbank]]'' und weitere Lieder mit dieser Struktur. Als eine Verbesserung im [[Koeffizient]]en diskutiert er die Struktur des Liedes ''{{lang|en|[[Old MacDonald Had a Farm]]}}'' ausführlich in einem Lemma.

In einer Untersuchung von [[Zählreim]]en anhand des Beispiels von ''{{lang|en|[[99 Bottles of Beer]]}}'' konstruiert er Lieder mit [[logarithmisch]]em Speicherbedarf, also <math>\mathcal{O}(\log n)</math>. Er betrachtet dafür das Schema mit den Versen <math>V_k</math>. dabei setzt er

<math>\begin{align}
V_k = &T_k \ast B\ast W\ast ',' \\
&T_k\ast B \ast ';' \\
&'\mbox{If one of those bottles should happen to fall, }'\\
&T_{k-1}\ast B\ast W\ast'.'
\end{align}</math>

Dabei ist

<math>
\begin{align}
B&= '\mbox{ bottles of Beer}'\\
W&= '\mbox{ on the Wall}'
\end{align}
</math>

<math>\ast</math> ist die [[Konkatenation (Wort)|Verkettung von Strings]] und <math>T_k</math> eine Einbettung der [[Natürliche Zahl|natürlichen Zahl]] <math>k</math> in die englische Sprache. Aufgrund der logarithmischen [[Zahlendarstellung]] des [[Dezimalsystem]]s lässt sich so eine Einbettung mit logarithmischem Speicheraufwand konstruieren. Offensichtlich haben dann die [[rekursiv]] erklärten Lieder <math>L_n</math> mit <math>L_0=\varepsilon</math>, das [[Leeres Wort|leere Lied]], und <math>L_{n+1}=V_{n+1} \ast L_n</math> eine logarithmische Komplexität für große <math>n\in\mathbb{N}</math>.

Dieses Resultat habe sich in allen Situationen, die eine Liedgeneration bei begrenztem Speicherplatz erfordern, als mehr als ausreichend bewährt. Eine nicht weiter optimierbare Struktur sieht er in dem Song ''{{lang|en|[[That’s the Way (I Like It)]]}}'' der US-amerikanischen Band [[KC and the Sunshine Band]]. Die Entwicklung dieser Struktur sieht er durch die Notwendigkeit größerer Lied[[Exemplar|instanzen]] bei minimalem Speicherplatz durch den Fortschritt moderner [[Droge]]n<nowiki/>technologie bedingt.<ref group="A">Originalwortlaut: ''{{lang|en|However, the advent of modern drugs has led to demands for still less memory space.}}''</ref> Er beweist in einem kurzen Argument dessen konstante Komplexität (<math>\mathcal{O}(1)</math>) und schließt sein Papier mit dem Hinweis auf das [[Ungelöste Probleme der Mathematik|offene Problem]] des Studiums nicht[[deterministisch]]er Liedstrukturen (siehe [[Aleatorik]]).

== Rezeptionen ==
In einem [[Leserbrief]] an die ACM wies Kurt Eisemann ([[San Diego State University]]) auf eine bekannte Verbesserung der Komplexitätsabschätzung hin, indem die <math>L_n</math> wie oben zu betrachten seien. Setzt man <math>V_k='\mbox{la}'</math>, habe man eine Verbesserung der von Knuth vorgeschlagenen Methode um <math>c=\frac{2}{53}= 0.037736\dots</math>. Eine Komplexität von <math>\mathcal{O}(0)</math> könne man durch die Nutzung ''stiller Datenstrukturen'' erreichen.<ref>K. Eisemann, Letter: ''Further Results on The Complexity of Songs'', Comm. ACM, 1985, 28(3), 235.</ref> Darrah Chavey griff Knuths Idee ernsthaft auf, um einen [[didaktisch]]en Ansatz zur Erläuterung von Methoden der Informatik zu entwickeln.<ref>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), S. 4–8, [[doi:10.1145/236452.236475]]</ref>

== Anmerkungen ==
<references group="A" />

== Einzelnachweise ==
<references />

{{SORTIERUNG:Complexity of Songs #The}}

[[Kategorie:Komplexitätstheorie]]
[[Kategorie:Musikkritik]]
[[Kategorie:Musiktheoretische Literatur]]
[[Kategorie:Popmusik]]
[[Kategorie:Wissenschaftlicher Witz]]

The Complexity of Songs - Versionsgeschichte

91.137.29.180: Liedtitel von "Old MacDonald Had a Farm" korrigiert