Donald Knuth este un informatician căruia îi pasă atât de mult de acuratețea cărților sale pe care le sugerează un dolar hexagonal (2,56 USD, 0x1,00 USD) pentru orice „eroare” găsită, unde o eroare este definită ca orice „incorect din punct de vedere tehnic, istoric, tipografic sau politic”. Îmi doream foarte mult să obțin un cec de la Knuth, așa că am decis să caut erori în opera lui magistrală „Arta programarii” (TAOCP). Am reușit să găsim trei. Fidel cuvântului său, Knut a trimis un cec pentru 0x3,00 USD.

După cum puteți vedea, acesta nu este o verificare reală. Knuth trimitea cecuri reale, dar s-a oprit în 2008 din cauza fraudă rampantă. El trimite acum „certificate personale de depozit” către Banca din San Serriff (Șef). Spune că este dispus să trimită bani reali dacă este necesar, dar se pare că este prea multă bătaie de cap.

Am găsit două greșeli de scriere și o eroare istorică. Le voi enumera în ordinea descrescătoare a trivialității.

Greșeală de tipar #1

Prima greșeală de tipar se află la pagina 392 a celui de-al treilea volum din „Sortarea și căutarea”, al optulea rând de jos: „După o căutare nereușită, uneori (uneori) este de dorit să introduceți o înregistrare nouă în tabelul care conține K; metoda care face acest lucru se numește algoritmul de căutare și inserare. Greșeala este că în schimb cândva trebuie să fie uneori.

Desigur, o astfel de greșeală nu este surprinzătoare. Numai în acest articol vor exista câteva greșeli de scriere (nicio recompensă pentru găsirea lor). Ceea ce este cu adevărat surprinzător este că a trecut neobservat atât de mult timp. Pagina 392 nu este îngropată adânc în secțiunea de matematică, așa este chiar prima pagină Capitolul XNUMX „Căutare”! Posibil una dintre cele mai citite secțiuni ale cărții. În teorie, ar trebui să existe cele mai puține greșeli de scriere, dar nu.

Apropo, dacă v-ați gândit vreodată să citiți TAOCP, încercați. Mulți vor spune că asta este director, nu este destinat citirii directe, dar acest lucru nu este adevărat. Autorul are un punct de vedere clar și un stil distinctiv. Singurul lucru care împiedică lizibilitatea este complexitatea matematicii. Totuși, există o soluție simplă: citește până când ajungi la matematică pe care nu o înțelegi, sări peste ea și mergi la următoarea secțiune pe care o poți înțelege. Citind astfel, mi-e dor de cel puțin 80% din carte, dar celelalte 20% sunt grozave!

Se mai spune că TAOCP irelevant, este depășit sau nu se aplică în alt mod „programării reale”. Nici acest lucru nu este adevărat. De exemplu, prima secțiune după introducere se uită la găsirea unui element într-o matrice nesortată. Cel mai simplu algoritm este familiar tuturor programatorilor. Porniți indicatorul la începutul matricei, apoi faceți următoarele într-o buclă:

1. Verificați dacă elementul curent este cel dorit. Dacă da, îl returnăm; in caz contrar
2. Verificați dacă pointerul se află în afara limitei matricei. Dacă da, returnați o eroare; in caz contrar
3. Măriți și continuați.

Acum luați în considerare: câte verificări de limite necesită acest algoritm, în medie? În cel mai rău caz, în care matricea nu conține un element, fiecare element din listă va necesita o verificare și, în medie, va fi ceva de genul . Un algoritm de căutare mai inteligent ar putea scăpa cu o singură verificare a limitelor. Atașați elementul dorit la sfârșitul matricei, apoi porniți indicatorul la începutul matricei și faceți următoarele într-o buclă:

1. Verificați dacă elementul curent este cel dorit. Dacă da, returnăm un răspuns dacă pointerul se află în matrice sau o eroare dacă nu este. In caz contrar
2. Măriți și continuați.

Într-un fel sau altul, elementul este garantat a fi găsit, iar verificarea limitelor este efectuată o singură dată când se întâmplă acest lucru. Aceasta este o idee profundă, dar este destul de simplă chiar și pentru un programator începător. Probabil că nu pot vorbi despre relevanța muncii pentru alții, dar am putut imediat să aplic această înțelepciune atât codului personal, cât și profesional. Cartea TAOCP este plină de astfel de pietre prețioase (pentru a fi corect, există și o mulțime de lucruri ciudate acolo, cum ar fi sortare cu bule).

