Donald Knuth on inforaatika valdkonna teadlane, kes hoolib oma raamatute täpsusest nii palju, et pakub ühe heksadollar ($2,56, 0x$1,00) iga leitud "viga" eest, kus vea alla kuulub kõik, mis on "tehniliselt, ajalooliselt, trükiviga või poliitiliselt vale". Ma tõeliselt tahtsin Knuthilt tšekki saada, seega otsustasin otsida vigu tema silmapaistvas teoses "Programmimise kunst" (TAOCP). Õnnestus leida kolm. Tõele au andes, saatis Knuth tšeki summas 0x$3,00.

Nagu näete, ei ole see tõeline tšekk. Varem saatis Knuth päris tšekke, kuid lõpetas selle 2008. aastal suure petuskeemi tõttu. Nüüd saadab ta "isiklikke deposiidisertifikaate"San-Seriffi pangas (BoSS). Ta ütleb, et on valmis vajadusel saatma päris raha, kuid tundub, et see on liiga vaevaline. Leidsin kaks trükiviga ja ühe ajaloolise vea. Loetlen need alates vähemolulisest.

Trükiviga nr 1

Esimene trükiviga on kolmanda köite "Sorteerimine ja otsimine" leheküljel 392, kaheksas rida alt üles: "Pärast ebaõnnestunud otsingut on mõnikord (sometime) soovitatav sisestada tabelisse uus sissekanne, mis sisaldab

Esimene trükiviga on kolmanda köite „Sorteerimine ja otsimine“ leheküljel 392, kaheksas rida alt: „Pärast ebaõnnestunud otsingut on mõnikord (sometime) soovitatav tabelisse sisestada uus kirje, mis sisaldab K; meetod, mida selleks kasutatakse, nimetatakse leidmise ja lisamise algoritmiks. Probleem on selles, et selle asemel, et millegi! peab olema mõnikord.

Loomulikult pole sellises veas midagi üllatavat. Selles artiklis on kindlasti mitu trükiviga (ei mingeid auhindu nende leidmise eest). Mis on tõeliselt üllatav, on see, et seda nii kaua ei märgatud. Leht 392 ei asu sügaval matemaatika jaotuses, see on esimene leht kuuendas peatükis „Otsing“! Võib-olla üks loetavamaid osi raamatust. Teooria järgi peaks seal olema kõige vähem trükivigu, aga ei ole.

Muide, kui olete kunagi mõelnud TAOCP lugemisest, proovige. Paljud ütlevad, et see on käsiraamat, mis ei ole mõeldud otseseks lugemiseks, kuid see ei ole tõsi. Autoril on selge seisukoht ja iseloomulik stiil. Ainuke, mis takistab lugemist, on matemaatika keerukus. Siiski on lihtne lahendus: lugege, kuni jõuate matemaatikani, mida te ei mõista, jätke see vahele ja avage järgmine jaotis, mille mõistate. Nii lugedes jätan ma vahele vähemalt 80% raamatust, aga ülejäänud 20% on imelised!

Samuti öeldakse, et TAOCP pole asjakohane, on aegunud või muul viisil rakendumatuks muutunud "reaalses programmeerimises". See pole tõsi. Näiteks käsitletakse esimeses jaotises, pärast sissejuhatust, elemendi otsimist sorteerimata massiivis. Kõige lihtsam algoritm on tuttav kõigile programmeerijatele. Käivitage näitaja massiivi alguses, seejärel tehke tsüklis järgmised toimingud:

Kuidas kontrollida, kas praegune element on soovitud. Kui jah, tagastame selle; vastasel juhul
Kontrollige, kas näitaja on massiivi piirist väljas. Kui on, tagastage viga; vastasel juhul
Suurendage näitajat ja jätkake.

Nüüd vaatame: kui palju piiri kontrollimisi nõuab see algoritm keskmiselt? Halvimal juhul, kui massiiv ei sisalda elementi, vajab iga elemendi jaoks loendis ühte kontrollimist ja keskmiselt on see midagi sellist . Nutikam otsingu algoritm võib vajada ainult ühte piiri kontrollimist. Lisage vajalik element massiivi lõppu, seejärel käivitage näitaja massiivi alguses ja tehke tsüklis järgmised toimingud:

Kontrollige, kas praegune element on soovitud. Kui jah, tagastame vastuse, kui osutaja on massiivi piirides, või vea, kui see ei ole. Vastasel juhul
Suurendage näitajat ja jätkake.

