Donald Knuth — un om de știință în domeniul informaticii, care se îngrijorează atât de mult de corectitudinea cărților sale încât oferă o sută de dolari hexadecimali ($2,56, 0x$1,00) pentru orice „eroare” găsită, unde o eroare este considerată tot ceea ce este „tehnic, istoric, tipografic sau politic greșit”. Mi-a plăcut mult să primesc un cec de la Knuth, așa că am decis să caut erori în opera sa remarcabilă „Arta programării” (TAOCP). Am reușit să găsesc trei. În conformitate cu cuvântul, Knuth mi-a trimis un cec de 0x$3,00.
Așa cum vedeți, acesta nu este un cec adevărat. Cândva, Knuth trimitea cecuri reale, dar a încetat în 2008 din cauza . Acum trimite „certificate de depozit personale” în (BoSS). El spune că este gata să trimită bani reali dacă este necesar, dar, se pare, este prea complicat.
Am găsit două greșeli de tipografie și o greșeală istorică. Le voi enumera în ordine de la cea mai puțin trivială.
Greșeala de tipografie nr. 1
Prima greșeală de tipografie — pe pagina 392 a volumului trei „Sortare și căutare”, a opta linie de jos: „După o căutare nereușită, uneori (sometime) este recomandabil să introduci o nouă înregistrare în tabel care conține K; metoda care face acest lucru se numește algoritm de căutare și inserare. Greșeala este că în loc de sometime ar trebui să fie sometimes.
Desigur, o astfel de greșeală nu este surprinzătoare. Doar în acest articol cu siguranță se vor găsi câteva greșeli de tipografie (fără recompense pentru găsirea lor). Ceea ce este cu adevărat surprinzător este că a fost neremarcată atât de mult timp. Pagina 392 nu este îngropată adânc în secțiunea de matematică, aceasta este cea mai prima pagină a șasea capitol„ Căutare”! Poate unul dintre cele mai citite secțiuni ale cărții. În teorie, acolo ar trebui să fie cele mai puține greșeli de tipografie, dar nu este așa.
Apropo, dacă ai gândit vreodată să citești TAOCP, încearcă. Mulți vor spune că este un ghid, nu destinat citirii directe, dar aceasta nu este adevărat. Autorul are un punct de vedere clar și un stil distinctiv. Singurul lucru care împiedică citibilitatea este complexitatea matematicii. Totuși, există o soluție simplă: citește până ajungi la matematica pe care nu o înțelegi, sări peste ea și deschide următoarea secțiune pe care o poți înțelege. Citind astfel, sar peste cel puțin 80% din carte, dar restul de 20% este minunat!
De asemenea, se spune că TAOCP nu este relevantă, este învechită sau în alt mod inaplicabil programării „reale”. Aceasta este, de asemenea, o minciună. De exemplu, în prima secțiune după introducere se discută despre căutarea unui element într-un tablou nesortat. Cel mai simplu algoritm este cunoscut de toți programatorii. Porniți un pointer la începutul tabloului, apoi efectuați următorii pași într-un ciclu:
- Verificați dacă elementul curent este cel dorit. Dacă da, returnați-l; în caz contrar
- Verificați dacă pointerul este în afara tabloului. Dacă da, returnați o eroare; în caz contrar
- Creșteți pointerul și continuați.
Acum să ne gândim: câte verificări de limită necesită acest algoritm, în medie? În cel mai rău caz, când tabloul nu conține elementul, pentru fiecare element din listă va fi necesară o verificare, iar în medie va fi ceva de genul 
. Un algoritm de căutare mai inteligent poate necesita doar o verificare de limită. Atașați elementul dorit la sfârșitul tabloului, apoi porniți pointerul la începutul tabloului și efectuați următorii pași într-un ciclu:
- Verificați dacă elementul curent este cel dorit. Dacă da, returnați răspunsul, dacă pointerul este în limitele tabloului, sau o eroare, dacă nu este. În caz contrar
- Creșteți pointerul și continuați.
Așa sau altfel, elementul va fi găsit garantat, iar verificarea limitelor se face doar o singură dată, atunci când se întâmplă. Aceasta este o idee profundă, dar suficient de simplă chiar și pentru un programator începător. Probabil că nu pot vorbi despre relevanța lucrării pentru alții, dar am reușit imediat să aplic această înțelepciune atât în codul personal, cât și în cel profesional. Cartea TAOCP este plină de astfel de perle (până la urmă, este plină și de lucruri ciudate, cum ar fi ).
„Căutare, căutare
Atât de mult timp
Căutare, căutare
Eu doar voiam să dansez”
— Luther Vandross, „Căutare” (1980)
Typo #2
A doua greșeală se află în volumul 4A, „Algoritmi combinatori”, partea 1. Pe pagina 60 este descrisă o problemă legată de programarea spectacolelor comediantului în diferite cazinouri. Ca exemplu, sunt menționați câțiva comedianti reali, inclusiv Lily Tomlin, Weird Al Yankovic și Robin Williams, care era încă în viață când cartea a fost publicată. Knuth menționează întotdeauna numele complete în index, astfel încât Williams este menționat pe pagina 882 ca „Williams, Robin Mac-Laurin”. Dar al doilea său prenume se termină cu „n” și nu cu „m”, adică Mac-Laurin.
Mac-Laurin este numele de familie al mamei sale. Ea a fost stră-strănepoata lui Anselm Joseph Mac-Laurin, al 34-lea guvernator al Mississippi-ului. Se pare că mandatul său nu a fost marcat de nimic bun. Din carte :
„Cel mai important eveniment din timpul administrației lui Mac-Laurin a fost declarația de război a Statelor Unite împotriva Spaniei în primăvara anului 1898... Din păcate, războiul a dat poate ocazia unor funcționari publici să practice mită. Mac-Laurin a fost acuzat de diverse practici discutabile, inclusiv nepotism și abuz excesiv de putere în ceea ce privește grațierea. În epoca mișcării pentru temperanță, criticii l-au acuzat pe guvernator de alcoolism, ceea ce el a recunoscut public.”
Eroare istorică
Să examinăm algoritmul tradițional de înmulțire din programa școlară. Câte operații de înmulțire cu un singur digit necesită? Să presupunem că înmulțiți 
-digit number 
pe 
-digit 
. Mai întâi, înmulțiți prima cifră 
cu fiecare cifră 
pe rând. Apoi înmulțiți a doua cifră 
cu fiecare cifră 
pe rând și așa mai departe, până treceți prin toate cifrele 
. Astfel, înmulțirea tradițională necesită 
înmulțiri primitive. În special, înmulțirea a două numere pe 
digit necesită 
înmulțiri cu un singur digit.
Este rău, dar procesul poate fi optimizat printr-o metodă dezvoltată de matematicianul sovietic Anatoliy Alexeyevich Karatsuba. Să presupunem că 
și 
- sunt numere zecimale de două cifre; adică există numere 
, 
, 
, 
astfel încât 
și 
(generalizarea acestui algoritm pentru cifre mai mari necesită anumite manevre; deși nu este foarte complicat, pentru a nu greși în detalii, mai bine rămân la un exemplu simplu). Atunci 
, 
, 
. Înmulțirea binomilor dă 
. Până acum, avem în continuare 
înmulțiri cu un singur digit: 
, 
, 
, 
. Acum să adunăm și să scădem 
. După câteva permutări, pe care le voi lăsa ca exercițiu pentru cititor, se obține 
— doar trei multiplicări de un singur digit! (Există anumiți coeficienți constanți, dar aceștia pot fi calculați doar prin adunare și deplasare de cifre).
Nu cere dovezi, dar algoritmul Karatsuba (generalizat recursiv din exemplul de mai sus) îmbunătățește metoda tradițională de multiplicare cu 
operații până la 
. Așadar, observați că este o îmbunătățire reală a algoritmului, nu o optimizare pentru calcule mentale. De fapt, algoritmul nu este potrivit pentru a fi utilizat în minte, deoarece necesită cheltuieli mari pentru operații recursive. În plus, efectul nu va deveni evident decât când numerele devin suficient de mari (din fericire, în locul algoritmului Karatsuba au apărut metode și mai rapide: în martie 2019 a fost publicat un algoritm care necesită doar multiplicări; accelerarea se aplică doar numerelor atât de mari încât nu sunt imaginabile).
Acest algoritm este descris pe pagina 295 a celui de-al doilea volum „Algoritmi calculați”. Acolo, Knuth scrie: „Este interesant că această idee a fost descoperită abia în 1962 anul”, când a fost publicat un articol care descria algoritmul Karatsuba. Dar! În 1995, Karatsuba a publicat un articol intitulat „Complexitatea calculului”, în care afirmă câteva lucruri: 1) în jurul anului 1956, Kolmogorov a sugerat că multiplicarea nu poate fi efectuată în mai puțin de 
pași; 2) în 1960 anul, Karatsuba a fost prezent la un seminar unde Kolmogorov a expus ipoteza sa n². 3) „Exact în urmă cu o săptămână” Karatsuba a elaborat algoritmul „împarte și stăpânește”; 4) în 1962, Kolmogorov a scris și a publicat un articol în numele lui Karatsuba despre algoritm. „Am aflat despre acest articol doar după ce a fost reprintat.”
Astfel, eroarea constă în faptul că în loc de 1962 trebuie să fie menționat 1960 anul. Asta e tot.
Analiză
Căutarea erorilor nu necesita abilități deosebite.
- Prima eroare a fost atât de banală pe cât se poate, și se afla într-un loc relativ vizibil (începutul capitolului). Orice idiot ar putea să o găsească; doar că eu am fost acel idiot.
- Căutarea celei de-a doua greșeli tipografice a necesitat noroc și dăruire, dar nu abilități. Indexul pentru „Williams” se află pe penultima pagină a volumului, o parte destul de vizibilă a cărții. Tocmai răsfoiam indexul (nu este atât de rău pe cât pare, deoarece în indexurile lui Knuth sunt ascunse ouă de Paște. De exemplu, există înregistrări în arabă și ebraică, ambele indicând pagina 66. Dar pe această pagină nu este menționat niciunul dintre limbile respective; în schimb, se menționează „limbile care se citesc de la dreapta la stânga”). Și atenția mi-a fost atrasă de al doilea nume. Deoarece de obicei citesc Wikipedia, am verificat Robin Williams și am observat o discrepanță.
- Mi-aș dori să pot spune că am făcut o cercetare serioasă pentru a găsi o greșeală istorică, dar de fapt doar am aruncat o privire . În primele linii scrie: „Algoritmul lui Karatsuba este un algoritm de multiplicare rapidă. A fost descoperit de Anatoli Karatsuba în 1960 și publicat în 1962”. După aceasta, nu a mai fost decât să adun două și cu două.
În viitor, mi-aș dori să găsesc o greșeală mai semnificativă, în special în codul lui Knuth. De asemenea, aș dori să găsesc un bug în primul volum „Algoritmi fundamentali”. Poate că aș fi găsit, dar biblioteca locală are dintr-un motiv oarecare doar volumele 2, 3 și 4A.
Fapte financiare:
- În total, contribuția mea la TAOCP constă în doar trei simboluri: o adăugare s, o înlocuire m pe n și 2 pe 0. La prețul de 2,56 USD, acestea sunt simboluri destul de profitabile; dacă ai fi plătit astfel de bani, un articol de 1000 de cuvinte (în medie, aproximativ patru simboluri) ți-ar aduce zece bucurii.
- Cu trei dolari hexazecimale, împreună cu alți 29 de cetățeni, împart locul 69 în lista celor mai bogați contribuitori ai băncii San Serif (la data de 1 mai 2019).
Alte discuții despre cecurile lui Knuth
Recomandări generale pentru găsirea greșelilor în cărțile lui Knuth. Se referă în principal la greșeli tehnice, pe care nu le am. Există o propoziție pe care am luat-o în serios:
Cel mai bine este să aștepți până când ai strâns un set de greșeli pentru a le trimite. Combinând câteva greșeli reale, dar nu foarte valoroase, îți vei crește șansele ca una dintre ele să fie cu adevărat considerată o greșeală sau un sfat. Dacă trimiți greșelile una câte una, fiecare ar putea fi respinsă individual.
Nu am vrut să trimit doar greșeli stupide, așa că am ascultat sfatul și am trimis scrisoarea doar după ce am găsit o eroare istorică care mi s-a părut suficient de gravă.
Ashutosh Mehra este al treilea cel mai bogat investitor în San Serriff cu o avere colosală de 0x$207,f0 în BoSS.
- Divers:
Sursa: habr.com
