Diskussion:The Complexity of Songs

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „The Complexity of Songs“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Ein gelungener neuer Artikel! (erl.)

Hallo 0g1o2i3k4e5n6, ein sehr gelungener Artikel, den Du da geschrieben hast – ich drücke Dir beide Daumen, das er auf die Hauptseite kommt! Der Stub in meinem Benutzernamensraum ist inzwischen gelöscht, und ich habe „Über die Komplexität von Liedern“ eben nochmal kurz in den Artikeln „Donald Ervin Knuth“ und „Wissenschaftlicher Witz“ erwähnt, damit dieser Artikel auch etwas leichter aufgefunden werden kann :). Viele Grüße, --Frakturfreund 15:52, 10. Feb. 2010 (CET)

Alles schon mitbekommen ;-) . Merci anyway .--goiken 16:11, 10. Feb. 2010 (CET)

Überarbeiten (erl.)

Zahlreiche Verlinkungen auf BKLs/FS. --Xocolatl 17:39, 10. Feb. 2010 (CET)

Jup.--goiken

??? (erl.)

…und jetzt bitte noch mal für alle, die nicht Mathematik studiert haben. Abgesehen davon, dass hier mathematische Formeln für etwas verwendet werden, für das sie nicht gedacht sind. Was genau sagen diese Formeln eigentlich aus? --93.184.136.17 07:38, 17. Feb. 2010 (CET)

Also, wenn du nicht halbwegs klar umreißen kannst, was dein Verständnisproblem ist, fürchte ich, wird man dir nicht helfen können. Hast du die Landau-Notation halbwegs verstanden und mal in der Einleitung von Komplexitätstheorie gestöbert? --goiken 12:14, 17. Feb. 2010 (CET)

Der Artikel ist halt ein Insiderwitz, Knuth parodiert eben gerade den Formalismus der Komplexitätstheorie, indem er ihn komplett durchexerziert. Von daher wäre es nicht sinnvoll, alle Formeln aus dem Artikel zu entfernen – und richtig lustig kann man ihn wohl nur finden, wenn man mit dieser formalen Sprache wenigstens etwas vertraut ist (was wohl überwiegend auf Informatiker und Mathematiker zutreffen sollte).

Aber im Prinzip sagt die ${\mathcal {O}}$-Notation hier einfach nur aus, wie komplex ein Lied ist, also wie viel Text man sich ungefähr merken muss, um ein Lied der Länge $n$ singen zu können – aber das steht ja schon schöner im Artikel selbst.

Und der etwas längere Formelteil bei den 99 Bottles of Beer ist quasi einfach nur eine Art Bauanleitung für dieses Lied – das wird klarer, wenn Du Dir einmal den vollständigen Liedtext ansiehst, da kommen ziemlich viele Wiederholungen drin vor, Knuths Darstellung ist sozusagen die kurz Möglichste, in der all’ diese Redundanzen entfernt wurden. --Frakturfreund 14:28, 17. Feb. 2010 (CET)

Mein Problem war/ist, dass ich diese ganzen Formeln nicht verstehe. Und wenn ich den Artikel Komplexitätstheorie nur sehe, wird mir schlecht. Wenn die Formeln nicht als "Klartext" übersetzt werden können, werde ich wohl damit leben müssen. Mit ist schon klar, worum es im Prinzip geht. Ich hoffte nur auf eine Erläuterung wie "in dieser Zeile passiert Folgendes...". --93.184.136.17 14:39, 17. Feb. 2010 (CET)

Was passiert, steht direkt darunter. das Zeichen $\ast$ steht für einen Operator, der die Zeichenketten rechts und links von ihm aneinanderhängt. Das nennt man Verkettung. Und was die Variablen bedeuten ist imho auch erklärt. Die stehen für verschiedene Strings. Viel mehr, was man erklären könnte, passiert da gar nicht. --goiken 14:49, 17. Feb. 2010 (CET)

Ach ja, das alte Problem, wenn Nichtmathematiker auf diese merkwürdige Fachsprache aus dem mathematischen Elfenbeinturm treffen … ich würde Dir gerne den Artikel Zugbrücke außer Betrieb von Hans Magnus Enzensberger ans Herz legen (der kommt auch ganz ohne Formeln aus, versprochen!), da wird dieses Problem sehr schön behandelt und von beiden Seiten beleuchtet. Ansonsten bin ich gerne bereit, Dir bei Verständnissſchwierigkeiten zu helfen, um die Zugbrücke wieder herunterzulassen … Du müsstest aber etwas konkreter werden, was genau Du nicht verstehst. --Frakturfreund 14:58, 17. Feb. 2010 (CET)

