Låtens svårighetsgrad

Låtens svårighetsgrad
allmän information
Författare	Donald Ervin Knuth
namn	engelsk Sångernas komplexitet
Publiceringsdatum	1977
Publicerad i	Kommunikation från ACM
Volym	27
Släpp	fyra
Sidor	17–24
Licens	Proprietär
Identifierare
DOI	10.1145/358027.358042
Full text
Information i Wikidata ?

" The Complexity of Songs " är en artikel publicerad av datavetenskapsteoretikern Donald Knuth 1977 [1] , som är ett " insideskämt " relaterat till beräkningskomplexitetsteori . Huvudämnet för artikeln är trenden i utvecklingen av den populära sången , förknippad med övergången från långa och innehållsfyllda ballader till texter med hög grad av upprepning och lite (eller inget) meningsfullt innehåll [2] . Artikeln noterar att vissa låtar kan nå den komplexitetsnivå som motsvarar formeln O ( log N ) , där N är antalet ord i låten.

Artikelns innehåll

Knuth gör påståendet att "våra avlägsna förfäder uppfann konceptet refräng " för att minska sångers rumsliga komplexitet, vilket blir en viktig faktor när ett stort antal sånger måste memoreras. Lemma 1 i tidningen anger att om längden på en sång betecknas med N , så minskar om man lägger till en refräng sångens komplexitet till cN , där koefficienten c < 1 [1] .

Knuth fortsätter med att demonstrera ett sätt att konstruera låtar med O ( ) komplexitet, och påpekar att detta tillvägagångssätt "senare förbättrades av en skotsk bonde vid namn S. McDonald " [1] . ${\sqrt N}$

Ett ännu mer komplext tillvägagångssätt ges av låtar med O ( ) komplexitet. Detta är den klass av låtar som kallas " m flaskor öl på väggen ". $\log N$

Slutligen, under loppet av 1900-talet, har framsteg, som sporrats av det faktum att "spridningen av moderna droger har lett till behovet av ännu mindre minnesanvändning" lett till uppkomsten av sånger av godtycklig längd med O(1) rymdkomplexitet, såsom låten definierad av: rekursiv relation [1] :

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

V_k =

' Det är så ', 'jag gillar det' ,

U

U

\för alla

k\ge 1

U=

'äh va', 'äh va'

Efterföljande forskning

Professor Kurt Eisemann vid University of San Diego gör i ett brev till Communications of the ACM [3] ytterligare förbättringar av den sista, till synes oförbättrbara uppskattningen, O(1). Han börjar med iakttagelsen att i praktiska tillämpningar kan värdet av den "dolda konstanten" c i den stora O-notationen vara kritisk, och drar gränsen mellan acceptabelt och oacceptabelt: till exempel skulle ett konstant värde på 10 80 resultera i mängden information som överstiger kapaciteten för någon av de metoder för informationslagring som är kända för vetenskapen. Han noterar vidare att redan i det medeltida Europa var en teknik känd genom vilken textinnehållet i vilken godtycklig melodi som helst kan beskrivas genom återfallsrelationen , där , vilket ger värdet av konstanten c lika med 2. Men som det visade sig , nådde en annan kultur den absoluta nedre gränsen för komplexitet O(0)! Professor Eisemann uttrycker det så här: $S_k = C_2S_{k-1}$ $C_2 = 'la'$

När resenärer från Mayflower landade på denna strand, hälsade indianerna, stolta över sina prestationer i teorin om lagring och tillgång till information, först främlingar med fullständig tystnad. Detta var ett sätt att förmedla deras högsta prestation i sångkomplexitet, nämligen att visa att den lägsta gränsen c = 0 verkligen är uppnåelig.

Originaltext (engelska)[ visaDölj] När Mayflower -resenärerna först kom ner på dessa stränder, välkomnade indianerna stolta över sin prestation i teorin om informationslagring och -hämtning, först främlingar med fullständig tystnad. Detta var menat att förmedla deras högsta prestation i sångernas komplexitet, nämligen demonstrationen att en så låg gräns som c =0 verkligen går att uppnå.

Emellertid visade sig européerna vara oförberedda på uppfattningen av detta koncept, och de indiska ledarna, för att hitta en gemensam grund för att överföra sina prestationer, visade därefter det tillvägagångssätt som beskrivs av återfallsrelationen , där , med suboptimal komplexitet, vilket ger värdet c =1 [2] [3] . $S_k = C_1S_{k-1}$ $C_1 = 'jag'$

Anteckningar

↑ 1 2 3 4
Knuth, D. "Sångernas komplexitet", SIGACT News , sommaren 1977, 17-24.
- Återtryckt i: Knuth, D. "The Complexity of Songs", Communications of the ACM , 1984, 27 (4) s. 344-346.
↑ 1 2 Steven Krantz (2005) Mathematical Apocrypha Redux, ISBN 0-88385-554-2 , pp. 2, 3.
↑ 1 2 Kurt Eisemann, "Ytterligare resultat på sångernas komplexitet", Communications of the ACM , vol 28 (1985), nr. 3, sid. 235.

Länkar

" The Complexity of Songs ", Knuth, Donald E. (1984).
Översatt artikel Arkiverad 26 februari 2013 på Wayback Machine .

Donald Knuth
Publikationer	Konsten att programmera " Sångsvårighetsscore " Datorer och sättning Konkret matematik Surrealistiska siffror Saker en datavetare Utvalda pappersserier
programvara	Τ Ε Χ MIXAL ( MIX MMIX GNU MDK )
Teckensnitt	AMS Euler Modern dator METAFONT
Kompetent programmering	WEBB CWEB
Algoritmer	Knuths algoritm X Knuth–Bendix kompletteringsalgoritm Knuth-Morris-Pratt-algoritm Vispa blandar Robinson–Schensted–Knuth korrespondens Trabb Pardo–Knuth-algoritm
Övrig	Dansande länkar Knuth belöningscheck Knut Award man eller pojke test Kvartsimaginär bas -yllion Potrzebie system av vikter och mått