„Caută, caută
Atât cât
Caută, caută
am vrut doar sa dansez"
— Luther Vandross, „Căutarea” (1980)

Greșeală de tipar #2

A doua greșeală de tipar se află în Volumul 4A, Algoritmi combinatori, Partea 1. Pagina 60 descrie o problemă care implică programarea comedianților pentru a juca la diferite cazinouri. Mai mulți comedianți din viața reală sunt citați ca exemple, inclusiv Lily Tomlin, Weird Al Yankovic și Robin Williams, care era încă în viață când a fost publicată cartea. Knuth afișează întotdeauna numele complete în index, așa că Williams este listat la pagina 882 ca „Williams, Robin McLorim”. Dar al doilea nume se termină cu „n” și nu „m”, adică McLaurin.

McLaurin era numele de fată al mamei sale. Ea a fost strănepoata lui Anselm Joseph McLaurin, al 34-lea guvernator al Mississippi. Domnia lui, se pare, nu a fost amintită pentru nimic bun. Din carte „Mississippi: istorie”:

„Cel mai important eveniment din timpul administrației McLaurin a fost declarația de război a Statelor Unite împotriva Spaniei în primăvara anului 1898... Din păcate, războiul poate să fi oferit unor oficiali guvernamentali posibilitatea de a se angaja în mită. McLaurin a fost acuzat de diverse practici îndoielnice, inclusiv nepotism și utilizarea excesivă a puterilor de grațiere. În timpul mișcării de temperanță, criticii l-au acuzat pe guvernator că este un bețiv, ceea ce a recunoscut public.”

Greseala istorica

Lua în considerare algoritm tradițional de multiplicare din programa școlară. Câte înmulțiri cu o singură cifră necesită? Să presupunem că te înmulți -număr digital pe -pic . Mai întâi înmulțiți prima cifră pentru fiecare cifră unul câte unul. Apoi înmulțiți a doua cifră pentru fiecare cifră unul câte unul și așa mai departe până când treci prin toate numerele . Astfel, înmulțirea tradițională necesită înmulțiri primitive. În special, înmulțirea a două numere cu grade necesare înmulțiri cu o singură cifră.

Acest lucru este rău, dar este posibil să se optimizeze procesul folosind o metodă dezvoltată de matematicianul sovietic Anatoly Alekseevich Karatsuba. Să ne prefacem că и  - numere zecimale din două cifre; adică sunt numere , , , astfel încât и (generalizarea acestui algoritm la numere mai mari necesită o anumită manipulare; deși nu este prea dificil, pentru a nu greși în detalii, mai bine mă voi păstra la un exemplu simplu). Apoi , , . Înmulțirea binoamelor dă . Momentan mai avem înmulțire cu o singură cifră: , , , . Acum să adunăm și să scădem . După câteva rearanjamente, pe care le voi lăsa ca exercițiu pentru cititor, se dovedește  - doar trei înmulțiri cu o singură cifră! (Există niște coeficienți constanți, dar aceștia pot fi calculați doar prin adăugarea și deplasarea cifrelor).

Nu cere dovezi, dar Algoritmul Karatsuba (generalizat recursiv din exemplul de mai sus) îmbunătățește metoda tradițională de înmulțire cu operatii inainte . Vă rugăm să rețineți că aceasta este o îmbunătățire reală a algoritmului, nu o optimizare pentru calcule mentale. Într-adevăr, algoritmul nu este potrivit pentru aritmetica mentală, deoarece necesită costuri generale mari pentru operațiuni recursive. În plus, efectul nu se va manifesta pe deplin până când numerele vor deveni suficient de mari (din fericire, algoritmul lui Karatsuba a fost înlocuit cu metode și mai rapide: în martie 2019, a fost publicat un algoritm care necesită doar n jurnal n înmulțiri; accelerația se aplică numai numerelor inimaginabil de mari).

