Donald Knuth — një shkencëtar në fushën e informatikës, i cili është aq i kujdesshëm për saktësinë e librave të tij sa që ofron një dollar heksadecimal ($2.56, 0x$1.00) për çdo "gabim" të gjetur, ku një gabim përkufizohet si gjithçka që është "teknikisht, historikisht, tipografikisht ose politikisht e gabuar". Unë isha shumë i interesuar të marr një çek nga Knuth, kështu që vendosa të kërkoj gabime në veprën e tij të jashtëzakonshme "Arti i programimit" (TAOCP). Arrita të gjej tri. Vërtet, Knuth më dërgoi një çek për 0x$3.00.
Siç e shihni, kjo nuk është një çek i vërtetë. Më parë, Knuth dërgonte çeqe të vërteta, por e ndali këtë në vitin 2008 për shkak të . Tani ai dërgon "certifikata personale depozite" në (BoSS). Ai thotë se është i gatshëm të dërgojë para të vërteta në rast nevoje, por duket se është shumë e lodhshme.
Gjeta dy gabime shtypi dhe një gabim historik. Do t'i lista ato në rendin e zvogëlimit të trivialitetit.
Gabimi i shtypit nr. 1
Gabimi i parë është në faqen 392 të vëllimit të tretë "Kërkimi dhe renditja", rreshti i tetë nga fundi: "Pas një kërkimi të pasuksesshëm ndonjëherë (sometime) është e dëshirueshme të futet një regjistrim i ri në tabelë, që përmban K; metodi që e bën këtë quhet algoritmi i kërkimit dhe futjes. Gabimi qëndron në faktin se në vend të sometime duhet të jetë sometimes.
Sigurisht, nuk ka asgjë befasuese në një gabim të tillë. Vetëm në këtë artikull padyshim se do të gjenden disa gabime shtypi (pa shpërblime për gjetjen e tyre). Ajo që në të vërtetë është befasuese është se si nuk u vunë re gjatë kaq shumë kohës. Faqja 392 nuk është thellësisht e varrosur në një seksion me matematikë, ajo është faqja më e parë e kapitullit të gjashtë "Kërkimi"! Ndoshta, një nga seksionet më të lexuara të librit. Idealisht, aty duhet të ketë më pak gabime shtypi, por jo.
Për më tepër, nëse keni menduar ndonjëherë të lexoni TAOCP, provoni. Shumë do të thonë se kjo është një udhëzues, i pa përshtatshëm për leximin e drejtpërdrejtë, por kjo është e pavërtetë. Autori ka një pikëpamje të qartë dhe një stil të veçantë. E vetmja gjë që pengon lehtësinë e leximit është kompleksiteti i matematikës. Megjithatë, ka një zgjidhje të thjeshtë: lexoni deri sa të arrini te matematika që nuk kuptoni, kaloni atë dhe hapni seksionin tjetër që mund të kuptoni. Duke lexuar në këtë mënyrë, unë kaloj të paktën 80% të librit, por 20% e tjera janë të mrekullueshme!
Gjithashtu thuhet se TAOCP nuk është relevante, e ka skadohë sa i përket «programimit real». Kjo gjithashtu është e pavërtetë. Për shembull, në seksionin e parë pas hyrjes, shqyrtohet kërkimi i një elementi në një masiv të neshtuar. Algoritmi më i thjeshtë është i njohur për çdo programues. Filloni me treguesin në fillim të masivit, pastaj kryeni hapat e mëposhtëm në një cikël:
- Kontrolloni nëse elementi aktual është ai që dëshironi. Nëse po, e kthejmë; përndryshe
- Kontrolloni nëse treguesi është jashtë masivit. Nëse po, e kthejmë një gabim; përndryshe
- Shtoni treguesin dhe vazhdoni.
Tani le të shqyrtojmë: sa kontrollime kufijesh kërkon ky algoritëm, mesatarisht? Në rastin më të keq, kur masivi nuk përmban elementin, për çdo element në listë do të kërkohet një kontrollim, dhe mesatarisht do të jetë diçka e tillë 
. Një algoritëm më i zgjuar i kërkimit mund të kërkojë vetëm një kontrollim kufiri. Shtoni elementin e dëshiruar në fund të masivit, pastaj filloni me treguesin në fillim të masivit dhe kryeni hapat e mëposhtëm në një cikël:
- Kontrolloni nëse elementi aktual është ai që dëshironi. Nëse po, e kthejmë përgjigjen, nëse treguesi është brenda masivit, ose një gabim, nëse jo. Përndryshe
- Shtoni treguesin dhe vazhdoni.
Kështu ose ndryshe, elementi do të gjendet me siguri, dhe kontrollimi i kufijve bëhet vetëm një herë, kur ndodh kjo. Kjo është një ide e thellë, por mjaft e thjeshtë edhe për programuesit fillestarë. Ndoshta nuk mund të flas për relevancën e këtij punimi për të tjerët, por unë menjëherë e aplikova këtë mençuri si në kodin tim personal ashtu edhe në atë profesional. Libra TAOCP është plot me kushte të tilla (për të qenë të drejtë, ka shumë gjëra të çuditshme aty, si ).
"Kërkim, kërkim
Ka shumë kohë
Kërkim, kërkim
Unë thjesht doja të dansoja"
- Luther Vandross, "Kërkimi" (1980)
Gabimi nr. 2
Gabimi i dytë është në vëllimin 4A, "Algoritmet Kombinatorike", pjesa 1. Në faqen 60 përshkruhet një detyrë për planifikimin e shfaqjeve të komikëve në kazino të ndryshme. Si shembuj përmenden disa komikë të vërtetë, përfshirë Lily Tomlin, Weird Al Yankovic dhe Robin Williams, i cili ishte akoma gjallë kur doli libri. Knuth gjithmonë jep emrat e plotë në indeks, prandaj Williams përmendet në faqen 882 si "Williams, Robin McLaurin". Por emri i tij i dytë përfundon me "n", jo me "m", pra McLaurin.
McLaurin është mbiemri i vajzërisë së nënës së tij. Ajo ishte vashë e Anselm Joseph McLaurin, guvernatori i 34-të i Mississippi. Sundimi i tij, duket, nuk mbeti në kujtesë për ndonjë gjë të mirë. Nga libri :
"Ngjarja më e rëndësishme gjatë administratës së McLaurin ishte shpallja e luftës nga Shtetet e Bashkuara kundër Spanjës në pranverën e vitit 1898… Fatkeqësisht, lufta ndoshta u dha disa zyrtarëve të shtetit mundësinë për të praktikuar korrupsionin. McLaurin u akuzua për praktika të ndryshme të dyshimta, përfshirë nepotizmin dhe përdorimin e tepruar të të drejtave për faljen. Në epokën e lëvizjes për abstinencë, kritikët akuzuan guvernatorin për pirje alkooli, të cilën e pranoi publikisht."
Gabimi Historik
Le të shqyrtojmë algoritmi tradicional i shumëzimit nga programa shkollore. Sa kërkon ai operacione shumëzimi me një cifër? Le të supozojmë se po shumëzoni 
-cifrën e numrit 
në 
-cifrat 
. Së pari, shumëzoni numrin e parë 
me secilën cifër 
një nga një. Pastaj shumëzoni numrin e dytë 
me secilën cifër 
një nga një dhe kështu me radhë, derisa të kaloni të gjitha cifrat 
. Kështu, shumëzimi tradicional kërkon 
shumëzime primitive. Në veçanti, shumëzimi i dy numrave sipas 
cifrave kërkon 
shumëzime me një cifër.
Kjo është keq, por procesi mund të optimizohet me anë të një metode të zhvilluar nga matematikani sovjetik Anatoly Alexeyevich Karatsuba. Le të supozojmë se 
dhe 
- numra dyshifrorë decimalë; pra ekzistojnë numra 
, 
, 
, 
të tillë që 
dhe 
(generalizimi i këtij algoritmi për numra më të mëdhenj kërkon disa manipulime; megjithatë kjo nuk është aq e komplikuar, por për të mos gabuar në detaje, më mirë të qëndroj në shembullin e thjeshtë). Atëherë 
, 
, 
. Shumëzimi i dy binomëve jep 
. Në këtë moment, akoma kemi 
shumëzime me një cifër: 
, 
, 
, 
. Tani, le të shtojmë dhe të heqim 
. Pas disa rregullime, që do t'i lë si një ushtrim për lexuesin, rezulton 
— vetëm tri shumëzime me një shifër! (Ka disa koeficientë konstantë, por ata mund të llogariten vetëm me mbledhje dhe zhvendosje të shifrave).
Mos kërkoni dëshmi, por algoritmi i Karatsubës (i përgjithësuar në mënyrë rekursive nga shembulli i mësipërm) përmirëson metodën tradicionale të shumëzimit nga 
operacionet në 
. Vini re se ky është një përmirësim real i algoritmit, dhe jo optimizim për llogaritjet mendore. Në të vërtetë, algoritmi nuk është i përshtatshëm për llogaritje në mend, pasi kërkon shpenzime të mëdha për operacionet rekursive. Për më tepër, efekti do të shfaqet plotësisht vetëm kur numrat të bëhen mjaft të mëdhenj (për fat, në vend të algoritmit të Karatsubës erdhën metoda edhe më të shpejta: në mars 2019 u publikua një algoritëm që kërkon vetëm shumëzime; përshpejtimi është i aplikuar vetëm për numra të jashtëzakonshëm të mëdhenj).
Ky algoritëm është përshkruar në faqen 295 të vëllimit të dytë "Algoritmet e llogaritur". Atje Knut shkruan: "Është e çuditshme se këtë ide e zbuluan vetëm në 1962 vitin", kur u publikua një artikull që përshkruan algoritmin e Karatsubës. Por! Në vitin 1995, Karatsuba publikoi një artikull "Karakteshimi i llogaritjeve", në të cilin thotë disa gjëra: 1) rreth vitit 1956, Kolmogorov supozoi se shumëzimi nuk mund të kryhet në më pak se 
hapa; 2) në 1960 vitin, Karatsuba mori pjesë në një seminar, ku Kolmogorov paraqiti hipotezën e tij n². 3) "Pikërisht për një javë" Karatsuba zhvilloi algoritmin "ndaje dhe mbizotëro"; 4) në vitin 1962 Kolmogorov shkroi dhe publikoi një artikull në emër të Karatsubës me përshkrimin e algoritmit. "Mësoja për këtë artikull vetëm pasi e ribotuan".
Pra, gabimi është se në vend të 1962 duhet të përmendet 1960 viti. Kaq është gjithçka.
Analiza
Kërkimi i gabimeve nuk kërkonte ndonjë mjeshtëri të veçantë.
- Gabimi i parë ishte aq banal sa mund të jetë, dhe ishte në një vend relativisht të dukshëm (fillimi i kapitullit). Çdo idiot mund ta gjente atë; thjesht unë isha ai idiot.
- Kërkimi i gabimit të dytë kërkonte fat dhe përkushtim, por jo aftësi. Indeksi për "Williams" ndodhet në faqen e parafundit të volumit, një pjesë e konsiderueshme e librit. Pashë pikërisht indeksin (nuk është aq keq sa duket, sepse në indekset e Knuth-it janë të fshehura vezët e Pashkës. Për shembull, ka regjistrime në arabisht dhe hebraisht, dhe të dy tregojnë për faqen 66. Por në këtë faqe nuk përmendet asnjë nga këto gjuhë; përkundrazi, aty përmenden "gjuhet që lexohen nga e djathta në të majtë"). Dhe vëmendjen time tërhoqi emri i dytë. Pasi zakonisht lexoj Wikipedia-n, kontrollova Robin Williams dhe pashë një mosmarrëveshje.
- Dëshiroja të thosha se kam bërë kërkimin serioz për të gjetur një gabim historik, por në të vërtetë thjesht shikova Në rreshtat e parë shkruhet: "Algoritmi i Karatsubës është një algoritëm shumë të shpejtë për shumëzim. U zbulua nga Anatoli Karatsuba në vitin 1960 dhe u publikua në vitin 1962". Pas kësaj, mbetej vetëm të shtosh dy herë dy.
Në të ardhmen do të doja të gjeja një gabim më thelbësor, veçanërisht në kodin e Knuth-it. Do doja gjithashtu të gjeja një gabim në volumit të parë "Algoritmet themelore". Ndoshta do të kisha gjetur, por në bibliotekën lokale për një arsye, ka vetëm volumin 2, 3 dhe 4A.
Fakte financiare:
- Në total, kontributi im në TAOCP përbëhet vetëm nga tre simbole: një shtesë s, zëvendësimi m në n dhe 2 në 0. Me çmimin prej $2,56, këto simbole janë mjaft të leverdishme; nëse do t'ju paguanin kaq shumë, një artikull prej 1000 fjalësh (në mesatare, katër simbole) do t'ju sillte dhjetë copë.
- Me tre dollarë hexadecimal unë së bashku me 29 qytetarë të tjerë ndaj 69 pozita në listën e personave më të pasur që kontribuojnë në bankën San-Seriff (me datë 1 maj 2019).
Diskutime të tjera mbi çekët e Knuth-it
Rregullat e përgjithshme për gjetjen e gabimeve në librat e Knuth-it. Kryesisht lidhen me gabime teknike që nuk i kam. Ka një fjali që e kam marrë seriozisht:
Më mirë të prisni derisa të mbledhni një grup gabimesh për t'i dërguar. Duke bashkuar disa gabime reale, por jo shumë të vlefshme, do të rrisni mundësinë që një nga ato të vlerësohet ose si gabim ose si këshillë. Nëse dërgoni gabime një nga një, çdo njëri mund të refuzohet.
Nuk e kisha dëshirë të dërgoja thjesht gabime të pa rëndësishme, prandaj e ndoqa këshillën dhe dërgova letrën vetëm kur gjetëm një gabim historik, i cili duket mjaft serioz.
Ashutosh Mehra është kontribuuesi i tretë më i pasur në San-Serrif me një pasuri të kolosëshme 0x$207,f0 në BoSS.
- Të ndryshme:
Burimi: habr.com
