The Complexity of Songs

{{#invoke:Vorlage:lang|flat}} (en, de: Über die Komplexität von Liedern) ist ein im Jahre 1977 von dem Informatiker 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 polemisiert zudem eine angebliche Tendenz populärer Musik von komplexen Balladen hin zu stark 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: {{#if:20051226111159

      | {{#ifeq: 20051226111159 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: The complexity of songs. | {{#invoke:WLink|getEscapedTitle|The complexity of songs.}} | {{#invoke:Webarchiv|getdomain|http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20051226111159}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Datum
         | {{#if: The complexity of songs. | {{#invoke:WLink|getEscapedTitle|The complexity of songs.}} | {{#invoke:Webarchiv|getdomain|http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2019-05-17 22:19:48 InternetArchiveBot | 2019-05-17 22:19:48 InternetArchiveBot |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20051226111159}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: The complexity of songs. | {{#invoke:WLink|getEscapedTitle|The complexity of songs.}} | {{#invoke:Webarchiv|getdomain|http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2019-05-17 22:19:48 InternetArchiveBot | 2019-05-17 22:19:48 InternetArchiveBot |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: The complexity of songs. | {{#invoke:WLink|getEscapedTitle|The complexity of songs.}} | {{#invoke:Webarchiv|getdomain|http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2019-05-17 22:19:48 InternetArchiveBot | 2019-05-17 22:19:48 InternetArchiveBot |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: The complexity of songs. | {{#invoke:WLink|getEscapedTitle|The complexity of songs.}} | {{#invoke:Webarchiv|getdomain|http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf}} }} (Memento{{#if: {{#if: 2019-05-17 22:19:48 InternetArchiveBot | 2019-05-17 22:19:48 InternetArchiveBot |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: The complexity of songs. | {{#invoke:WLink|getEscapedTitle|The complexity of songs.}} | {{#invoke:Webarchiv|getdomain|http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf}} }}  
                 }}}}}}}}{{#if:2019-05-17 22:19:48 InternetArchiveBot
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20051226111159|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf}}
    || {{#if:  || }}
  }}{{#if: The complexity of songs.
    | {{#if: {{#invoke:WLink|isBracketedLink|The complexity of songs.}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www.cs.utexas.edu/users/arvindn/misc/knuth_song_complexity.pdf }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} (PDF) In: SIGACT News, Sommer 1977, S. 17–24.
 Reprint in Commun. ACM, 27, no. 4 (1984), S. 344–346, doi:10.1145/358027.358042</ref>

Zusammenfassung

Knuths Artikel eröffnet mit der Beobachtung, dass das 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äten des Gedächtnisses. Als ein einfaches Konzept zur effizienteren Verwaltung von Speicher führt er das Konzept des Refrains ein. In einem ersten Lemma beweist er mit einer 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 (he: {{#invoke:Vorlage:lang|full|CODE=he |SCRIPTING=Hebr}}, ji: ver ken zogn ver ken redn) beweist er die Existenz von Liedern mit 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 {{#invoke:Vorlage:lang|flat}},<ref>Green Grow the Rushes, O (Wikisource)</ref> (auch {{#invoke:Vorlage:lang|flat}}) Alouette,<ref>L’Alouette Liedblatt (Noten, Text, Übersetzung) der Klingenden Brücke</ref> Ist das nicht ein Schnitzelbank und weitere Lieder mit dieser Struktur. Als eine Verbesserung im Koeffizienten diskutiert er die Struktur des Liedes {{#invoke:Vorlage:lang|flat}} ausführlich in einem Lemma.

In einer Untersuchung von Zählreimen anhand des Beispiels von {{#invoke:Vorlage:lang|flat}} konstruiert er Lieder mit logarithmischem 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 Verkettung von Strings und <math>T_k</math> eine Einbettung der natürlichen Zahl <math>k</math> in die englische Sprache. Aufgrund der logarithmischen Zahlendarstellung des Dezimalsystems 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 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 {{#invoke:Vorlage:lang|flat}} der US-amerikanischen Band KC and the Sunshine Band. Die Entwicklung dieser Struktur sieht er durch die Notwendigkeit größerer Liedinstanzen bei minimalem Speicherplatz durch den Fortschritt moderner Drogentechnologie bedingt.<ref group="A">Originalwortlaut: {{#invoke:Vorlage:lang|flat}}</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 offene Problem des Studiums nichtdeterministischer 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 didaktischen 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 />