Nii või naa, element leitakse kindlasti, ja piire kontrollitakse ainult üks kord, kui see toimub. See on sügavam mõte, kuid piisavalt lihtne isegi algajale programmeerijale. Tõenäoliselt ei saa ma rääkida ettepaneku relevantsusest teiste jaoks, kuid suutsin rakendada seda tarkust kohe nii isiklikus kui ka professionaalses koodis. Raamat TAOCP on täis selliseid pärleid (õigusemõistmise nimel, seal on ka palju kummalisi asju, nagu mullisortimine).

„Otsimine, otsimine
Nii kaua
Otsimine, otsimine
Ma tahtsin lihtsalt tantsida“
— Luther Vandross, „Otsimine“ (1980)

Trükiviga nr 2

Teine trükiviga on köites 4A, „Kombinatoorsed algoritmid“, osa 1. Leheküljel 60 on kirjeldatud komöödikute etenduste planeerimise ülesannet erinevates kasiinodes. Näiteks tuuakse välja mitmed tegelikud koomikud, sealhulgas Lily Tomlin, Weird Al Yankovic ja Robin Williams, kes oli raamatu väljaandmise ajal veel elus. Knuth toob alati välja täielikud nimed, seega mainitakse Williamsi leheküljel 882 kui „Williams, Robin McLorin“. Kuid tema teine nimi lõppeb „n“-iga, mitte „m“-iga, seega on McLorin.

McLorin on tema ema neiupõlvenimi. Ta oli Anslem Joseph McLorini lapselapselaps. Tema valitsemine ei jätnud ilmselt suurt muljet. Raamatust „Mississippi: ajalugu“:

„Kõige olulisem sündmus Mac-Lorini administratsiooni ajal oli Ameerika Ühendriikide sõjakuulutamine Hispaaniale 1898. aasta kevadel… Kahjuks andis sõda ilmselt mõnele riigiametnikule võimaluse praktiseerida altkäemaksu. Mac-Lorinile esitati süüdistusi erinevates kahtlastes praktikates, sealhulgas nepotismis ja liialdatud armuandmise volituste kasutamises. Suitsuvaba liikumise ajal süüdistati kuberneri alkoholi kuritarvitamises, mida ta avalikult tunnustas.“

Histooriline viga

Vaadakem traditsiooniline korrutamisalgoritm kooliprogrammist. Kui palju nõuab see ühekohalisi korrutamisi? Oletame, et korrutad -kohalist arvu järgnevaga -kohaline . Esiteks korrutad esimese numbri iga numbri järgides. Siis korrutad teise numbri iga numbri järgides ja nii edasi, kuni oled kõik numbrid läbi teinud . Seega nõuab traditsiooniline korrutamine primitiivsete korrutamiste arvu. Täpsemalt vajavad kahe arvu korrutamine kohakohalisi korrutamisi. üheharulisi korrutusi.

See on halb, kuid protsessi saab optimeerida Nõukogude matemaatiku Anatoli Aleksejevič Karatsuba välja töötatud meetodi abil. Oletame, et ja — kahekohalised kümnendnumbrid; see tähendab, et on olemas numbrid , , , sellised, et ja (selle algoritmi laiendamine suurematele numbritele nõuab teatud manipulatsioone; kuigi see ei ole liiga keeruline, et mitte vale detailide üle, eelistan ma jääda lihtsa näite juurde). Siis , , . Kahe liikme korrutamine annab . Praegu on meil endiselt ühe numbri korrutamised: , , , . Nüüd liidame ja lahutame . Pärast mitmeid ümberkorraldusi, mille jätan lugejatele harjutamiseks, saame — kokku kolm ühe numbri korrutamist! (On mõned püsiväärtused, kuid neid saab arvutada ainult liitmise ja positsioonide nihutamise kaudu).

Ärge paluge tõestust, kuid Karatsuba algoritm (rekursiivselt laiendatud ülaltoodud näitest) parandab traditsioonilist korrutamisviisi operatsioonidest kuni . Pange tähele, et see on tõeline algoritmi täiustamine, mitte meeles arvestamiseks optimeerimine. Tõepoolest, algoritm ei sobi meeles arvestamiseks, kuna see nõuab palju ressursse rekursiivsete toimingute jaoks. Lisaks avaldub efekt täielikult alles siis, kui numbrid on piisavalt suured (õnneks tuleb Karatsuba algoritmi asemel välja veelgi kiiremaid meetodeid: märtsis 2019 avaldati algoritm, mis vajab vaid n log n korrutamist; kiirus on rakendatav ainult uskumatult suurte numbrite puhul).

