Donald Knuth është një shkencëtar kompjuteri që kujdeset aq shumë për saktësinë e librave të tij, saqë ai sugjeron një hex dollar (2,56$, 0x1,00$) për çdo "gabim" të gjetur, ku një gabim përkufizohet si çdo gjë që është "teknikisht, historikisht, tipografikisht ose politikisht e pasaktë". Doja shumë të merrja një çek nga Knuth, kështu që vendosa të kërkoja gabime në opusin e tij magnum "Arti i programimit" (TAOCP). Arritëm të gjenim tre. Në përputhje me fjalën e tij, Knut dërgoi një çek për 0x3,00 dollarë.

Siç mund ta shihni, ky nuk është një kontroll i vërtetë. Knuth dërgonte çeqe të vërteta, por ndaloi në 2008 për shkak të mashtrim i shfrenuar. Ai tani i dërgon "certifikatat personale të depozitave". Banka e San Serrifit (BoSS). Ai thotë se është i gatshëm të dërgojë para të vërteta nëse është e nevojshme, por duket se është shumë e vështirë.

Kam gjetur dy gabime shtypi dhe një gabim historik. Unë do t'i rendis ato sipas rendit të parëndësisë në rënie.

Gabimi nr. 1

Gabimi i parë tipik është në faqen 392 të vëllimit të tretë të "Sortimi dhe kërkimi", rreshti i tetë nga fundi: "Pas një kërkimi të pasuksesshëm, ndonjëherë (ndonjëherë) është e dëshirueshme të futet një rekord i ri në tabelën që përmban K; metoda që e bën këtë quhet algoritmi i kërkimit dhe futjes. Gabimi është se në vend të kësaj dikur duhet të jetë ndonjëherë.

Sigurisht, një gabim i tillë nuk është befasues. Vetëm në këtë artikull do të ketë disa gabime shtypi (nuk ka shpërblim për gjetjen e tyre). Ajo që është vërtet befasuese është se kaloi pa u vënë re për kaq shumë kohë. Faqja 392 nuk është varrosur thellë në seksionin e matematikës, është faqen e parë Kapitulli 6 "Kërkimi"! Ndoshta një nga pjesët më të lexuara të librit. Në teori, duhet të ketë sa më pak gabime shtypi, por jo.

Meqë ra fjala, nëse keni menduar ndonjëherë të lexoni TAOCP, provojeni. Shumë do të thonë se kjo është direktoria, nuk synohet për lexim të drejtpërdrejtë, por kjo nuk është e vërtetë. Autori ka një këndvështrim të qartë dhe një stil të veçantë. E vetmja gjë që pengon lexueshmërinë është kompleksiteti i matematikës. Sidoqoftë, ekziston një zgjidhje e thjeshtë: lexoni derisa të arrini te matematika që nuk e kuptoni, kalojeni atë dhe shkoni te pjesa tjetër që mund ta kuptoni. Duke lexuar në këtë mënyrë, më mungon të paktën 80% e librit, por 20% e tjera është e mrekullueshme!

Thuhet gjithashtu se TAOCP të parëndësishme, është i vjetëruar ose ndryshe nuk zbatohet për "programimin real". Kjo gjithashtu nuk është e vërtetë. Për shembull, seksioni i parë pas hyrjes shikon gjetjen e një elementi në një grup të pazgjedhur. Algoritmi më i thjeshtë është i njohur për të gjithë programuesit. Filloni treguesin në fillim të grupit, më pas bëni sa më poshtë në një lak:

1. Kontrolloni nëse elementi aktual është ai i dëshiruar. Nëse po, ne e kthejmë atë; ndryshe
2. Kontrolloni nëse treguesi është jashtë kufirit të grupit. Nëse po, ktheni një gabim; ndryshe
3. Zmadhoni dhe vazhdoni.

Tani merrni parasysh: sa kontrolle kufijsh kërkon mesatarisht ky algoritëm? Në rastin më të keq, kur grupi nuk përmban një element, çdo element në listë do të kërkojë një kontroll, dhe mesatarisht do të jetë diçka si . Një algoritëm më i zgjuar kërkimi mund të shpëtojë me vetëm një kontroll të kufijve. Bashkangjisni elementin e dëshiruar në fund të grupit, më pas nisni treguesin në fillim të grupit dhe bëni sa më poshtë në një lak:

1. Kontrolloni nëse elementi aktual është ai i dëshiruar. Nëse po, ne kthejmë një përgjigje nëse treguesi është brenda grupit, ose një gabim nëse nuk është. Përndryshe
2. Zmadhoni dhe vazhdoni.