Acest algoritm este descris la pagina 295 din volumul XNUMX, Algoritmi semi-numerici. Acolo Knuth scrie: „Este curios că această idee a fost descoperită doar în 1962 an”, când a fost publicat un articol care descrie algoritmul lui Karatsuba. Dar! În 1995, Karatsuba a publicat o lucrare „Computational Complexity”, care spune mai multe lucruri: 1) în jurul anului 1956, Kolmogorov a sugerat că înmulțirea nu se poate face în mai puțin de trepte; 2) în 1960 anul Karatsuba a participat la seminarul unde Kolmogorov și-a prezentat ipoteza n². 3) „În exact o săptămână,” Karatsuba a dezvoltat algoritmul „împărțiți și cuceriți”; 4) în 1962, Kolmogorov a scris și a publicat un articol în numele lui Karatsuba cu o descriere a algoritmului. „Am aflat despre acest articol abia după ce a fost republicat.”

Deci eroarea este că în loc de 1962 trebuie specificat 1960 an. Asta e tot.

analiza

Găsirea erorilor nu a necesitat abilități speciale.

1. Prima eroare a fost cât se poate de banală și a fost într-un loc relativ vizibil (începutul capitolului). Orice idiot l-ar fi găsit; Tocmai m-am dovedit a fi acel idiot.
2. Găsirea celei de-a doua greșeli a necesitat noroc și diligență, dar nu pricepere. Indexul pentru „Williams” se află pe penultima pagină a volumului, o parte destul de proeminentă a cărții. Tocmai răsfoiam indexul (nu este atât de jalnic pe cât pare, pentru că există ouă de Paște ascunse în indexurile lui Knuth. De exemplu, există intrări în arabă și ebraică, ambele indicând pagina 66. Dar pagina respectivă nu menționează fie limbi; în schimb, se referă la „limbi care sunt citite de la dreapta la stânga”). Și al doilea nume mi-a atras atenția. Deoarece citesc de obicei Wikipedia, l-am verificat pe Robin Williams și am observat o discrepanță.
3. Mi-aș dori să pot spune că am făcut cercetări serioase pentru a găsi o eroare istorică, dar într-adevăr doar m-am uitat Pagina Wikipedia despre algoritmul lui Karatsuba. Primele rânduri spun: „Algoritmul Karatsuba este un algoritm de multiplicare rapidă. Descoperit de Anatoly Karatsuba în 1960 și publicat în 1962.” După aceea, tot ce a mai rămas a fost să adauge doi și doi.

Pe viitor aș dori să găsesc o eroare mai semnificativă, mai ales în codul lui Knuth. De asemenea, aș dori să găsesc o eroare în primul volum al Algoritmilor fundamentale. Poate l-aș fi găsit, dar din anumite motive biblioteca locală are doar volumele 2, 3 și 4A.

Date financiare:

• În total, contribuția mea la TAOCP constă din doar trei personaje: o adăugare s, înlocuire m pe n и 2 pe 0. La 2,56 USD, acestea sunt câteva simboluri destul de profitabile; Dacă ai fi plătit cu asemenea bani, un articol de 1000 de cuvinte (în medie patru caractere) ți-ar câștiga zece mii.
• Cu trei dolari hexazecimali, eu, împreună cu alți 29 de cetățeni, sunt la egalitate pe locul 69 pe lista celor mai bogați deponenți ai Băncii San Serriff (de la 1 mai 2019).

Alte discuții despre cecuri de la Knuth

• Cum să obțineți un cec de la Knuth

  Recomandări generale pentru găsirea erorilor în cărțile lui Knuth. În mare parte se referă la erori tehnice, pe care nu le am. Există o sugestie pe care am luat-o în serios:

  Cel mai bine este să așteptați până când ați colectat un set de erori pentru a le trimite. Combinând mai multe erori reale, dar nu foarte valoroase, creșteți probabilitatea ca una dintre ele să fie de fapt considerată o greșeală sau un sfat. Dacă trimiteți erori pe rând, fiecare în parte poate fi respinsă.

  Nu am vrut să trimit doar greșeli de scriere prostii, ci am luat sfatul și am trimis scrisoarea doar când am găsit o eroare istorică care mi s-a părut destul de gravă.

• Cecurile lui Ashutosh Mehra

  Ashutosh Mehra este al treilea cel mai bogat investitor din San Serriff, cu o valoare netă uimitoare de 0x207,f0 USD în BoSS.

• Verificați unele erori nefuncționale în codul TeX real
• Diverse: #1 #2 #3 #4 #5 #6

Sursa: www.habr.com