Donald Knuth — një shkencëtar në fushën e informatikes, i cili e intereson shumë saktësia e librave të tij, duke ofruar një dollar hexadeci ($2.56, 0x$1.00) për çdo «gabim» të gjetur, ku një gabim konsiderohet gjithçka që është «teknikisht, historikisht, tipografikisht ose politikisht e gabuar». Unë me të vërtetë doja të merrja një çek nga Knuth, kështu që vendosa të kërkoja për gabime në veprën e tij të shkëlqyer «Art i Programimit» (TAOCP). Arrita të gjej tre. Në përputhje me fjalën, Knuth dërgoi një çek për 0x$3.00.
Siç e shihni, ky nuk është një çek i vërtetë. Disa kohë më parë, Knuth dërgonte çekë të vërtetë, por e ndaloi në vitin 2008 për shkak të . Tani ai dërgon «certifikata depoziti personale» në (BoSS). Ai thotë se është gati të dërgojë para të vërteta në rast nevoje, por duket se është shumë e mundimshme.
Gjeta dy gabime tipografike dhe një gabim historik. Do t'i rendit ato sipas rënie triviale.
Gabimi tipografik Nr. 1
Gabimi i parë — në faqe 392 të vëllimit të tretë «Klasifikimi dhe Kërkimi», rreshti i tetë lart: «Pas një kërkimi të pasuksesshëm, ndonjëherë (sometime) është e dëshirueshme të futni një rekord të ri në tabelë, që përmban K; metodi që e bën këtë quhet algoritmi i kërkimit dhe futjes. Problemi është se në vend të ndonjëherë duhet të jetë ndonjëherë.
Sigurisht, nuk ka asgjë të çuditshme në një gabim të tillë. Në këtë artikull do të ketë disa gabime shtypi (s'ka çmime për gjetjen e tyre). Ajo që është vërtet e çuditshme është se nuk janë vënë re për kaq gjatë. Faqja 392 nuk është e fshehur thellë në seksionin për matematikën, kjo është faqja e parë e kapitullit të gjashtë "Kërkimi"! Mund të jetë një nga seksionet më të lexuara të librit. Në teori, aty duhet të ketë më pak gabime, por jo.
Për më tepër, nëse ndonjëherë keni menduar të lexoni TAOCP, provoni. Shumë do të thonë se kjo është një manual, jo e destinuar për lexim të drejtpërdrejtë, por kjo është e vërtetë. Autori ka një pikëpamje të qartë dhe një stil të veçantë. E vetmja gjë që pengon lexueshmërinë është vështirësia e matematikës. Megjithatë, ka një zgjidhje të thjeshtë: lexoni derisa të arrini te matematika që nuk e kuptoni, kaloni atë dhe hapni seksionin tjetër që mund të kuptoni. Duke lexuar kështu, unë kaloj të paktën 80% të librit, por 20% e tjera janë të shkëlqyera!
Po ashtu thuhet se TAOCP nuk është e rëndësishme, është e vjetër ose ndryshe e papërshtatshme për "programimin e vërtetë". Kjo është gjithashtu e pavërtetë. Për shembull, në seksionin e parë pas hyrjes shqyrtohet gjetja e një elementi në një array të pang sorted. Algoritmi më i thjeshtë është i njohur për të gjithë programuesit. Aktivizoni treguesin në fillim të array, pastaj kryeni hapat e mëposhtëm në një cikël:
- Kontrolloni nëse elementi aktual është ai i dëshiruar. Nëse po, e kthejmë atë; në të kundërtën
- Kontrolloni nëse treguesi është jashtë kufijve të array. Nëse po, kthejmë një gabim; në të kundërtën
- Rritni treguesin dhe vazhdoni.
Tani le të shqyrtojmë: sa kontrolle kufij kërkon ky algoritëm, në mesatare? Në rastin më të keq, kur array nuk përmban elementin, për çdo element në listë do të jetë e nevojshme një kontroll, dhe në mesatare do të jetë diçka si 
. Një algoritëm më i mençur i kërkimit mund të ketë vetëm një kontroll kufiri. Shtoni elementin e nevojshëm në fund të array, pastaj aktivizoni treguesin në fillim të array dhe kryeni hapat e mëposhtëm në një cikël:
- Kontrolloni nëse elementi aktual është ai që dëshironi. Nëse është kështu, kthejeni përgjigjen, nëse treguesi është brenda masivit, ose një gabim, nëse nuk është. Përndryshe
- Rritni treguesin dhe vazhdoni.
Në çdo rast, elementi do të gjendet patjetër, dhe kontrolli i kufijve bëhet vetëm një herë, kur ndodh kjo. Kjo është një ide e thellë, por mjaft e thjeshtë, madje edhe për një programist fillestar. Ndoshta nuk mund të flas për rëndësinë e kësaj pune për të tjerët, por unë arrita ta aplikoj këtë mençuri menjëherë në kodin tim personal dhe profesional. Libri TAOCP është plot me perla të tilla (të drejtat e drejtësisë, aty ka shumë gjëra të çuditshme si ).
«Kërkoni, kërkoni
Ka shumë kohë
Kërkoni, kërkoni
Unë thjesht doja të vallzosh»
— Luther Vandross, «Kërkoni» (1980)
Gabimi nr. 2
Gabimi i dytë është në vëllimin 4A, "Algoritmet kombinatorike", pjesa 1. Në faqen 60 përshkruhet një problem rreth planifikimit të paraqitjeve të komikëve në kazino të ndryshme. Si shembuj përmenden disa komikë realë, përfshirë Lily Tomlin, "Weird Al" Yankovic dhe Robin Williams, i cili ishte ende gjallë kur doli libri. Knuth gjithmonë jep emrat e plota në indekse, pra Williams përmendet në faqen 882 si "Williams, Robin Mac-Lorin". Por emri i tij i dytë përfundon me "n", dhe jo me "m", pra Mac-Lorin.
Mac-Lorin është mbiemri i vajzërisë së nënës së tij. Ajo ishte pasardhëse e Anselm Joseph Mac-Lorin, guvernatorit të 34-të të Mississippi. Qeverisja e tij, duket, nuk mbeti në kujtesë për ndonjë gjë të mirë. Nga libri :
«Ngjarja më e rëndësishme gjatë administratës McLorin ishte shpallja e luftës nga Shtetet e Bashkuara ndaj Spanjës në pranverën e vitit 1898… Fatkeqësisht, lufta ndoshta i dha disa zyrtarëve shtetërorë mundësinë për të praktikuar korrupsionin. McLorin u akuzua për praktika të dyshimta, duke përfshirë nepotizmin dhe përdorimin e tepërt të fuqive të faljes. Në epokën e lëvizjes për abstimin, kritikët e akuzuan guvernatorin për alkoolizëm, të cilin ai e pranoi publikisht».
Gabimi historik
Le të shqyrtojmë algoritmi tradicional i shumëzimit nga programi shkollor. Sa operacione njësh eshtë e nevojshme? Supozoni se po shumëzoni 
-numrin me një shifër 
në 
-numëri me një shifër 
. Së pari, shumëzoni shifrën e parë 
me çdo shifër 
në radhë. Pastaj, shumëzoni shifrën e dytë 
me çdo shifër 
në radhë dhe kështu me radhë, derisa të kaloni përmes të gjitha shifrave 
. Kështu, shumzimi tradicional kërkon 
shumëzime primare. Në veçanti, shumëzimi i dy numrave me 
shifra kërkon 
shumëzime njësh.
Kjo është e keqe, por procesin mund ta optimizoni duke përdorur metodën e zhvilluar nga matematicieni sovjetik Anatoly Alexeyevich Karatsuba. Le të supozojmë se 
dhe 
— numrat dhjetorë me dy shifra; pra ekzistojnë numra 
, 
, 
, 
të tillë që 
dhe 
(zgjerimi i këtij algoritmi për numra më të mëdhenj kërkon disa manipulasione; ndonëse kjo nuk është shumë e komplikuar, për të mos gabuar në detaje, do të preferoja të qëndroja në një shembull të thjeshtë). Atëherë 
, 
, 
. Shumëzimi i dy-binëve jep 
. Deri më tani ne ende kemi 
shumëzime një-shifrore: 
, 
, 
, 
. Tani le të shtojmë dhe heqim 
. Pas disa rregullimeve, të cilat do t'i lë si ushtrim për lexuesin, rezulton 
— vetëm tre shumëzime një-shifrore! (Ka disa koeficientë të vazhdueshëm, por ato mund të llogariten vetëm përmes shtimit dhe shifrave të zhvendosura).
Mos kërkoni prova, por algoritmi i Karatsubës (i gjeneruar në mënyrë rekursive nga shembulli i mësipërm) përmirëson metodën tradicionale të shumëzimit nga 
operacione deri në 
. Vini re se është një përmirësim real i algoritmit, e jo një optimizim për llogaritjet në mendje. Në të vërtetë, algoritmi nuk është i përshtatshëm për llogaritjet në mendje, pasi kërkon kosto të mëdha për operacionet rekurzive. Për më tepër, efekti do të shfaqet plotësisht vetëm kur numrat të jenë mjaft të mëdhenj (me fat, në vend të algoritmit të Karatsubës, janë zbuluar metoda edhe më të shpejta: në mars 2019 u publikua një algoritem që kërkon vetëm shumëzimesh; përshpejtimi është i aplikueshëm vetëm për numra të pabesueshëm të mëdhenj).
Ky algoritëm përshkruhet në faqen 295 të volumit të dytë të «Algoritmet e fituara». Aty Knut shkruan: «Është interesante se kjo ide u zbulua vetëm në 1962 vitin», kur u publikua një artikull që përshkruan algoritmin e Karatsubës. Por! Në 1995, Karatsuba publikoi një artikull të titulluar «Kompleksiteti i llogaritjeve», ku ai përmend disa gjëra: 1) rreth vitit 1956 Kolmogorov supozoi se shumzimi nuk mund të realizohet për më pak se 
hapa; 2) në 1960 Në vitin 1962, Karacuba mori pjesë në një seminar ku Kolmogorov paraqiti hipotezën e tij n². 3) "Saktësisht një javë" Karacuba zhvilloi algoritmin "ndaj dhe sundo"; 4) në vitin 1962 Kolmogorov shkroi dhe publikoi një artikull në emër të Karacubës me përshkrimin e algoritmit. "Mora vesh për këtë artikull vetëm pasi e ribotuan".
Kështu, gabimi përbëhet nga fakti që në vend të 1962 duhej të ishte e specifikuar 1960 viti. Këtu e gjithë historia.
Analiza
Kërkimi i gabimeve nuk kërkonte një mjeshtëri të veçantë.
- Gabimi i parë ishte aq banal sa ishte e mundur dhe ndodhej në një vend relativisht të dukshëm (fillimi i kapitullit). Cilido idiot do ta kishte gjetur atë; thjesht, unë isha ai idiot.
- Gjetja e gabimeve të dyta kërkonte fat dhe përpjekje, por jo aftësi. Indeksi për "Williams" ndodhet në faqen parafund e librit, një pjesë e dukshme e librit. Unë po shfletoja saktësisht indeksin (nuk është aq e keqe sa duket, pasi në indekset e Knuth janë fshehur vezë Pashke. Për shembull, atje ka shënime në arabisht dhe hebraisht, dhe të dyja tregojnë tek faqja 66. Por në këtë faqe nuk përmendet asnjë nga këto gjuhë; përkundrazi, përmendet "gjuhët që lexohen nga e djathta në të majtë"). Dhe vëmendja ime u tërhoq nga emri i dytë. Duke qenë se zakonisht lexoj Wikipedian, kontrollova Robin Williams dhe vura re një mosmarrëveshje.
- Do doja të thoja se kam bërë një hulumtim të rëndësishëm 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 për shumim të shpejtë. U zbulua nga Anatol Karatsuba në vitin 1960 dhe u publikua në vitin 1962". Pas kësaj nuk mbetej gjë tjetër vetëm se të shtoja dy herë dy.
Në të ardhmen, do të doja të gjeja një gabim më të rëndësishëm, veçanërisht në kodin e Knuth. Do të doja gjithashtu të gjeja një bug në vëllimin e parë të "Algoritmet Fundamentale". Ndoshta do ta kisha gjetur, por për ndonjë arsye, në bibliotekën 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 simbole: një shtesë s, një zëvendësim m në n dhe 2 në 0. Me një çmim prej $2.56, këto janë simbole mjaft fitimprurëse; nëse do t'ju paguanin kaq para, një artikull prej 1000 fjalësh (në mesatarisht, katër simbole) do t'ju sillte dhjetë të tillë.
- Me tre dollarë hexadecimal, ndajem vendin e 69-të në listën e investitorëve më të pasur të bankës San-Serif, së bashku me 29 qytetarë të tjerë (nga 1 maji 2019).
Diskutime të tjera mbi çekët e Knuth
Udhëzime të përgjithshme për gjetjen e gabimeve në librat e Knuth. Kryesisht përfshijnë gabime teknike që nuk i kam. Ka një fjali atje që e mora seriozisht:
Më mirë është të prisni derisa të mbledhni një grup gabimesh për të dërguar. Duke bashkuar disa gabime reale, por jo shumë të vlefshme, do të rrisni mundësinë që njëra prej tyre të konsiderohet vërtet si gabim ose këshillë. Nëse dërgoni gabime një nga një, çdo njëra mund të refuzohet veç e veç.
Nuk doja të dërgoja thjesht gabime të kota, kështu që e ndoqa këshillën dhe dërgova një letër vetëm kur gjetëm një gabim historik që dukej mjaft serioz.
Ashutosh Mehra është kontribuesi i tretë më i pasur në San-Seriff me një pasuri kolosale 0x$207,f0 në BoSS.
- Të ndryshme:
Burimi: habr.com
