ProHoster > Blog > internetne novice > Od Knuta sem prejel ček za 0 x 3,00 $

Od Knuta sem prejel ček za 0 x 3,00 $

Donald Knuth je računalničar, ki tako zelo skrbi za točnost svojih knjig, da predlaga en hex dolar (2,56 USD, 0x 1,00 USD) za vsako najdeno "napako", pri čemer je napaka opredeljena kot vse, kar je "tehnično, zgodovinsko, tipografsko ali politično nepravilno." Zelo sem želel dobiti ček od Knutha, zato sem se odločil poiskati napake v njegovem magnum opusu "Umetnost programiranja" (TAOCP). Uspelo nam je najti tri. Zvest svoji besedi je Knut poslal ček za 0x 3,00 $.

Od Knuta sem prejel ček za 0 x 3,00 $

Kot lahko vidite, to ni pravi pregled. Knuth je včasih pošiljal prave čeke, vendar je prenehal leta 2008 zaradi divja goljufija. Zdaj pošilja "osebna potrdila o vlogi". Banka San Serriff (BoSS). Pravi, da je pripravljen poslati pravi denar, če bo potrebno, vendar se zdi, da je to prevelik zalogaj.

Našel sem dve tipkarski in eno zgodovinsko napako. Navedel jih bom po padajoči trivialnosti.

Tipkarska napaka #1

Prva tipkarska napaka je na strani 392 tretjega zvezka »Razvrščanje in iskanje«, osma vrstica od spodaj: »Po neuspešnem iskanju je včasih (včasih) zaželeno vnesti nov zapis v tabelo, ki vsebuje K; metoda, ki to počne, se imenuje algoritem iskanja in vstavljanja. Napaka je, da namesto nekje mora biti Včasih.

Seveda takšna napaka ni presenetljiva. Samo v tem članku bo gotovo nekaj tipkarskih napak (brez nagrade, če jih najdete). Resnično presenetljivo je, da je tako dolgo ostalo neopaženo. Stran 392 ni zakopana globoko v matematičnem delu, ampak je čisto prva stran Poglavje XNUMX "Iskanje"! Verjetno eden najbolj branih delov knjige. Teoretično bi moralo biti čim manj tipkarskih napak, a ne.

Mimogrede, če ste kdaj razmišljali o branju TAOCP, poskusite. Mnogi bodo rekli, da je to imenik, ki ni namenjen neposrednemu branju, vendar to ni res. Avtor ima jasno stališče in svojstven slog. Edina stvar, ki ovira berljivost, je zapletenost matematike. Vendar pa obstaja preprosta rešitev: berite, dokler ne pridete do matematike, ki je ne razumete, jo preskočite in pojdite na naslednji razdelek, ki ga razumete. Ob takem branju pogrešam vsaj 80% knjige, ostalih 20% pa je super!

Rečeno je tudi, da TAOCP nepomemben, je zastarel ali kako drugače ni uporaben za "pravo programiranje". Tudi to ne drži. Na primer, prvi razdelek po uvodu obravnava iskanje elementa v nerazvrščenem nizu. Najenostavnejši algoritem poznajo vsi programerji. Zaženite kazalec na začetku matrike, nato pa v zanki naredite naslednje:

  1. Preverite, ali je trenutni element želeni. Če je tako, ga vrnemo; drugače
  2. Preverite, ali je kazalec zunaj meje polja. Če je tako, vrni napako; drugače
  3. Povečaj in nadaljuj.

Zdaj razmislite: koliko preverjanj meja v povprečju zahteva ta algoritem? V najslabšem primeru, ko matrika ne vsebuje elementa, bo vsak element na seznamu zahteval eno preverjanje in v povprečju bo nekaj takega Od Knuta sem prejel ček za 0 x 3,00 $. Pametnejši iskalni algoritem bi se lahko izognil le z enim preverjanjem meja. Pripnite želeni element na konec matrike, nato zaženite kazalec na začetku matrike in naredite naslednje v zanki:

  1. Preverite, ali je trenutni element želeni. Če je tako, vrnemo odgovor, če je kazalec znotraj matrike, ali napako, če ni. V nasprotnem primeru
  2. Povečaj in nadaljuj.

Tako ali drugače je element zagotovljeno najden, preverjanje meja pa se izvede samo enkrat, ko se to zgodi. To je globoka ideja, vendar je dovolj preprosta tudi za programerja začetnika. Verjetno ne morem govoriti o pomembnosti dela za druge, vendar sem lahko to modrost takoj uporabil tako v osebnem kot poklicnem kodeksu. Knjiga TAOCP je polna takšnih draguljev (po pravici povedano, notri je tudi veliko nenavadnih stvari, kot npr. sortiranje mehurčkov).

"Išči, išči
Tako dolgo
Iskanje, iskanje
Hotel sem samo plesati"
— Luther Vandross, "The Search" (1980)

Tipkarska napaka #2

