Donald Knuth je informatičar kome je toliko stalo do tačnosti svojih knjiga da sugeriše jedan heksadecimalni dolar ($2,56, 0x$1,00) za bilo koju pronađenu "grešku", pri čemu se greška definiše kao bilo šta što je "tehnički, istorijski, tipografski ili politički nekorektno." Zaista sam želio dobiti ček od Knutha, pa sam odlučio da potražim greške u njegovom magnum opusu "Umetnost programiranja" (TAOCP). Uspjeli smo pronaći tri. Vjeran svojoj riječi, Knut je poslao ček za 0x3,00$.

Kao što vidite, ovo nije prava provjera. Knuth je slao prave čekove, ali je prestao 2008. godine zbog neobuzdana prevara. On sada šalje "lične potvrde o depozitu". Bank of San Serriff (Šef). Kaže da je spreman da pošalje pravi novac ako bude potrebno, ali čini se da je to prevelika gnjavaža.

Našao sam dvije greške u kucanju i jednu istorijsku grešku. Navešću ih po opadajućoj trivijalnosti.

Tipska greška #1

Prva greška u kucanju je na strani 392 trećeg toma „Sortiranje i pretraživanje“, osmi red od dna: „Nakon neuspešne pretrage, ponekad (ponekad) je poželjno uneti novi zapis u tabelu koja sadrži K; metoda koja to radi naziva se algoritam pretraživanja i umetanja. Greška je što umesto toga nekada trebalo bi biti ponekad.

Naravno, takva greška nije iznenađujuća. Sigurno će biti nekoliko grešaka u kucanju samo u ovom članku (nema nagrada za njihovo pronalaženje). Ono što je zaista iznenađujuće je da je tako dugo prošlo nezapaženo. Stranica 392 nije zakopana duboko u sekciju matematike, jeste prva stranica Poglavlje XNUMX "Traži"! Vjerovatno jedan od najčitanijih dijelova knjige. U teoriji bi trebalo da bude najmanje grešaka u kucanju, ali ne.

Usput, ako ste ikada razmišljali o čitanju TAOCP-a, pokušajte. Mnogi će reći da je to directory, nije namijenjeno direktnom čitanju, ali to nije istina. Autor ima jasan stav i karakterističan stil. Jedina stvar koja ometa čitljivost je složenost matematike. Međutim, postoji jednostavno rješenje: čitajte dok ne dođete do matematike koju ne razumijete, preskočite je i idite na sljedeći odjeljak koji možete razumjeti. Čitajući na ovaj način, nedostaje mi barem 80% knjige, ali ostalih 20% je super!

Takođe se kaže da je TAOCP nebitno, je zastario ili na drugi način nije primjenjiv na "pravo programiranje". Ovo takođe nije tačno. Na primjer, prvi dio nakon uvoda razmatra pronalaženje elementa u nesortiranom nizu. Najjednostavniji algoritam poznat je svim programerima. Pokrenite pokazivač na početku niza, a zatim uradite sljedeće u petlji:

1. Provjerite je li trenutni element željeni. Ako je tako, vraćamo ga; inače
2. Provjerite je li pokazivač izvan granice niza. Ako je tako, vratite grešku; inače
3. Uvećajte i nastavite.

Sada razmislite: koliko provjera granica u prosjeku zahtijeva ovaj algoritam? U najgorem slučaju, kada niz ne sadrži element, svaki element na listi će zahtijevati jednu provjeru, a u prosjeku će biti nešto poput . Pametniji algoritam pretraživanja mogao bi se izvući samo jednom provjerom granica. Pričvrstite željeni element na kraj niza, zatim pokrenite pokazivač na početku niza i uradite sljedeće u petlji:

1. Provjerite je li trenutni element željeni. Ako je tako, vraćamo odgovor ako je pokazivač unutar niza, ili grešku ako nije. Inače
2. Uvećajte i nastavite.

Na ovaj ili onaj način, element je zajamčeno pronađen, a provjera granica se izvodi samo jednom kada se to dogodi. Ovo je duboka ideja, ali je dovoljno jednostavna čak i za programera početnika. Vjerovatno ne mogu govoriti o relevantnosti rada za druge, ali sam odmah uspio primijeniti ovu mudrost i na lični i na profesionalni kodeks. TAOCP knjiga je puna takvih dragulja (da budemo iskreni, tu ima i dosta čudnih stvari, kao npr. bubble sort).

