Sang sværhedsgrad

Sang sværhedsgrad
generel information
Forfatter	Donald Ervin Knuth
Navn	engelsk Sangenes kompleksitet
Udgivelsesdato	1977
Udgivet i	Kommunikation af ACM
Bind	27
Frigøre	fire
sider	17-24
Licens	proprietære
Identifikatorer
DOI	10.1145/358027.358042
Fuld tekst
Oplysninger i Wikidata ?

" The Complexity of Songs " er en artikel udgivet af datalogisteoretikeren Donald Knuth i 1977 [1] , som er en " indvendig joke " relateret til beregningsmæssig kompleksitetsteori . Artiklens hovedemne er tendensen i udviklingen af den populære sang , forbundet med overgangen fra lange og indholdsfyldte ballader til tekster med høj grad af gentagelse og lidt (eller intet) meningsfuldt indhold [2] . Artiklen bemærker, at nogle sange kan nå den sværhedsgrad, der svarer til formlen O ( log N ) , hvor N er antallet af ord i sangen.

Artiklens indhold

Knuth fremsætter påstanden om, at "vore fjerne forfædre opfandt begrebet omkvæd " for at reducere den rumlige kompleksitet af sange, hvilket bliver en vigtig faktor, når et stort antal sange skal huskes. Lemma 1 i papiret siger, at hvis længden af en sang er angivet med N , så reducerer tilføjelse af et omkvæd sangens kompleksitet til cN , hvor koefficienten c < 1 [1] .

Knuth fortsætter med at demonstrere en måde at konstruere sange med O ( ) kompleksitet på, og påpeger, at denne tilgang "senere blev forbedret af en skotsk landmand ved navn S. McDonald " [1] . ${\sqrt N}$

En endnu mere kompleks tilgang gives af sange med O ( ) kompleksitet. Dette er klassen af sange kendt som " m flasker øl på væggen ". $\log N$

Endelig, i løbet af det 20. århundrede, har fremskridt, ansporet af det faktum, at "udbredelsen af moderne stoffer har ført til behovet for endnu mindre hukommelsesbrug" ført til fremkomsten af sange af vilkårlig længde med O(1) rumkompleksitet, såsom sangen defineret af: rekursiv relation [1] :

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

V_k =

' Det er den måde ', 'jeg kan lide det' ,

U

U

\for alle

k\ge 1

U=

'øh huh' 'øh huh'

Efterfølgende forskning

Professor Kurt Eisemann fra University of San Diego foretager i et brev til Communications of the ACM [3] yderligere forbedringer til det sidste, tilsyneladende uforbedrede skøn, O(1). Han starter med den iagttagelse, at i praktiske anvendelser kan værdien af den "skjulte konstant" c i den store O-notation være kritisk og trækker grænsen mellem acceptabelt og uacceptabelt: for eksempel ville en konstant værdi på 10 80 resultere i mængden af information, der overstiger kapaciteten af nogen fra de midler til informationslagring, som videnskaben kender. Han bemærker endvidere, at man allerede i middelalderens Europa kendte en teknik, hvorved det tekstmæssige indhold af enhver vilkårlig melodi kan beskrives ved gentagelsesrelationen , hvor , som giver værdien af konstanten c lig med 2. Men som det viste sig , nåede en anden kultur den absolutte nedre grænse for kompleksitet O(0)! Professor Eisemann udtrykker det sådan: $S_k = C_2S_{k-1}$ $C_2 = 'la'$

Da rejsende fra Mayflower landede på denne kyst, hilste de indfødte amerikanere, stolte af deres præstationer i teorien om opbevaring og adgang til information, først de fremmede med fuldstændig tavshed. Dette var et middel til at formidle deres højeste præstation i sangkompleksitet, nemlig at demonstrere, at den laveste grænse c = 0 faktisk er opnåelig.

Originaltekst (engelsk)[ Visskjule] Da Mayflower -rejsende første gang kom ned på disse kyster, hilste de indfødte amerikanere stolte over deres præstation i teorien om informationslagring og -hentning, først de fremmede velkommen med fuldstændig stilhed. Dette var beregnet til at formidle deres højeste præstation i sanges kompleksitet, nemlig demonstrationen af, at en grænse så lav som c = 0 faktisk er opnåelig.

Europæerne viste sig imidlertid at være uforberedte på opfattelsen af dette koncept, og de indiske ledere, for at finde et fælles grundlag for at overføre deres præstationer, demonstrerede efterfølgende tilgangen beskrevet af gentagelsesforholdet , hvor , med suboptimal kompleksitet, som giver værdien c =1 [2] [3] . $S_k = C_1S_{k-1}$ $C_1 = 'i'$

Noter

↑ 1 2 3 4
Knuth, D. "The Complexity of Songs", SIGACT News , Summer 1977, 17-24.
- Genoptrykt i: 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, "Yderligere resultater om sanges kompleksitet", Communications of the ACM , bind 28 (1985), nr. 3, s. 235.

Links

" Sanges kompleksitet ", Knuth, Donald E. (1984).
Oversat artikel Arkiveret 26. februar 2013 på Wayback Machine .

Donald Knuth
Publikationer	Kunsten at programmere " Sangsværhedsscore " Computere og sætning Konkret matematik Surrealistiske tal Ting en datamatiker Udvalgte papirserier
Software	Τ Ε Χ MIXAL ( MIX MMIX GNU MDK )
Skrifttyper	AMS Euler Moderne computer METAFONT
Kompetent programmering	WEB CWEB
Algoritmer	Knuths algoritme X Knuth-Bendix færdiggørelsesalgoritme Knuth-Morris-Pratt algoritme Pisk Blanding Robinson–Schensted–Knuth korrespondance Trabb Pardo-Knuth algoritme
Andet	Dansende links Knuth belønning check Knut prisen mand eller dreng test Kvart-imaginær base -yllion Potrzebie system af vægte og mål