www.wikidata.de-de.nina.az

The Complexity of Songs en de über die Komplexität von Liedern ist ein im Jahre 1977 von dem Informatiker Donald E Knuth

The Complexity of Songs

The Complexity of Songs (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. Die Erstveröffentlichung erfolgte 1977 in SIGACT News, 1984 wurde der Artikel in den Communications of the ACM nachgedruckt.

Zusammenfassung Bearbeiten

Knuths Artikel eröffnet mit der Beobachtung, dass das Singen der meisten Lieder der Länge das Lernen von Text der Länge 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 reduzieren kann.

Im direkten Anschluss analysiert er ein Konzept, das dieses Resultat weiter verbessert: Anhand des Liedes Echad mi jodea (he: אחד מי יודע, ji: ver ken zogn ver ken redn) beweist er die Existenz von Liedern mit asymptotischer Speicherkomplexität von . Als konzeptuell vergleichbar nennt er das Lied Green Grow the Rushes, O, (auch The Dilly Song) Alouette, Ist das nicht ein Schnitzelbank und weitere Lieder mit dieser Struktur. Als eine Verbesserung im Koeffizienten diskutiert er die Struktur des Liedes Old McDonald had a Farm ausführlich in einem Lemma.

In einer Untersuchung von Zählreimen anhand des Beispiels von 99 Bottles of Beer konstruiert er Lieder mit logarithmischem Speicherbedarf, also . Er betrachtet dafür das Schema mit den Versen . dabei setzt er

Dabei ist

ist die Verkettung von Strings und eine Einbettung der natürlichen Zahl 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 mit , das leere Lied, und eine logarithmische Komplexität für große .

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 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 Liedinstanzen bei minimalem Speicherplatz durch den Fortschritt moderner Drogentechnologie bedingt. Er beweist in einem kurzen Argument dessen konstante Komplexität () und schließt sein Papier mit dem Hinweis auf das offene Problem des Studiums nichtdeterministischer Liedstrukturen. (siehe Aleatorik)

Rezeptionen Bearbeiten

In einem Leserbrief an die ACM wies Kurt Eisemann (San Diego State University) auf eine bekannte Verbesserung der Komplexitätsabschätzung hin, indem die wie oben zu betrachten seien. Setzt man , habe man eine Verbesserung der von Knuth vorgeschlagenen Methode um . Eine Komplexität von könne man durch die Nutzung stiller Datenstrukturen erreichen. Darrah Chavey griff Knuths Idee ernsthaft auf, um einen didaktischen Ansatz zur Erläuterung von Methoden der Informatik zu entwickeln.

Anmerkungen Bearbeiten

  1. Zur Notation siehe Landau-Symbol.
  2. Originalwortlaut: However, the advent of modern drugs has led to demands for still less memory space.

Einzelnachweise Bearbeiten

  1. Steven Krantz: Mathematical Apocrypha Redux. 2005, ISBN 0-88385-554-2, S. 2, 3.
  2. Donald E. Knuth: (Memento des Originals vom 26. Dezember 2005 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.cs.utexas.edu (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
  3. Green Grow the Rushes, O (Wikisource)
  4. K. Eisemann, Letter: Further Results on The Complexity of Songs, Comm. ACM, 1985, 28(3), 235.
  5. 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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
The Complexity of Songs en de Uber die Komplexitat von Liedern ist ein im Jahre 1977 von dem Informatiker Donald E Knuth veroffentlichter Fachartikel und wissenschaftlicher Witz Er analysiert darin die Lange von Liedern in Abhangigkeit vom zu lernenden Text mit den Methoden der Komplexitatstheorie Der Artikel polemisiert zudem eine angebliche Tendenz popularer Musik von komplexen Balladen hin zu stark repetitiven Texten beziehungsweise Trivialitat 1 Die Erstveroffentlichung erfolgte 1977 in SIGACT News 1984 wurde der Artikel in den Communications of the ACM nachgedruckt 2 Inhaltsverzeichnis 1 Zusammenfassung 2 Rezeptionen 3 Anmerkungen 4 EinzelnachweiseZusammenfassung BearbeitenKnuths Artikel eroffnet mit der Beobachtung dass das Singen der meisten Lieder der Lange n displaystyle n nbsp das Lernen von Text der Lange n displaystyle n nbsp voraussetzt Bei wachsender Liedzahl strapaziere diese Eigenschaft die Speicherkapazitaten des Gedachtnisses Als ein einfaches Konzept zur effizienteren Verwaltung von Speicher fuhrt er das Konzept des Refrains ein In einem ersten Lemma beweist er mit einer elementaren Rechnung dass dieses Konzept die benotigte Speicherkapazitat um einen konstanten Faktor c lt 1 displaystyle c lt 1 nbsp reduzieren kann Im direkten Anschluss analysiert er ein Konzept das dieses Resultat weiter verbessert Anhand des Liedes Echad mi jodea he אחד מי יודע ji ver ken zogn ver ken redn beweist er die Existenz von Liedern mit asymptotischer Speicherkomplexitat von O n displaystyle mathcal O sqrt n nbsp A 1 Als konzeptuell vergleichbar nennt er das Lied Green Grow the Rushes O 3 auch The Dilly Song Alouette Ist das nicht ein Schnitzelbank und weitere Lieder mit dieser Struktur Als eine Verbesserung im Koeffizienten diskutiert er die Struktur des Liedes Old McDonald had a Farm ausfuhrlich in einem Lemma In einer Untersuchung von Zahlreimen anhand des Beispiels von 99 Bottles of Beer konstruiert er Lieder mit logarithmischem Speicherbedarf also O log n displaystyle mathcal O log n nbsp Er betrachtet dafur das Schema mit den Versen V k displaystyle V k nbsp dabei setzt erV k T k B W T k B If one of those bottles should happen to fall T k 1 B W displaystyle begin aligned V k amp T k ast B ast W ast amp T k ast B ast amp mbox If one of those bottles should happen to fall amp T k 1 ast B ast W ast end aligned nbsp Dabei istB bottles of Beer W on the Wall displaystyle begin aligned B amp mbox bottles of Beer W amp mbox on the Wall end aligned nbsp displaystyle ast nbsp ist die Verkettung von Strings und T k displaystyle T k nbsp eine Einbettung der naturlichen Zahl k displaystyle k nbsp in die englische Sprache Aufgrund der logarithmischen Zahlendarstellung des Dezimalsystems lasst sich so eine Einbettung mit logarithmischem Speicheraufwand konstruieren Offensichtlich haben dann die rekursiv erklarten Lieder L n displaystyle L n nbsp mit L 0 e displaystyle L 0 varepsilon nbsp das leere Lied und L n 1 V n 1 L n displaystyle L n 1 V n 1 ast L n nbsp eine logarithmische Komplexitat fur grosse n N displaystyle n in mathbb N nbsp Dieses Resultat habe sich in allen Situationen die eine Liedgeneration bei begrenztem Speicherplatz erfordern als mehr als ausreichend bewahrt Eine nicht weiter optimierbare Struktur sieht er in dem Song 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 grosserer Liedinstanzen bei minimalem Speicherplatz durch den Fortschritt moderner Drogentechnologie bedingt A 2 Er beweist in einem kurzen Argument dessen konstante Komplexitat O 1 displaystyle mathcal O 1 nbsp und schliesst sein Papier mit dem Hinweis auf das offene Problem des Studiums nichtdeterministischer Liedstrukturen siehe Aleatorik Rezeptionen BearbeitenIn einem Leserbrief an die ACM wies Kurt Eisemann San Diego State University auf eine bekannte Verbesserung der Komplexitatsabschatzung hin indem die L n displaystyle L n nbsp wie oben zu betrachten seien Setzt man V k la displaystyle V k mbox la nbsp habe man eine Verbesserung der von Knuth vorgeschlagenen Methode um c 2 53 0 037736 displaystyle c frac 2 53 0 037736 dots nbsp Eine Komplexitat von O 0 displaystyle mathcal O 0 nbsp konne man durch die Nutzung stiller Datenstrukturen erreichen 4 Darrah Chavey griff Knuths Idee ernsthaft auf um einen didaktischen Ansatz zur Erlauterung von Methoden der Informatik zu entwickeln 5 Anmerkungen Bearbeiten Zur Notation siehe Landau Symbol Originalwortlaut However the advent of modern drugs has led to demands for still less memory space Einzelnachweise Bearbeiten Steven Krantz Mathematical Apocrypha Redux 2005 ISBN 0 88385 554 2 S 2 3 Donald E Knuth The complexity of songs Memento des Originals vom 26 Dezember 2005 im Internet Archive nbsp Info Der Archivlink wurde automatisch eingesetzt und noch nicht gepruft Bitte prufe Original und Archivlink gemass Anleitung und entferne dann diesen Hinweis 1 2 Vorlage Webachiv IABot www cs utexas edu 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 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 S 4 8 doi 10 1145 236452 236475 Abgerufen von https de wikipedia org w index php title The Complexity of Songs amp oldid 237914322