„Traži, traži
Tako dugo
Traži, traži
Samo sam htela da plešem"
- Luther Vandross, "The Search" (1980.)

Tipska greška #2

Druga greška u kucanju je u tom 4A, Kombinatorni algoritmi, deo 1. Strana 60 opisuje problem koji uključuje zakazivanje komičara za nastupe u raznim kockarnicama. Nekoliko komičara iz stvarnog života navodi se kao primjer, uključujući Lily Tomlin, Weird Al Yankovica i Robina Williamsa, koji je još bio živ kada je knjiga objavljena. Knuth uvijek navodi puna imena u indeksu, tako da je Williams naveden na stranici 882 kao "Williams, Robin McLorim." Ali njegovo srednje ime završava se na "n", a ne na "m", odnosno na McLaurin.

McLaurin je bilo djevojačko prezime njegove majke. Bila je praunuka Anselma Josepha McLaurina, 34. guvernera Misisipija. Njegova vladavina, očigledno, nije ostala upamćena ni po čemu dobrom. Iz knjige "Misisipi: Istorija":

“Najvažniji događaj tokom McLaurinove administracije bila je objava rata Sjedinjenih Država Španiji u proljeće 1898. godine... Nažalost, rat je nekim državnim službenicima možda pružio priliku da se upuste u podmićivanje. McLaurin je optužen za razne upitne prakse, uključujući nepotizam i pretjeranu upotrebu ovlasti za pomilovanje. Tokom pokreta umjerenosti, kritičari su optužili guvernera da je pijanica, što je on javno priznao.”

Istorijska greška

Razmislite tradicionalni algoritam množenja iz školskog programa. Koliko jednocifrenog množenja je potrebno? Pretpostavimo da se množite -cifreni broj na -bit . Prvo pomnožite prvu cifru za svaku cifru jedan po jedan. Zatim pomnožite drugu cifru za svaku cifru jedan po jedan i tako redom dok ne prođete kroz sve brojeve . Stoga tradicionalno množenje zahtijeva primitivna množenja. Konkretno, množenje dva broja sa obavezni činovi jednocifrena množenja.

Ovo je loše, ali moguće je optimizirati proces koristeći metodu koju je razvio sovjetski matematičar Anatolij Aleksejevič Karatsuba. Pretvarajmo se to и  - dvocifreni decimalni brojevi; odnosno postoje brojevi , , , takav da и (generaliziranje ovog algoritma na veće brojeve zahtijeva određenu manipulaciju; iako nije preteško, da ne bih pogriješio u detaljima, bolje ću se zadržati na jednostavnom primjeru). Onda , , . Množenje binoma daje . Trenutno još imamo jednocifreno množenje: , , , . Sada saberimo i oduzmemo . Nakon nekoliko prestrojavanja, koje ću ostaviti kao vježbu za čitaoca, ispostavilo se  - samo tri jednocifrena množenja! (Postoje neki konstantni koeficijenti, ali oni se mogu izračunati samo sabiranjem i pomicanjem cifara).

Ne traži dokaz, ali Karatsuba algoritam (rekurzivno generalizovan iz gornjeg primjera) poboljšava tradicionalni metod množenja sa operacije ranije . Imajte na umu da je ovo pravo poboljšanje algoritma, a ne optimizacija za mentalne proračune. Zaista, algoritam nije prikladan za mentalnu aritmetiku, jer zahtijeva velike režijske troškove za rekurzivne operacije. Osim toga, efekat se neće u potpunosti manifestirati sve dok brojevi ne postanu dovoljno veliki (srećom, Karatsubin algoritam je zamijenjen još bržim metodama: u martu 2019. objavljen je algoritam koji zahtijeva samo n log n množenja; ubrzanje se odnosi samo na nezamislivo velike brojeve).