Druga tipkarska napaka je v zvezku 4A, Kombinatorni algoritmi, 1. del. Stran 60 opisuje težavo, ki vključuje načrtovanje komikov za nastope v različnih igralnicah. Kot primeri so navedeni številni komiki iz resničnega življenja, vključno z Lily Tomlin, Weird Al Yankovic in Robinom Williamsom, ki je bil še živ, ko je bila knjiga objavljena. Knuth v indeksu vedno navaja polna imena, zato je Williams na strani 882 naveden kot "Williams, Robin McLorim." Toda njegovo srednje ime se konča z "n" in ne z "m", to je McLaurin.

McLaurin je bil dekliški priimek njegove matere. Bila je pravnukinja Anselma Josepha McLaurina, 34. guvernerja Mississippija. Njegove vladavine si očitno niso zapomnili po ničemer dobrem. Iz knjige "Misisipi: Zgodovina":

»Najpomembnejši dogodek med McLaurinovo administracijo je bila napoved vojne Španiji s strani Združenih držav spomladi 1898 ... Na žalost je vojna nekaterim vladnim uradnikom morda dala priložnost, da se vključijo v podkupovanje. McLaurin je bil obtožen različnih vprašljivih praks, vključno z nepotizmom in pretirano uporabo pooblastil za pomilostitev. Med gibanjem za zmernost so kritiki guvernerja obtožili, da je pijanec, kar je javno priznal.«

Zgodovinska napaka

Razmislite tradicionalni algoritem množenja iz šolskega kurikuluma. Koliko enomestnih množenj zahteva? Recimo, da pomnožite Od Knuta sem prejel ček za 0 x 3,00 $-mestno število Od Knuta sem prejel ček za 0 x 3,00 $ o Od Knuta sem prejel ček za 0 x 3,00 $-bit Od Knuta sem prejel ček za 0 x 3,00 $. Najprej pomnožite prvo števko Od Knuta sem prejel ček za 0 x 3,00 $ za vsako števko Od Knuta sem prejel ček za 0 x 3,00 $ enega po enega. Nato pomnožite drugo števko Od Knuta sem prejel ček za 0 x 3,00 $ za vsako števko Od Knuta sem prejel ček za 0 x 3,00 $ eno za drugo in tako naprej, dokler ne preberete vseh številk Od Knuta sem prejel ček za 0 x 3,00 $. Tako je potrebno tradicionalno množenje Od Knuta sem prejel ček za 0 x 3,00 $ primitivna množenja. Zlasti množenje dveh števil s Od Knuta sem prejel ček za 0 x 3,00 $ potrebnih činov Od Knuta sem prejel ček za 0 x 3,00 $ enomestna množenja.

To je slabo, vendar je mogoče proces optimizirati z metodo, ki jo je razvil sovjetski matematik Anatolij Aleksejevič Karacuba. Pretvarjajmo se, da Od Knuta sem prejel ček za 0 x 3,00 $ и Od Knuta sem prejel ček za 0 x 3,00 $ - dvomestna decimalna števila; to pomeni, da obstajajo številke Od Knuta sem prejel ček za 0 x 3,00 $, Od Knuta sem prejel ček za 0 x 3,00 $, Od Knuta sem prejel ček za 0 x 3,00 $, Od Knuta sem prejel ček za 0 x 3,00 $ tako da Od Knuta sem prejel ček za 0 x 3,00 $ и Od Knuta sem prejel ček za 0 x 3,00 $ (posploševanje tega algoritma na večja števila zahteva nekaj manipulacije; čeprav ni pretežko, se bom raje držal preprostega primera, da ne bi prišlo do napak v podrobnostih). Potem Od Knuta sem prejel ček za 0 x 3,00 $, Od Knuta sem prejel ček za 0 x 3,00 $, Od Knuta sem prejel ček za 0 x 3,00 $. Množenje binomov daje Od Knuta sem prejel ček za 0 x 3,00 $. Trenutno imamo še Od Knuta sem prejel ček za 0 x 3,00 $ enomestno množenje: Od Knuta sem prejel ček za 0 x 3,00 $, Od Knuta sem prejel ček za 0 x 3,00 $, Od Knuta sem prejel ček za 0 x 3,00 $, Od Knuta sem prejel ček za 0 x 3,00 $. Sedaj pa seštevajmo in odštevajmo Od Knuta sem prejel ček za 0 x 3,00 $. Po nekaj preureditvah, ki jih bom pustil kot vajo bralcu, se izkaže Od Knuta sem prejel ček za 0 x 3,00 $ - samo tri enomestna množenja! (Obstaja nekaj stalnih koeficientov, vendar jih je mogoče izračunati samo s seštevanjem in premikanjem števk).

Ne zahtevajte dokazov, ampak algoritem Karatsuba (rekurzivno posplošeno iz zgornjega primera) izboljša tradicionalno metodo množenja z Od Knuta sem prejel ček za 0 x 3,00 $ operacije pred Od Knuta sem prejel ček za 0 x 3,00 $. Upoštevajte, da je to resnična izboljšava algoritma in ne optimizacija za miselne izračune. Algoritem dejansko ni primeren za mentalno aritmetiko, saj zahteva velike režijske stroške za rekurzivne operacije. Poleg tega se učinek ne bo v celoti pokazal, dokler številke ne bodo dovolj velike (na srečo so Karatsubin algoritem nadomestile še hitrejše metode: marca 2019 je bil objavljen algoritem, ki zahteva le n dnevnik n množenja; pospešek velja samo za nepredstavljivo velika števila).