Seda algoritmi on kirjeldatud „Arvutuslikud algoritmid“ teise köite lehel 295. Seal kirjutab Knuth: „Uskumatu, et seda ideed avastati alles 1962 aastal“, mil avaldati artikkel, mis kirjeldas Karatsuba algoritmi. Kuid! 1995. aastal avaldas Karatsuba artikli „Arvutamise keerukus“, kus ta ütleb mitu asja: 1) umbes 1956. aastal tegi Kolmogorov eelduse, et korrutamine ei saa toimuda vähem kui sammu; 2) 1960 aastal 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 kirjeldustega. "Saime sellest artiklist teada alles pärast seda, kui see trükiti uuesti."

Seega on viga selles, et selle asemel, 1962 peaks olema märgitud 1960 aasta. Nii et see ongi.

Analüüs

Vigade leidmine ei nõudnud erilist oskust.

Esimene viga oli nii banaalne, kui vähegi võib olla, ja asus suhteliselt nähtaval kohal (peatüki alguses). Igasugune inimene oleks selle üles leidnud; lihtsalt mina sattusin olema see inimene.
Teise trükkimisvea leidmine nõudis õnne ja vaeva, mitte oskusi. „Williamsi“ indeks asub raamatu eelviimasel leheküljel, mis on üsna tähelepanuväärne osa raamatust. Ma just sirvisin indeksit (see ei ole nii halb, nagu tundub, sest Knuthi indeksites on peidetud ülestähendusi. Näiteks on seal kirjeid araabiakeeles ja heebrea keeles, ja mõlemad viitavad leheküljele 66. Kuid sellel leheküljel ei mainita ühtegi neist keeltest; seal räägitakse hoopis „keeltest, mida loetakse paremalt vasakule“). Ja mu tähelepanu köitis teine nimi. Kuna ma tavaliselt loen Vikipeediat, kontrollisin Robin Williamsi ja märkasin lahknevust.
Tahaksin öelda, et tegin tõsise uurimistöö ajaloolise vea leidmiseks, kuid tegelikult vaid vaatasin Vikipeedia lehte Karatsuba algoritmi kohta. Esimeste ridade seas on kirjas: „Karatsuba algoritm on kiire korrutamise algoritm. Avastas Anatoli Karatsub 1960. aastal ja avaldati 1962. aastal“. Pärast seda jäi vaid kokku liita kaks korda kaks.

Tulevikus tahaksin leida mõne suurema vea, eriti Knuthi koodis. Samuti tahaksin leida vea „Fundamentaalsed algoritmid“ esimese köite kohta. Võib-olla oleksin seda leidnud, aga kohalikus raamatukogus on mingil põhjusel ainult köited 2, 3 ja 4A.

Finantsfaktid:

Kokku koosneb minu panus TAOCP-st vaid kolmest sümbolist: ühest lisamisest s, asendamisest m järgnevaga n ja 2 järgnevaga 0. Hindadega $2,56 on need üsna tulusad sümbolid; kui teile makstaks selliseid summasid, siis tooks 1000 sõna artikli (keskmiselt neli sümbolit) teile kümme korda rohkem.
Kolme kuuekümnendiku dollariga jagan koos 29 teise kodanikuga 69. kohta San-Seriifi pangas kõige rikkamate hoiustajate nimekirjas (seisuga 1. mai 2019).

Teised Knuthi tšekivaatlused

Kuidas saada tšekki Knutilt
Üldised soovitused Knuthi raamatutes vigade leidmiseks. Peamiselt puudutavad tehnilisi vigu, mida mul pole. Seal on üks lause, mida võtsin tõsiselt:
Parem on oodata, kuni olete kogunud hulga vigu, mida saata. Ühendades mitu tõelist, kuid mitte eriti väärtuslikku viga, suurendate tõenäosust, et üks neist tõeliselt vigadena või soovitustes hinnatakse. Kui saata vigu ükshaaval, võivad igaüht eraldi tagasi lükata.
Ma ei tahtnud lihtsalt saata tarbetut trükiviga, vaid järgisin nõu ja saatsin kirja alles siis, kui leidsin ajaloolise vea, mis tundus piisavalt tõsine.
Ashotush Mehra tšekid
Ashotush Mehra on kolmas kõige rikkam investeerija San-Seriffis, kelle koguväärtus on 0x$207,f0 BoSS-is.
Mõnede mittefunktsionaalsete vigade tšekk reaalses TeX koodis
Erinevad: #1 #2 #3 #4 #5 #6