Ovaj algoritam je opisan na stranici 295 u tom XNUMX, Polunumerički algoritmi. Tamo Knuth piše: „Zanimljivo je da je ova ideja otkrivena tek u 1962 godine”, kada je objavljen članak koji opisuje Karatsubin algoritam. Ali! Godine 1995, Karatsuba je objavio rad o “Computational Complexity” koji kaže nekoliko stvari: 1) Oko 1956. Kolmogorov je sugerirao da se množenje ne može obaviti za manje od stepenice; 2) u 1960 godine Karatsuba je prisustvovao seminaru na kojem je Kolmogorov izložio svoju hipotezu n². 3) „Za tačno nedelju dana“, Karatsuba je razvio algoritam „zavadi pa vladaj“; 4) Kolmogorov je 1962. napisao i objavio članak u ime Karatsube sa opisom algoritma. “Saznao sam za ovaj članak tek nakon što je ponovo objavljen.”

Dakle greška je u tome što umjesto 1962 mora biti specificirano 1960 godine. To je sve.

Анализ

Pronalaženje grešaka nije zahtijevalo posebnu vještinu.

1. Prva greška je bila što trivijalna i bila je na relativno vidljivom mestu (početak poglavlja). Svaki idiot bi ga našao; Upravo sam ispao taj idiot.
2. Pronalaženje druge greške u kucanju zahtevalo je sreću i marljivost, ali ne i veštinu. Indeks za "Williams" nalazi se na pretposljednjoj stranici sveske, prilično istaknutom dijelu knjige. Samo sam prelistavao indeks (nije tako patetično kao što zvuči, jer u Knuthovim indeksima postoje uskršnja jaja skrivena. Na primjer, postoje unosi na arapskom i hebrejskom, oba upućuju na stranicu 66. Ali ta stranica ne spominje oba jezika; umjesto toga se odnosi na „jezike koji se čitaju s desna na lijevo“). I drugo ime mi je privuklo pažnju. Pošto obično čitam Wikipediju, provjerio sam Robina Williamsa i primijetio neslaganje.
3. Voleo bih da mogu da kažem da sam ozbiljno istraživao da pronađem istorijsku grešku, ali zaista sam samo pogledao Stranica Wikipedije o Karatsubinom algoritmu. Već u prvim redovima stoji: „Karatsuba algoritam je brzi algoritam množenja. Otkrio ga je Anatolij Karacuba 1960. i objavljen 1962. Nakon toga preostalo je samo sabrati dva i dva.

U budućnosti bih želio pronaći značajniju grešku, posebno u Knuthovom kodu. Također bih želio pronaći grešku u prvom tomu Fundamental Algoritama. Možda bih ga i našao, ali iz nekog razloga lokalna biblioteka ima samo tomove 2, 3 i 4A.

Finansijske činjenice:

• Ukupno, moj doprinos TAOCP-u sastoji se od samo tri karaktera: jednog dodatka s, zamjena m na n и 2 na 0. Po ceni od 2,56 dolara, ovo su neki prilično unosni simboli; Ako bi vam se platio toliki novac, članak od 1000 riječi (u prosjeku četiri znaka) bi vam zaradio deset hiljada.
• Sa tri heksadecimalna dolara, ja sam, sa još 29 građana, izjednačen za 69. mjesto na listi najbogatijih štediša San Serriff banke (od 1. maja 2019.).

Ostale rasprave o čekovima od Knutha

• Kako dobiti ček od Knutha

  Opće preporuke za pronalaženje grešaka u Knuthovim knjigama. Uglavnom se tiču ​​tehničkih grešaka, kojih nemam. Postoji jedan predlog koji sam ozbiljno shvatio:

  Najbolje je pričekati dok ne prikupite skup grešaka za slanje. Kombinacijom nekoliko stvarnih, ali ne baš vrijednih grešaka, povećavate vjerovatnoću da će se jedna od njih zaista smatrati greškom ili savjetom. Ako pošaljete greške jednu po jednu, svaka pojedinačno može biti odbijena.

  Nisam želeo da šaljem samo glupe greške u kucanju, već sam poslušao savet i poslao pismo tek kada sam našao istorijsku grešku koja se činila dovoljno ozbiljnom.

• Čekovi Ashutosha Mehre

  Ashutosh Mehra je treći najbogatiji investitor u San Serriffu sa ogromnom neto vrijednošću od 0x207.f0 u BoSS-u.

• Provjerite ima li nekih nefunkcionalnih grešaka u pravom TeX kodu
• Ostalo: #1 #2 #3 #4 #5 #6

izvor: www.habr.com