So, ich habe mich gestern Abend noch mal ausführlich mit der Geschichte beschäftigt und auch den empfohlenen Artikel gelesen (wirklich sehr schön). Und nach dem ich den Formel-Abscheu-Reflex überwunden habe, hab ich es jetzt einigermaßen verstanden. Glaube ich zumindest... Das Ganze läuft auf eine Programmierschleife hinaus wie

1. Setze Strophe mit Anzahl Flaschen = x,

2. Wiederhole Strophe mit Anzahl Flaschen = x-1.

Und weil das Thema hier Komplexität ist, gibt es keine Anweisungen, sondern eine Beschreibung in der speziellen ${\mathcal {O}}$-Notation. Und dieser Komplexitätsfaktor ist dann wohl so etwas wie die Komprimierung. Fast gleiche Strophen = wenig Komplexität = kleiner Komplexitätsfaktor. Soweit alles richtig? --93.184.136.17 07:38, 18. Feb. 2010 (CET)

Der Komplexitätsfaktor sagt, wie stark Textmenge Wächst, die man lernen muss, wenn man sehr lange Lieder singen möchte. Das Lied 99 Bottles ist bis auf den Term $T_{k}$ Konstant. (Also immer gleich) Wenn das Lied sehr groß wird, wird dieser konstante Teil im Verhältnis zum Rest sehr sehr klein, deshalb vernachlässigt man ihn. Wenn ich dann also lerne, wie ich alle natürlichen Zahlen bis zu einer gewissen Schranke singe, hätte ich gelernt, das Lied bis zu dieser Zahl hin zu singen.

Der Aufbau des gebräuchlichsten Zahlensystems ist, dass ich eine Zahl stückweise mit ihren Zehnerpotenzen spezifiziere also die Zahl als $\displaystyle \sum _{i=0}^{k}a_{i}10^{i}$ auffasse und die Koeffizienten $\{a_{0},a_{1},a_{2}\dots a_{k}\}$ aufzähle. Wenn ich $k$ Stellen kenne, habe ich eine Zahl der zwischen $0$ und $10^{k}$ beschrieben. Von der andern Seite heißt das, ich muss $\log(n)$ viele "Worte" Lernen um eine Zahl der Größe $n$ zu singen. Deshalb sagt Knuth, dass das Lied logarithmische Komplexität hat.

Die andern Lieder funktionieren ähnlich. Er sucht sich halt einen sprechlichen Gegenstand, der es erlaubt, dass man wegen eines gewissen Widerholungsmusters, weniger lernen muss, als man singt.

Je stärker die Wiederholung, desto besser das Verhältnis Liedlänge/Lerntext. Nur dass das hier halt kaum eine Verbesserung im eigentlichen Sinne darstellt. Bei Algorithmen macht das wesentlich mehr Sinn, solche Betrachtungen anzustellen: Jeh mehr ich bereits angestellte Berechnungen wiederverwenden kann, desto schneller habe ich ein Ergebnis, desto besser die Methode. --goiken 13:07, 18. Feb. 2010 (CET)

Ok... Komplexität ist also nicht Komprimierung, sondern eher "Verschiedenheit". Nimm "1.000.000 bottles of beer", und es hilft beim Singen auch nicht mehr viel, die eigentliche Strophe zu kennen. Nur in der Notation (und einer späteren mathematischen Verwendung) ist der Unterschied dann gewaltig. Ich denke, die Idee dahinter habe ich jetzt verstanden, wenn auch nicht jeden mathematischen Ausdruck. Vielen Dank für die Erklärungen und die Geduld mit einem fast vollständigen mathematischen Laien. --93.184.136.17 14:35, 18. Feb. 2010 (CET)

Datum (erl.)

Ein Artikel von 1984, der 1977 erstveröffentlicht wurde? Nicht vielleicht doch ein Artikel von 1977, der 1984 nachgedruckt wurde? 194.138.39.59 13:49, 17. Feb. 2010 (CET)

Stimmt, so herum macht das natürlich viel mehr Sinn, ich habe das eben im Artikel korrigiert. Vielen Dank für den Hinweis, --Frakturfreund 14:28, 17. Feb. 2010 (CET)