Në një mënyrë apo tjetër, elementi është i garantuar të gjendet, dhe kontrolli i kufijve kryhet vetëm një herë kur kjo ndodh. Kjo është një ide e thellë, por është mjaft e thjeshtë edhe për një programues fillestar. Ndoshta nuk mund të flas për rëndësinë e punës me të tjerët, por menjëherë arrita ta zbatoja këtë urtësi si për kodin personal ashtu edhe për atë profesional. Libri TAOCP është plot me perlë të tillë (të them të drejtën, aty ka edhe shumë gjëra të çuditshme, si p.sh. lloj flluskë).

"Kërko, kërko
Kaq gjatë
Kërko, kërko
Unë thjesht doja të kërceja"
- Luther Vandross, "Kërkimi" (1980)

Gabimi nr. 2

Gabimi i dytë tipik është në Vëllimin 4A, Algoritme Kombinuese, Pjesa 1. Faqja 60 përshkruan një problem që përfshin planifikimin e humoristëve për të performuar në kazino të ndryshme. Disa humoristë të jetës reale citohen si shembuj, duke përfshirë Lily Tomlin, Weird Al Yankovic dhe Robin Williams, i cili ishte ende gjallë kur u botua libri. Knuth gjithmonë rendit emrat e plotë në indeks, kështu që Williams renditet në faqen 882 si "Williams, Robin McLorim". Por emri i tij i mesëm përfundon me "n" dhe jo "m", domethënë McLaurin.

McLaurin ishte emri i vajzërisë së nënës së tij. Ajo ishte stërmbesa e Anselm Joseph McLaurin, Guvernatori i 34-të i Misisipit. Mbretërimi i tij, me sa duket, nuk u kujtua për asgjë të mirë. Nga libri "Misisipi: Historia":

“Ngjarja më e rëndësishme gjatë administratës së McLaurin ishte shpallja e luftës nga Shtetet e Bashkuara ndaj Spanjës në pranverën e vitit 1898... Fatkeqësisht, lufta mund t'i ketë dhënë disa zyrtarëve qeveritarë mundësinë për t'u përfshirë në ryshfet. McLaurin u akuzua për praktika të ndryshme të dyshimta, duke përfshirë nepotizmin dhe përdorimin e tepruar të kompetencave të faljes. Gjatë lëvizjes së maturisë, kritikët e akuzuan guvernatorin si pijanec, gjë që ai e pranoi publikisht.

Gabim historik

Konsideroj algoritmi tradicional i shumëzimit nga programi shkollor. Sa shumëzime njëshifrore kërkon? Supozoni se ju shumëzoni - numri shifror mbi - bit . Së pari shumëzojeni shifrën e parë për çdo shifër nje nga nje. Pastaj shumëzoni shifrën e dytë për çdo shifër një nga një dhe kështu me radhë derisa të kaloni nëpër të gjithë numrat . Kështu kërkon shumëzimi tradicional shumëzimet primitive. Në veçanti, duke shumëzuar dy numra me gradat e nevojshme shumëzimet njëshifrore.

Kjo është e keqe, por është e mundur të optimizohet procesi duke përdorur një metodë të zhvilluar nga matematikani sovjetik Anatoly Alekseevich Karatsuba. Le të pretendojmë se и  - numra dhjetorë dyshifrorë; dmth ka numra , , , sikurse и (përgjithësimi i këtij algoritmi në numra më të mëdhenj kërkon disa manipulime; megjithëse nuk është shumë e vështirë, për të mos gabuar në detaje, më mirë do t'i përmbahem një shembulli të thjeshtë). Pastaj , , . Shumëzimi i binomeve jep . Për momentin kemi ende shumëzimi njëshifror: , , , . Tani le të mbledhim dhe zbresim . Pas disa rirregullimeve, që do t'i lë si ushtrim për lexuesin, rezulton  - vetëm tre shumëzime njëshifrore! (Ka disa koeficientë konstante, por ato mund të llogariten vetëm duke shtuar dhe zhvendosur shifrat).

Mos kërkoni prova, por Algoritmi Karatsuba (i përgjithësuar në mënyrë rekursive nga shembulli i mësipërm) përmirëson metodën tradicionale të shumëzimit me operacionet më parë . Ju lutemi vini re se ky është një përmirësim i vërtetë i algoritmit, jo një optimizim për llogaritjet mendore. Në të vërtetë, algoritmi nuk është i përshtatshëm për aritmetikë mendore, pasi kërkon kosto të mëdha të përgjithshme për operacione rekursive. Për më tepër, efekti nuk do të shfaqet plotësisht derisa numrat të bëhen mjaft të mëdhenj (për fat të mirë, algoritmi i Karatsuba është zëvendësuar nga metoda edhe më të shpejta: në mars 2019, u publikua një algoritëm që kërkon vetëm n log n shumëzimet; nxitimi vlen vetëm për numra të paimagjinueshëm të mëdhenj).

Ky algoritëm përshkruhet në faqen 295 të Vëllimit XNUMX, Algoritme gjysmë numerike. Aty Knuth shkruan: “Është kurioze që kjo ide u zbulua vetëm në 1962 vit”, kur u botua një artikull që përshkruan algoritmin e Karatsuba. Por! Në vitin 1995, Karatsuba botoi një punim mbi "Kompleksitetin kompjuterik", i cili thotë disa gjëra: 1) Rreth vitit 1956, Kolmogorov sugjeroi që shumëzimi nuk mund të bëhej në më pak se hapa; 2) në 1960 vit Karatsuba mori pjesë në seminarin ku Kolmogorov paraqiti hipotezën e tij n². 3) "Në saktësisht një javë", Karatsuba zhvilloi algoritmin "përça dhe sundo"; 4) në 1962, Kolmogorov shkroi dhe botoi një artikull në emër të Karatsuba me një përshkrim të algoritmit. “Mësova për këtë artikull vetëm pasi u ribotua.”