Ta algoritem je opisan na strani 295 XNUMX. zvezka, Polnumerični algoritmi. Tam Knuth piše: »Nenavadno je, da je bila ta ideja odkrita šele v 1962 leto,« ko je bil objavljen članek, ki opisuje Karatsubin algoritem. Ampak! Leta 1995 je Karatsuba objavil članek "Computational Complexity", ki pravi več stvari: 1) okrog leta 1956 je Kolmogorov predlagal, da množenja ni mogoče izvesti v manj kot Od Knuta sem prejel ček za 0 x 3,00 $ koraki; 2) v 1960 leta se je Karatsuba udeležil seminarja, kjer je Kolmogorov predstavil svojo hipotezo n². 3) »V točno enem tednu« je Karatsuba razvil algoritem »deli in vladaj«; 4) leta 1962 je Kolmogorov napisal in objavil članek v imenu Karatsube z opisom algoritma. "Za ta članek sem izvedel šele, ko je bil ponovno objavljen."

Napaka je torej v tem, da namesto 1962 je treba navesti 1960 leto. To je vse.

Analiza

Iskanje napak ni zahtevalo posebne spretnosti.

  1. Prva napaka je bila čim bolj nepomembna in je bila na relativno vidnem mestu (začetek poglavja). Vsak idiot bi ga našel; Pravkar sem izpadel tisti idiot.
  2. Iskanje druge tipkarske napake je zahtevalo srečo in marljivost, ne pa spretnosti. Kazalo za "Williams" je na predzadnji strani zvezka, precej vidnem delu knjige. Ravno sem brskal po kazalu (ni tako patetično, kot se sliši, ker so v Knuthovih kazalih skrita velikonočna jajca. Obstajajo na primer vnosi v arabščini in hebrejščini, oba kažeta na stran 66. Vendar ta stran ne omenja obeh jezikih; namesto tega se nanaša na "jezike, ki se berejo od desne proti levi"). In drugo ime je pritegnilo mojo pozornost. Ker običajno berem Wikipedijo, sem preveril Robina Williamsa in opazil neskladje.
  3. Želim si, da bi lahko rekel, da sem opravil resno raziskavo, da bi našel zgodovinsko napako, a v resnici sem samo pogledal Stran Wikipedije o Karatsubovem algoritmu. Že prve vrstice pravijo: »Algoritem Karatsuba je hiter algoritem množenja. Odkril Anatolij Karacuba leta 1960 in objavil leta 1962." Potem je ostalo samo sešteti dva in dva.

V prihodnosti bi rad našel pomembnejšo napako, zlasti v Knuthovi kodi. Prav tako bi rad našel napako v prvem zvezku Temeljnih algoritmov. Mogoče bi ga našel, toda lokalna knjižnica ima iz nekega razloga le zvezke 2, 3 in 4A.

Finančna dejstva:

  • Skupaj je moj prispevek k TAOCP sestavljen iz samo treh znakov: en dodatek s, zamenjava m o n и 2 o 0. Pri 2,56 $ je to nekaj precej donosnih simbolov; Če bi vam plačali toliko denarja, bi vam članek s 1000 besedami (v povprečju štiri znake) prinesel deset tisočakov.
  • S tremi šestnajstiškimi dolarji sem skupaj z 29 drugimi državljani vezan na 69. mesto na lestvici najbogatejših vlagateljev banke San Serriff Bank (od 1. maja 2019).

Druge razprave o čekih iz Knutha

  • Kako dobiti ček od Knuta

    Splošna priporočila za iskanje napak v Knuthovih knjigah. Večinoma gre za tehnične napake, ki jih jaz nimam. Tam je en predlog, ki sem ga vzel resno:

    Najbolje je, da počakate, da zberete nabor napak, da jih pošljete. S kombiniranjem več resničnih, a ne preveč dragocenih napak, povečate verjetnost, da bo ena od njih dejansko obravnavana kot napaka ali nasvet. Če pošiljate napake eno za drugo, bo lahko vsaka posebej zavrnjena.

    Nisem želel poslati samo nesmiselnih tipkarskih napak, ampak sem upošteval nasvet in poslal pismo šele, ko sem našel zgodovinsko napako, ki se je zdela dovolj resna.

  • Čeki Ashutosha Mehre

    Ashutosh Mehra je tretji najbogatejši vlagatelj v San Serriffu z ogromno neto vrednostjo 0 x 207,f0 $ v BoSS.

  • Preverite nekatere nefunkcionalne napake v pravi kodi TeX
  • Razno: #1 #2 #3 #4 #5 #6

Vir: www.habr.com

Dodaj komentar