La complexité des chansons - The Complexity of Songs

" The Complexity of Songs " est un article de journal publié par l' informaticien Donald Knuth en 1977, comme une blague sur la théorie de la complexité computationnelle . L'article capitalise sur la tendance des chansons populaires à passer de longues ballades riches en contenu à des textes très répétitifs avec peu ou pas de contenu significatif. L'article note qu'une chanson de longueur N mots peut être produite en se rappelant, par exemple, seulement O ( log N ) mots (« complexité spatiale » de la chanson).

Résumé de l'article

Knuth écrit que «nos anciens ancêtres ont inventé le concept de refrain » pour réduire la complexité spatiale des chansons, ce qui devient crucial lorsqu'un grand nombre de chansons doit être conservé dans sa mémoire . Le lemme 1 de Knuth indique que si N est la longueur d'une chanson, alors le refrain diminue la complexité de la chanson à cN , où le facteur  c  <1.

Knuth démontre en outre une manière de produire des chansons avec une complexité O ( ), une approche "encore améliorée par un fermier écossais nommé O. MacDonald ". ${\ displaystyle {\ sqrt {N}}}$

Des approches plus ingénieuses donnent des chansons de complexité O ( ), une classe connue sous le nom de " m bouteilles de bière sur le mur ". ${\ displaystyle \ log N}$

Enfin, les progrès du XXe siècle - stimulés par le fait que «l'avènement des drogues modernes a conduit à des demandes de mémoire encore moins» - conduisent à une amélioration ultime: il existe des chansons arbitrairement longues avec une complexité spatiale O (1), ex. chanson définie par la relation de récurrence

${\ displaystyle S_ {0} = \ epsilon, S_ {k} = V_ {k} S_ {k-1}, \, k \ geq 1,}$

${\ displaystyle V_ {k} =}$ «C'est ainsi , » Je l' aime » , pour tous ${\ displaystyle U}$${\ displaystyle U}$${\ displaystyle k \ geq 1}$

${\ displaystyle U =}$ 'euh huh,' 'uh huh'

Développements ultérieurs

Le professeur Kurt Eisemann de l'Université d'État de San Diego dans sa lettre aux Communications de l'ACM améliore encore cette dernière estimation apparemment imbattable. Il commence par une observation selon laquelle, pour des applications pratiques, la valeur de la "constante cachée" c dans la notation Big Oh peut être cruciale pour faire la différence entre la faisabilité et l'impossibilité: par exemple, une valeur constante de 10 ⁸⁰ dépasserait la capacité de tout appareil connu. Il remarque en outre qu'une technique a déjà été connue en Europe médiévale par laquelle le contenu textuel d'une mélodie arbitraire peut être enregistré en se basant sur la relation de récurrence , où , donnant la valeur de la grande constante Oh c égale à 2. Cependant, il s'avère que une autre culture a atteint la limite inférieure absolue de O (0). Comme le dit le professeur Eisemann: ${\ displaystyle S_ {k} = C_ {2} S_ {k-1}}$${\ displaystyle C_ {2} = 'la'}$

«Lorsque les voyageurs de Mayflower sont descendus pour la première fois sur ces côtes, les Amérindiens fiers de leur réussite dans la théorie du stockage et de la récupération de l'information, ont d'abord accueilli les étrangers dans un silence complet. Cela visait à exprimer leur accomplissement maximal dans la complexité des chansons , à savoir la démonstration qu'une limite aussi basse que c  = 0 peut effectivement être obtenue. "

Cependant, les Européens n'étaient pas préparés à saisir cette notion, et les chefs , afin d'établir un terrain d'entente pour transmettre leurs réalisations, ont ensuite procédé à la démonstration d'une approche décrite par la relation récurrente , où , avec une complexité sous-optimale donnée par c  = 1. ${\ displaystyle S_ {k} = C_ {1} S_ {k-1}}$${\ displaystyle C_ {1} = 'i'}$

Le résultat de la complexité spatiale O (1) a également été mis en œuvre par Guy L. Steele, Jr. , peut-être contesté par l'article de Knuth. TELNET Song du Dr Steele a utilisé un algorithme complètement différent basé sur la récursion exponentielle, une parodie de certaines implémentations de TELNET.

Il a été suggéré que l'analyse de la complexité des chants humains peut être un outil pédagogique utile pour enseigner la théorie de la complexité aux élèves.

L'article «Sur les fonctions sous- exponentielles superpolylogarithmiques » du professeur Alan Sherman écrit que l'article de Knuth était fondamental pour l'analyse d'une classe spéciale de fonctions.

Les références

Liens externes

• " La complexité des chansons ", Knuth, Donald E. (1984).