Pra, gabimi është se në vend të 1962 duhet të specifikohet 1960 vit. Kjo eshte e gjitha.

Analizë

Gjetja e gabimeve nuk kërkonte aftësi të veçanta.

1. Gabimi i parë ishte sa më i parëndësishëm dhe ishte në një vend relativisht të dukshëm (fillimi i kapitullit). Çdo idiot do ta kishte gjetur; Unë thjesht dola të isha ai idiot.
2. Gjetja e gabimit të dytë të shtypit kërkonte fat dhe zell, por jo aftësi. Indeksi për "Williams" është në faqen e parafundit të vëllimit, një pjesë mjaft e spikatur e librit. Sapo po shfletoja indeksin (nuk është aq patetike sa duket, sepse ka vezë të Pashkëve të fshehura në indekset e Knuth-it. Për shembull, ka shënime në arabisht dhe hebraisht, të dyja që tregojnë faqen 66. Por ajo faqe nuk përmend të dyja gjuhët; në vend të kësaj i referohet "gjuhëve që lexohen nga e djathta në të majtë"). Dhe emri i dytë më tërhoqi vëmendjen. Meqenëse zakonisht lexoja Wikipedia, kontrollova Robin Williams dhe vura re një mospërputhje.
3. Do të doja të mund të thosha se bëra një kërkim serioz për të gjetur një gabim historik, por në të vërtetë thjesht shikova Faqja e Wikipedia për algoritmin e Karatsuba. Rreshtat e para thonë: "Algoritmi Karatsuba është një algoritëm i shumëzimit të shpejtë. Zbuluar nga Anatoly Karatsuba në 1960 dhe botuar në 1962." Pas kësaj mbetej vetëm të shtoheshin dy dhe dy.

Në të ardhmen do të doja të gjeja një gabim më domethënës, veçanërisht në kodin e Knuth. Do të doja gjithashtu të gjeja një gabim në vëllimin e parë të Algoritmeve Fundamentale. Ndoshta do ta kisha gjetur, por për disa arsye biblioteka lokale ka vetëm vëllimet 2, 3 dhe 4A.

Faktet financiare:

• Në total, kontributi im në TAOCP përbëhet nga vetëm tre personazhe: një shtesë s, zëvendësim m mbi n и 2 mbi 0. Me 2,56 dollarë, këto janë disa simbole mjaft fitimprurëse; Nëse do të paguheshit kaq para, një artikull prej 1000 fjalësh (mesatarisht katër karaktere) do t'ju fitonte dhjetë euro.
• Me tre dollarë heksadecimal, unë, së bashku me 29 qytetarë të tjerë, renditemi në vendin e 69-të në listën e depozituesve më të pasur të Bankës San Serriff (që nga 1 maji 2019).

Diskutime të tjera rreth çeqeve nga Knuth

• Si të merrni një çek nga Knuth

  Rekomandime të përgjithshme për gjetjen e gabimeve në librat e Knuth. Kryesisht kanë të bëjnë me gabime teknike, të cilat unë nuk i kam. Ka një sugjerim që e mora seriozisht:

  Është më mirë të prisni derisa të keni mbledhur një sërë gabimesh për t'u paraqitur. Duke kombinuar disa gabime reale, por jo shumë të vlefshme, ju rritni gjasat që njëri prej tyre të konsiderohet në të vërtetë si një gabim ose këshillë. Nëse dorëzoni gabime një nga një, secili individualisht mund të refuzohet.

  Nuk doja të dërgoja thjesht gabime të pakuptimta, por mora këshillën dhe dërgova letrën vetëm kur gjeta një gabim historik që më dukej mjaft serioz.

• Çeqet e Ashutosh Mehrës

  Ashutosh Mehra është investitori i tretë më i pasur në San Serriff me një vlerë të madhe neto prej 0x207.f0$ në BoSS.

• Kontrolloni për disa gabime jofunksionale në kodin real TeX
• Të Ndryshme: #1 #2 #3 #4 #5 #6

Burimi: www.habr.com