Kappaleen vaikeusaste

Kappaleen vaikeusaste
yleistä tietoa
Tekijä	Donald Ervin Knuth
Nimi	Englanti Laulujen monimutkaisuus
Julkaisupäivämäärä	1977
Julkaistu	ACM:n viestintä
Äänenvoimakkuus	27
Vapauta	neljä
Sivut	17-24
Lisenssi	omistusoikeus
Tunnisteet
DOI	10.1145/358027.358042
Koko teksti
Tietoja Wikidatasta ?

" The Complexity of Songs " on tietojenkäsittelytieteen teoreetikon Donald Knuthin vuonna 1977 julkaisema artikkeli [1] , joka on laskennalliseen monimutkaisuusteoriaan liittyvä " sisäinen vitsi " . Artikkelin pääaiheena on suositun kappaleen kehityssuuntaus , joka liittyy siirtymiseen pitkistä ja sisällöllisistä balladeista teksteihin, joissa on paljon toistoa ja vähän (tai ei ollenkaan) merkityksellistä sisältöä [2] . Artikkelissa todetaan, että jotkin kappaleet voivat saavuttaa kaavaa O vastaavan monimutkaisuuden tason ( log N ) , jossa N on kappaleen sanojen lukumäärä.

Artikkelin sisältö

Knuth väittää, että "kaukaiset esi-isämme keksivät kuoron käsitteen " vähentääkseen kappaleiden monimutkaisuutta, mikä on tärkeä tekijä, kun suuri määrä kappaleita on opittava ulkoa. Työn Lemma 1 sanoo, että jos kappaleen pituutta merkitään N , niin kertosäkeen lisääminen vähentää kappaleen monimutkaisuutta arvoon cN , jossa kerroin c < 1 [1] .

Knuth esittelee edelleen tapaa rakentaa O ( ) -monimutkaisia kappaleita ja huomauttaa, että tätä lähestymistapaa "paransi myöhemmin skotlantilainen maanviljelijä nimeltä S. McDonald " [1] . ${\sqrt N}$

Vielä monimutkaisempaa lähestymistapaa antavat kappaleet, joiden monimutkaisuus on O ( ). Tämä on laululuokka, joka tunnetaan nimellä " m pulloa olutta seinällä ". $\log N$

Lopuksi, 1900-luvun aikana edistyminen, jota vauhditti se tosiasia, että "nykyaikaisten huumeiden lisääntyminen on johtanut tarpeeseen käyttää entistä vähemmän muistia", on johtanut mielivaltaisen pituisten kappaleiden syntymiseen O(1) kanssa. avaruuden monimutkaisuus, kuten kappale, jonka määrittelee: rekursiivinen relaatio [1] :

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

V_k =

' Se on tapa ', 'Pidän siitä' ,

U

U

\kaikille

k\ge 1

U=

'öh huh', 'öh huh'

Myöhempi tutkimus

Professori Kurt Eisemann San Diegon yliopistosta tekee kirjeessään Communications of the ACM:lle [3] lisäparannuksia viimeiseen, näennäisesti parantamattomaan arvioon O(1). Hän aloittaa havainnolla, että käytännön sovelluksissa "piilotetun vakion" c arvo suuressa O-merkinnässä voi olla kriittinen, mikä vetää rajan hyväksyttävän ja ei-hyväksyttävän välille: esimerkiksi vakioarvo 10 80 johtaisi Tietoa, joka ylittää minkään tieteen tunteman tiedontallennuskeinon kapasiteetin. Hän huomauttaa lisäksi, että jo keskiaikaisessa Euroopassa tunnettiin tekniikka, jolla minkä tahansa mielivaltaisen melodian tekstisisältöä voidaan kuvata toistuvuussuhteella , jossa , joka antaa vakion c arvon 2. Kuitenkin, kuten kävi ilmi, , toinen kulttuuri saavutti kompleksisuuden absoluuttisen alarajan O(0)! Professori Eisemann ilmaisee asian näin: $S_k = C_2S_{k-1}$ $C_2 = 'la'$

Kun matkustajat Mayflowerista laskeutuivat tälle rannalle, intiaanit, jotka olivat ylpeitä saavutuksistaan tallennusteoriassa ja tiedon saamisessa, tervehtivät ensin muukalaisia täydellisellä hiljaisuudella. Tämä oli keino välittää heidän korkein saavutuksensa kappaleiden monimutkaisuuden suhteen, nimittäin osoittaa, että alin raja c = 0 on todellakin saavutettavissa.

Alkuperäinen teksti (englanniksi)[ näytäpiilottaa] Kun Mayflower -matkailijat laskeutuivat ensimmäistä kertaa näille rannoille, syntyperäiset amerikkalaiset, jotka olivat ylpeitä saavutuksistaan tiedon tallennuksen ja haun teoriassa, toivottivat tuntemattomat ensin täydellisellä hiljaisuudella. Tämän oli tarkoitus välittää heidän huippusaavutuksensa kappaleiden monimutkaisuuden suhteen, nimittäin osoitus siitä, että niinkin alhainen raja kuin c = 0 on todellakin saavutettavissa.

Eurooppalaiset osoittautuivat kuitenkin valmistautumattomiksi näkemään tämän käsitteen, ja intialaiset johtajat, löytääkseen yhteisen perustan saavutustensa siirtämiselle, osoittivat myöhemmin toistumisrelaatiolla kuvattua lähestymistapaa , jossa optimaalisella monimutkaisuudella, joka antaa arvon c =1 [2] [3] . $S_k = C_1S_{k-1}$ $C_1 = 'i'$

Muistiinpanot

↑ 1 2 3 4
Knuth, D. "The Complexity of Songs", SIGACT News , kesä 1977, 17-24.
- Uusintapainos: 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 , s. 2, 3.
↑ 1 2 Kurt Eisemann, "Further Results on the Complexity of Songs", Communications of the ACM , vol 28 (1985), no. 3, s. 235.

Linkit

" The Complexity of Songs ", Knuth, Donald E. (1984).
Käännetty artikkeli Arkistoitu 26. helmikuuta 2013 Wayback Machinessa .

Donald Knuth
Julkaisut	Ohjelmoinnin taito " Laulun vaikeusaste " Tietokoneet ja ladonta Konkreettista matematiikkaa Surrealistisia numeroita Tietojenkäsittelytieteilijän asioita Valitut paperisarjat
Ohjelmisto	Τ Ε Χ MIXAL ( SEK MMIX GNU MDK )
Fontit	AMS Euler Tietokone moderni METAFONT
Osaava ohjelmointi	WEB CWEB
Algoritmit	Knuthin algoritmi X Knuth–Bendix-suoritusalgoritmi Knuth-Morris-Pratt-algoritmi Piiskan sekoitus Robinson-Schensted-Knuthin kirjeenvaihto Trabb Pardo–Knuthin algoritmi
Muut	Tanssivia linkkejä Knuthin palkintosekki Knut-palkinto mies tai poika testi Neljänneksen kuvitteellinen pohja -miljoonaa Potrzebie-järjestelmä painoja ja mittoja