Donald Knuth — znanstvenik na področju informatike, ki tako zelo skrbi za pravilnost svojih knjig, da ponuja eno šesterično dolar ($2,56, 0x$1,00) za vsako najdeno "napako", pri kateri šteje vse, kar je "tehnično, zgodovinsko, tipografsko ali politično napačno". Zelo sem želel prejeti ček od Knutha, zato sem se odločil poiskati napake v njegovem izjemnem delu "Kunst programiranja" (TAOCP). Uspelo mi je najti tri. Po resnici povedano, Knuth mi je poslal ček v višini 0x$3,00.
Kot vidite, to ni pravi ček. V preteklosti je Knuth pošiljal prave čeke, a je to prenehal početi leta 2008 zaradi . Zdaj pošilja "osebne depozitne certifikate" v (BoSS). Pravi, da je pripravljen poslati prave denarje v primeru potrebe, vendar se zdi, da je to preveč zapleteno.
Našel sem dve tipkarski napaki in eno zgodovinsko napako. Naštel jih bom po vrstnem redu manjše trivialnosti.
Tipkarska napaka št. 1
Prva tipkarska napaka je na strani 392 tretjega toma "Razvrščanje in iskanje", osma vrstica od spodaj: "Po neuspelem iskanju je včasih (sometime) priporočljivo v tabelo vnesti novo zapis, ki vsebuje K; metoda, ki to stori, se imenuje algoritem iskanja in vstavljanja. Napaka je v tem, da bi namesto sometime moralo biti sometimes.
Seveda v taki napaki ni nič presenetljivega. Le v tem članku se gotovo najde nekaj tipkarskih napak (brez nagrad za njihovo iskanje). To, kar je v resnici presenetljivo, pa je, da jih ni nihče opazil tako dolgo. Stran 392 ni globoko zakopana v oddelek z matematiko, to je prva stran šeste poglavja "Iskanje"! Morda en izmed najbolj branih delov knjige. Po logiki bi tam moralo biti najmanj tipkarskih napak, vendar ni.
Mimogrede, če ste kdaj pomislili, da bi prebrali TAOCP, poskusite. Mnogi bodo rekli, da je to priročnik, ki ni namenjen neposrednemu branju, a 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, preskočite jo in odprite naslednji odsek, ki ga lahko razumete. Tako pri branju preskočim vsaj 80% knjige, toda preostalih 20% je čudovitih!
Prav tako pravijo, da je TAOCP nerelevantna, zastarela ali na drug način neprimenljiva na „stvarno programiranje“. To takođe nije tačno. Na primer, u prvom delu nakon uvoda razmatra se pretraživanje elementa u nesortiranom nizu. Najjednostavniji algoritam je poznat svim programerima. Pokrenite pokazivač na početku niza, a zatim uradite sledeće u petlji:
- Proverite da li je trenutni element željeni. Ako jeste, vraćamo ga; u suprotnom,
- Proverite da li je pokazivač van granica niza. Ako jeste, vraćamo grešku; u suprotnom,
- Povećajte pokazivač i nastavite.
Sada razmislimo: koliko provere granica zahteva ovaj algoritam, u proseku? U najgorem slučaju, kada niz ne sadrži element, za svaki element na listi biće potrebna jedna provera, i u proseku će to biti nešto poput 
. Pametniji algoritam pretrage može da prođe sa samo jednom proverom granica. Priključite željeni element na kraj niza, zatim pokrenite pokazivač na početku niza i uradite sledeće u petlji:
- Proverite da li je trenutni element željeni. Ako jeste, vraćamo odgovor, ako je pokazivač unutar granica niza, ili grešku, ako nije. U suprotnom,
- Povećajte pokazivač i nastavite.
Bilo kako bilo, element će sigurno biti pronađen, a provera granica se vrši samo jednom, kada se to dogodi. To je duboka ideja, ali je dovoljno jednostavna čak i za početnika programera. Verovatno ne mogu govoriti o relevantnosti posla za druge, ali sam odmah uspeo da primenim ovu mudrost i u ličnom i u profesionalnom kodu. Knjiga TAOCP je puna takvih dragulja (da budemo pošteni, ima tu i mnogo čudnih stvari, poput ).
„Pretraga, pretraga
Toliko dugo
Pretraga, pretraga
Samo sam hteo da plešem“
— Luther Vandross, „Pretraga“ (1980)
Greška br. 2
Druga napaka je v zvezku 4A, „Kombinatorni algoritmi“, del 1. Na strani 60 je opisana naloga načrtovanja nastopov komikov v različnih igralnicah. Kot primer je navedenih nekaj realnih komikov, vključno z Lily Tomlin, Weird Al Yankovic in Robinom Williamsom, ki je bil še živ, ko je knjiga izšla. Knuth vedno v kazalo vključuje polna imena, zato je Williams omenjen na strani 882 kot „Williams, Robin Mac-Lorin“. Vendar se njegovo drugo ime konča na „n“, ne na „m“, torej Mac-Lorin.
Mac-Lorin je dekliška priimek njegove mame. Bila je pravnukinja Anselma Josepha Mac-Lorina, 34. guvernerja Mississippija. Njegovo vladanje naj bi se očitno zapomnilo po ničemer dobrem. Iz knjige :
„Najpomembnejši dogodek v času uprave Mac-Lorina je bilo napovedovanje vojne Španiji s strani Združenih držav spomladi 1898… Na žalost je vojna morda nekaterim državnim uslužbencem dala priložnost za prakso podkupovanja. Mac-Lorina so obtožili različnih dvomljivih praks, vključno s kumovstvom in pretirano uporabo pooblastil za pomilostitev. V dobi gibanja za treznost so ga kritiki obtožili alkoholizma, kar je tudi javno priznal.“
Zgodovinska napaka
Razmotrimo tradicionalni algoritem množenja iz šolske programe. Koliko enomestnih množenj zahteva? Recimo, da množite 
-mestno število 
na 
-mestno 
. Najprej pomnožite prvo številko 
z vsako številko 
zaporedoma. Nato pomnožite drugo številko 
z vsako številko 
zaporedoma in tako naprej, dokler ne preučite vseh številk 
. Tako tradicionalno množenje zahteva 
enostavnih množenj. Zlasti množenje dveh števil po 
mestih zahteva 
enomestna množenja.
To je slabo, vendar lahko proces optimiziramo s metodo, ki jo je razvil sovjetski matematik Anatolij Alekseevič Karacub. Predpostavimo, da 
in 
so dvomestna decimalna števila; torej obstajajo števila 
, 
, 
, 
taka, da 
in 
(posploševanje tega algoritma na večje številke zahteva določene manipulacije; čeprav to ni pretežko, vendar da se ne zmedem v podrobnostih, se bom raje držal enostavnega primera). Potem 
, 
, 
. Množenje dvokratnikov daje 
. Do sedaj imamo še vedno 
enomestnih množenj: 
, 
, 
, 
. Zdaj seštejmo in odštejmo 
. Po več presenetljivih spremembah, ki jih pustim kot vajo za bralca, dobimo 
— skupno tri enostavne množenja! (Obstajajo nekateri stalni koeficienti, a ti se lahko izračunajo le z Seštevanjem in premikom mest.)
Ne zahtevajte dokazov, toda Karatsuba algoritem (rekurzivno splošen iz zgoraj navedenega primera) izboljša tradicionalno množenje z 
operacijami do 
. Upoštevajte, da gre za pravo izboljšavo algoritma in ne optimizacijo za ročne izračune. Dejansko algoritem ni primeren za ročne izračune, saj zahteva velike stroške rekurzivnih operacij. Poleg tega se učinek ne bo v celoti pokazal, dokler številke ne postanejo dovolj velike (na srečo so se nad algoritmom Karatsube pojavile še hitrejše metode: marca 2019 je bil objavljen algoritem, ki potrebuje le množenj; pospešek velja le za neverjetno velike številke).
Ta algoritem je opisan na strani 295 drugega toma "Knjiga algoritmov". Tam Knuth piše: "Zanimivo je, da so to idejo odkrili šele v 1962 tem letu", ko je bila objavljena naloga, ki opisuje algoritem Karatsuba. Ampak! Leta 1995 je Karatsuba objavil članek "Zloženost izračunov", v katerem pravi več stvari: 1) okrog leta 1956 je Kolmogorov predpostavil, da množenja ni mogoče izvesti v manj kot 
korakih; 2) v 1960 tem letu je bil Karatsuba prisoten na seminarju, kjer je Kolmogorov predstavil svojo hipotezo n². 3) "Natančno teden dni kasneje" je Karatsuba razvil algoritem "deli in vladaj"; 4) leta 1962 je Kolmogorov napisal in objavil članek v imenu Karatsuba z opisom algoritma. "O tem članku sem izvedel šele potem, ko so ga ponovno objavili."
Tako napaka izhaja iz tega, da namesto 1962 mora biti naveden 1960 leto. To je vse.
Analiza
Iskanje napak ni zahtevalo posebnega znanja.
- Prva napaka je bila tako banala, kot je to mogoče, in se je nahajala na razmeroma vidnem mestu (začetek poglavja). Kdor koli bi jo našel; jaz pa sem bil tisti idiot.
- Iskanje druge napake je zahtevalo srečo in trud, a ne spretnosti. Indeks za "Williamsa" se nahaja na predzadnji strani zvezka, kar je precej opazna del knjige. Pravkar sem prelistaval indeks (to ni tako žalostno, kot se zdi, saj so v indeksih Knutha skriti pirhi. Na primer, tam so zapisi v arabščini in hebrejščini, ki se oba nanašata na stran 66. A na tej strani noben od jezikov ni omenjen; namesto tega so omenjeni "jeziki, ki se berejo z desne proti levi"). Moje oči so pritegnili drugo ime. Ker običajno berem Wikipedijo, sem preveril Robina Williamsa in opazil neskladje.
- Rad bi rekel, da sem opravil resno raziskavo, da bi našel zgodovinsko napako, a v resnici sem bil le na . V prvih stavkih piše: "Karatsubov algoritem je algoritem hitrega množenja. Odkrit leta 1960 od Anatolija Karatsube in objavljen leta 1962." Po tem je ostalo le še sešteti dva in dva.
V prihodnosti bi rad našel bolj pomembno napako, še posebej v Knuthovem kodi. Prav tako bi rad našel napako v prvem zvezku "Temeljni algoritmi". Morda bi jo tudi našel, a v lokalni knjižnici iz nekega razloga imajo le zvezke 2, 3 in 4A.
Finančne dejstva:
- Na splošno je moj prispevek v TAOCP sestavljen le iz treh simbolov: ene dodane s, zamenjave m na n in 2 na 0. Po ceni 2,56 USD so to precej dobičkonosni simboli; če bi vam plačali toliko denarja, bi vam članek dolžine 1000 besed (v povprečju štirje simboli) prinesel deset.
- S tremi hex dolarji skupaj z 29 drugimi državljani delim 69. mesto na seznamu najbogatejših vlagateljev banke San-Serriff (k 1. maju 2019).
Druge razprave o čekih od Knutha
Splošna priporočila za iskanje napak v knjigah Knutha. Večinoma se nanašajo na tehnične napake, katerih nimam. Obstaja en stavek, ki sem ga vzel resno:
Raje počakajte, da zberete komplet napak za pošiljanje. S povezovanjem več resničnih, čeprav ne zelo dragocenih napak, boste povečali verjetnost, da bo ena od njih resnično obravnavana kot napaka ali nasvet. Če pošiljate napake eno za drugo, lahko vsako posebej zavrnejo.
Nisem želel pošiljati preprosto trapastih napak, ampak sem upošteval nasvet in poslal pismo šele, ko sem našel zgodovinsko napako, ki se je zdela dovolj resna.
Ašutosh Mehra je tretji najbogatejši vlagatelj v San-Serriffu z ogromnim premoženjem 0x$207,f0 v BoSS.
- Različno:
Izvor: habr.com
