Donald Knuth — informaatika alal teadlane, kes hoolib oma raamatute täpsusest nii palju, et pakub ühe kuuenda dollari ($2,56, 0x$1,00) iga leitud «vea» eest, kus veaks loetakse kõik, mis on «tehniliselt, ajalooliselt, tüpograafiliselt või poliitiliselt vale». Ma tõesti tahtsin Knuthilt tšekki saada, seetõttu otsustasin otsida vigu tema silmapaistvas töös «Programmeerm kunst» (TAOCP). Õnnestus leida kolm. Tõtt-öelda, Knuth saatis tšeki summas 0x$3,00.
Nagu näete, ei ole see tõeline kšek. Varem saatis Knuth tõelisi tšekke, kuid lõpetas selle 2008. aastal . Nüüd saadab ta «isiklikke hoiustamise sertifikaate» (BoSS). Ta ütleb, et on valmis vajadusel tõelisi raha saatma, kuid tundub, et see on liiga vaevaline.
Leidsin kaks trükiviga ja ühe ajaloolise vea. Loetlen need kahanevas triviaaluse järjekorras.
Trükiviga nr 1
Esimene trükiviga on kolmanda köite, «Sorteerimine ja otsing» lehe 392, kaheksas rida alt: «Pärast ebaõnnestunud otsingut on mõnikord (sometime) soovitatav tabelisse sisestada uus kirje, mis sisaldab K; meetod, mis seda teeb, nimetatakse otsing ja sisestamise algoritmiks. Viga seisneb selles, et «sometime» asemel peaks olema sometimes peab olema Loomulikult pole sellises veas midagi üllatavat. Ainult selles artiklis leidub kindlasti mitmeid trükivigu (tasu nende leidmise eest ei ole). Mis on tegelikult üllatav, on see, et seda pole nii kaua märgatud. Leht 392 ei asu sügaval matemaatika jaotises, see on.
kogu kuuendast peatükist «Otsing»! Võib-olla on see üks loetavamaid jaotisi raames. Idee kohaselt peaks seal olema kõige vähem trükivigu, kuid ei ole. Muide, kui olete kunagi mõelnud TAOCP lugemisele, proovige. Paljud ütlevad, et see on viiteraamat
, mis ei ole mõeldud otse lugemiseks, kuid see ei ole tõsi. Autoril on selge seisukoht ja isikupärane stiil. Ainus, mis loetavust takistab, on matemaatika keerukus. Kuid sellele on lihtne lahendus: loe, kuni jõuad matemaatikani, mida sa ei mõista, jäta see vahele ja avaa järgmine jaotis, mida saad mõista. Sellisel viisil lugedes jätan ma vahele vähemalt 80% raamatust, kuid ülejäänud 20% on suurepärased! Samuti öeldakse, et TAOCPei ole asjakohane
, ei ole reaalne, on vananenud või muul viisil mitteoluline «reaalse programmeerimise» kontekstis. See pole ka tõsi. Näiteks käsitletakse esimeses jaotises pärast sissejuhatust elementide otsimist sorteerimata massiivis. Lihtsaim algoritm on kõikidele programmeerijatele tuttav. Käivitage suunaja massiivi alguses, seejärel tehke allolevaid toiminguid tsüklis:
- Kontrollige, kas praegune element on soovitud. Kui jah, tagastage see; vastasel juhul
- Kontrollige, kas suunaja on massiivi piiridest väljas. Kui jah, tagastage viga; vastasel juhul
- Suurendage suunajat ja jätkake.
Nüüd vaatame: kui palju piiri kontrollimist see algoritm keskmiselt nõuab? Halvimal juhul, kui massiivis ei ole elementi, vajab iga elemendi puhul loendis ühte kontrolli ning keskmiselt on see midagi sellist 
. Nutikam otsingu algoritm võib vajada vaid ühte piiri kontrolli. Lisage vajalik element massiivi lõppu, seejärel käivitage suunaja massiivi alguses ja tehke allolevaid toiminguid tsüklis:
- Kontrollige, kas praegune element on soovitud. Kui jah, tagastage vastus, kui suunaja on massiivi piirides, või viga, kui see pole nii. Vastasel juhul
- Suurendage suunajat ja jätkake.
Nii või naa, element leidub kindlasti ning piiri kontrollimise teeb ainult ühe korra, kui see on juhtunud. See on sügav idee, kuid piisavalt lihtne ka algaja programmeerija jaoks. Ilmselt ei saa ma rääkida selle töö relevantsusest teiste jaoks, kuid mul õnnestus koheselt seda tarkust rakendada nii isiklikus kui ka ametialases koodis. RAAMAT TAOCP on täis selliseid pärleid (aususe nimel, seal on ka palju veidraid asju, nagu ).
«Otsimine, otsimine
Nii kaua
Otsimine, otsimine
Ma tahtsin lihtsalt tantsida»
— Luther Vandross, «Otsimine» (1980)
Trükiviga nr 2
Teine viga on osas 4A, "Kombinatorilised algoritmid", osa 1. Leheküljel 60 on kirjeldatud koomikute esinemiste kavandamise ülesannet erinevates kasiinodes. Näiteks tuuakse välja mitmed tõelised koomikud, sealhulgas Lily Tomlin, Weird Al Yankovic ja Robin Williams, kes oli raamatu ilmumisel veel elus. Knut viitab alati täielikele nimedele, seega mainitakse Williamsi leheküljel 882 nimega "Williams, Robin MacLorin". Kuid tema teine nimi lõpeb "n"-iga, mitte "m"-iga, st MacLorin.
MacLorin on tema ema neiupõlvenimi. Ta oli Anselm Joseph MacLorini, Mississippi 34. kuberneri, lapselaps. Tema valitsus ei jää ilmselt meelde millegi hea poole. Raamatust :
„Ainus oluline sündmus MacLorini ametiaja jooksul oli Ameerika Ühendriikide sõda Hispaania vastu, mis kuulutati välja 1898. aasta kevadel… Kahjuks andis seda sõda mõnedele ametnikele võimaluse praktiseerida altkäemaksu. MacLorinit süüdistati mitmesugustes kahtlastes praktikas, sealhulgas sugulaste tööle võtmiseks ja volituste kuritarvitamiseks armuandetes. Tõrjumise ajastul süüdistati kuberneri alkoholi tarbimises, mida ta avalikult tunnustas.“
Ajalooline viga
Vaadake traditsiooniline korrutamise algoritm kooli õpikust. Kui palju ühekohalisi korrutamistoiminguid see nõuab? Oletame, et korrutate 
-kohalise numbrega 
. Tundub, et 
-kohaline number 
. Esiteks korrutate esimese numbri 
iga numbri 
järjekorras. Siis korrutate teise numbri 
iga numbri 
järjekorras ja nii edasi, kuni olete kõik numbrid läbi käinud 
. Seega nõuab traditsiooniline korrutamine 
primitivo korrutamisi. Eriti kahe arvu korrutamine 
-kohtade kaupa nõuab 
ühekoha korrutamisi.
See on halb, kuid protsessi saab optimeerida meetodiga, mille töötas välja nõukogude matemaatik Anatoli Aleksejevitš Karatsuba. Oletame, et 
ja 
on kahekohalised kümnendnumbrid; st on olemas numbrid 
, 
, 
, 
nii, et 
ja 
(selle algoritmi laiendamine suurematele arvudele nõuab teatud manipuleerimisi; kuigi see ei ole liiga keeruline, aga et üksikasjades eksida ei oleks, eelistan ma pidada kinni lihtsast näitest). Siis 
, 
, 
. Kahe liikme korrutamine annab 
. Seni on meil endiselt 
ühekoha korrutamisi: 
, 
, 
, 
. Nüüd liidame ja lahutame 
. Pärast mitmeid ümberkorraldusi, mille ma jätan lugeja ülesandeks, tuleb 
— kokku vaid kolm ühekohalist korrutamist! (On mõned pidevad koefitsiendid, kuid neid saab arvutada vaid liitmise ja numbrite nihutamisega).
Ära nõua tõestust, kuid Karatsuba algoritm (rekursiivselt üldistatud eeltoodud näitest) täiustab traditsioonilist korrutamismeetodit 
operatsioonidest tuhandeni 
. Pange tähele, et see on tegelik algoritmi täiustus, mitte optimeerimine meeles arvutamiseks. Tõepoolest, algoritm ei sobi vaimseks arvestamiseks, kuna see nõuab suuremaid kulusid rekursiivsete operatsioonide jaoks. Lisaks ilmneb efekt täielikult alles siis, kui numbrid on piisavalt suured (õnneks on Karatsuba algoritmist veel kiiremad meetodid: 2019. aasta märtsis avaldati algoritm, mis nõuab vaid korrutamist; kiirus suureneb ainult arusaamatult suurte numbrite korral).
Seda algoritmi kirjeldatakse teise köite 295. leheküljel "Aritmeetilised algoritmid". Seal kirjutab Knuth: "Huvitav, et seda ideed avastati alles 1962 aastal", kui avaldati artikkel, mis kirjeldab Karatsuba algoritmi. Kuid! 1995. aastal avaldas Karatsuba artikli "Arvutuste keerukus", kus ta mainib mitmeid asju: 1) umbes 1956. aastal предположил, et korrutamine pole võimalik vähem kui 
sammud; 2) aastal 1960 osales Karatsuba seminaril, kus Kolmogorov esitas oma hüpoteesi n². 3) „Just nädal aega hiljem“ töötas Karatsuba välja algoritmi „jaga ja valitse"; 4) 1962. aastal kirjutas ja avaldas Kolmogorov artikli Karatsuba nimel algoritmi kirjeldusega. „Ma kuulsin sellest artiklist alles pärast seda, kui seda ümber trükiti."
Nii et viga seisneb selles, et asemel 1962 peaks olema 1960 aasta. Nii lihtne see on.
Analüüs
Vigade leidmine ei nõudnud erilist oskust.
- Esimene viga oli nii banaalne kui võimalik ja asus suhteliselt silmapaistvas kohas (peatüki alguses). Iga idioot oleks selle leidnud; lihtsalt mina olin see idioot.
- Teise trüki vea leidmine nõudis õnne ja vaeva, kuid mitte oskust. "Williams'i" indeks on eelviimasel lehel, üsna märkimisväärne osa raamatust. Ma just sirvisin indeksit (see ei ole nii kahju, nagu tundub, sest Knuthi indeksites on varjatud munade jahtimisi. Näiteks on seal sissekanne araabia ja heebrea keeles, ja mõlemad viitavad lehele 66. Kuid sellel lehel ei mainita kumbagi keelt; selle asemel mainitakse "keeli, mida loetakse paremale poole"). Ja minu tähelepanu tõmbas teise nime. Kuna ma tavaliselt loen Vikipeediat, kontrollisin Robin Williams'i ja märkasin erinevust.
- Ma tahaksin öelda, et ma tegin tõsist uurimistööd ajaloo vea leidmiseks, kuid tegelikult vaatasin lihtsalt Esimeste ridade seas on kirjas: "Karatsuba algoritm on kiire korrutamise algoritm. Avas Anatoli Karatsuba 1960. aastal ja avaldati 1962. aastal." Pärast seda jäi vaid kokku lüüa kaks ja kaks.
Tulevikus tahaksin leida mõne olulisema vea, eriti Knuthi koodis. Tahaksin leida vea ka "Alustavaid algoritme" käsitlevas esimeses osas. Võib-olla leidsin selle, kuid kohalikes raamatukogudes on mingil põhjusel vaid 2., 3. ja 4A osa.
Finantsfaktid:
- Kokku koosneb minu panus TAOCP-st vaid kolmest sümbolist: ühest lisamisest s, asendamisest m . Tundub, et n ja 2 . Tundub, et 0. Hind on $2,56, need on üsna kasulikud sümbolid; kui teile makstaks selliseid summasid, siis 1000 sõna artikkel (keskmiselt neli sümbolit) tooks teile kümme tükki.
- Kolme kuueksandikkudega dollariga jagan koos 29 teise kodanikuga 69. koha San-Seriifi pangas kõige rikkamate sissemaksete loendis (olekus 1. mai 2019).
Teised arutelud Knuthi tšekkide üle
Üldised soovitused tõrgete leidmiseks Knuthi raamatutes. Peamiselt puudutavad tehnilisi vigu, mida mul pole. Seal on üks lause, mida ma võtsin tõsiselt:
On parem oodata, kuni kogute vea komplekti saatmiseks. Ühendades mõned reaalsed, kuid mitte väga väärtuslikud vead, suurendate tõenäosust, et mõni neist tõeliselt vigana või soovitusena käsitletakse. Kui saata vigasid ühekaupa, võivad nad kõik eraldi tagasi lükata.
Ma ei soovinud saata lihtsalt rumalaid trükivigu, vaid järgisin nõu ja saatsin kirja alles siis, kui leidsin ajaloolise vea, mis tundus piisavalt tõsine.
Ashutosh Mehra on kolmas kõige rikkam investeerija San-Seriffis, kelle varandus ulatub 0x$207,f0 BoSS-is.
- Erinevad:
Allikas: habr.com
