Evaluare de dificultate a cântecului

Evaluare de dificultate a cântecului
informatii generale
Autor	Donald Ervin Knuth
Nume	Engleză Complexitatea cântecelor
Data publicării	1977
Publicat în	Comunicările ACM
Volum	27
Eliberare	patru
Pagini	17–24
Licență	proprietate
Identificatori
DOI	10.1145/358027.358042
Text complet
Informații în Wikidata ?

„ The Complexity of Songs ” este un articol publicat de teoreticianul informaticii Donald Knuth în 1977 [1] , care este o „ glumă din interior ” legată de teoria complexității computaționale . Tema principală a articolului este tendința de evoluție a cântecului popular , asociată cu trecerea de la balade lungi și pline de conținut la texte cu grad ridicat de repetare și conținut puțin (sau deloc) semnificativ [2] . Articolul notează că unele melodii pot atinge nivelul de dificultate corespunzător formulei O ( log N ) , unde N este numărul de cuvinte din cântec.

Conținutul articolului

Knuth susține că „strămoșii noștri îndepărtați au inventat conceptul de refren ” pentru a reduce complexitatea spațială a cântecelor, care devine un factor important atunci când un număr mare de cântece trebuie memorate. Lema 1 din lucrare afirmă că dacă lungimea unui cântec este notată cu N , atunci adăugarea unui refren reduce complexitatea cântecului la cN , unde coeficientul c < 1 [1] .

Knuth continuă demonstrând un mod de a construi cântece cu complexitate O ( ), subliniind că această abordare „a fost îmbunătățită ulterior de un fermier scoțian pe nume S. McDonald ” [1] . ${\sqrt N}$

O abordare și mai complexă este dată de cântecele cu complexitate O ( ). Aceasta este clasa de cântece cunoscută sub numele de „ m sticle de bere pe perete ”. $\log N$

În cele din urmă, de-a lungul secolului al XX-lea, progresul, stimulat de faptul că „proliferarea medicamentelor moderne a dus la necesitatea utilizării și mai puține a memoriei” a dus la apariția cântecelor de lungime arbitrară cu O(1) complexitatea spațiului, cum ar fi cântecul definit de: relație recursivă [1] :

S_0=\epsilon, S_k = V_kS_{k-1},\, k\ge 1,

V_k =

„ Așa este ”, „Îmi place” ,

U

U

\pentru toți

k\ge 1

U=

„uh huh”, „uh huh”

Cercetări ulterioare

Profesorul Kurt Eisemann de la Universitatea din San Diego , într-o scrisoare către Communications of the ACM [3] , face îmbunătățiri suplimentare ultimei estimări, aparent de neîmbunătățit, O(1). El începe cu observația că în aplicațiile practice valoarea „constantei ascunse” c în notația mare O poate fi critică, trasând linia dintre acceptabil și inacceptabil: de exemplu, o valoare constantă de 10 80 ar rezulta în cantitatea de informații care depășesc capacitatea oricăruia din mijloacele de stocare a informațiilor cunoscute științei. El mai observă că deja în Europa medievală era cunoscută o tehnică prin care conținutul textual al oricărei melodii arbitrare poate fi descris prin relația de recurență , unde , care dă valoarea constantei c egală cu 2. Totuși, după cum sa dovedit , o altă cultură a atins limita inferioară absolută a complexității O(0)! Profesorul Eisemann spune astfel: $S_k = C_2S_{k-1}$ $C_2 = 'la'$

Când călătorii din Mayflower au aterizat pe acest țărm, nativii americani, mândri de realizările lor în teoria stocării și accesului la informații, i-au salutat la început pe străini cu tăcere deplină. Acesta a fost un mijloc de a transmite cea mai mare realizare a lor în complexitatea cântecului, și anume de a demonstra că limita cea mai inferioară c = 0 este într-adevăr realizabilă.

Text original (engleză)[ arataascunde] Când călătorii Mayflower au coborât pentru prima dată pe aceste țărmuri, nativii americani mândri de realizările lor în teoria stocării și regăsării informațiilor, i-au întâmpinat la început pe străini cu liniște deplină. Acest lucru a fost menit să transmită realizarea lor de vârf în complexitatea cântecelor, și anume demonstrația că o limită la fel de scăzută ca c =0 este într-adevăr obținută.

Totuși, europenii s-au dovedit a fi nepregătiți pentru perceperea acestui concept, iar liderii indieni, pentru a găsi un teren comun pentru transferul realizărilor lor, au demonstrat ulterior abordarea descrisă de relația de recurență , unde , cu o complexitate suboptimă, care dă valoarea c =1 [2] [3] . $S_k = C_1S_{k-1}$ $C_1 = 'i'$

Note

↑ 1 2 3 4
Knuth, D. „The Complexity of Songs”, SIGACT News , vara 1977, 17-24.
- Retipărit în: Knuth, D. „The Complexity of Songs”, Communications of the ACM , 1984, 27 (4) pp. 344-346.
↑ 1 2 Steven Krantz (2005) Mathematical Apocrypha Redux, ISBN 0-88385-554-2 , pp. 2, 3.
↑ 1 2 Kurt Eisemann, „Further Results on the Complexity of Songs”, Communications of the ACM , vol. 28 (1985), nr. 3, p. 235.

Link -uri

„ Complexitatea cântecelor ”, Knuth, Donald E. (1984).
Articol tradus Arhivat 26 februarie 2013 la Wayback Machine .

Donald Knuth
Publicații	Arta de a programa „ Scor de dificultate a cântecului ” Calculatoare și compoziție Matematică concretă Numere suprareale Lucruri un informatician Serii de lucrări alese
Software	Τ Ε Χ MIXAL ( MIX MMIX GNU MDK )
Fonturi	AMS Euler Computer modern METAFONT
Programare competenta	WEB CWEB
Algoritmi	Algoritmul X al lui Knuth Algoritmul de completare Knuth–Bendix Algoritmul Knuth-Morris-Pratt Schimbarea biciului Corespondența Robinson–Schensted–Knuth Algoritmul Trabb Pardo–Knuth
Alte	Legături de dans Verificare recompensă Knuth Premiul Knut test bărbat sau băiat Baza cvater-imaginară -yllion Potrzebie sistem de greutăți și măsuri