Donald Knuth iradokitzen duen bere liburuen zehaztasunaz hainbeste zaintzen duen informatikaria da hax dolar bat ($2,56, 0x$1,00) aurkitutako "errore" edozeinentzat, non errore bat "teknikoki, historikoki, tipografikoki edo politikoki okerra den edozer" gisa definitzen den. Benetan Knuth-en txeke bat lortu nahi nuen, beraz, bere obra nagusian akatsak bilatzea erabaki nuen "Programazioaren artea" (TAOCP). Hiru aurkitzea lortu genuen. Bere hitzari leial, Knutek txeke bat bidali zuen 0x3,00 $.

Ikus dezakezunez, hau ez da egiazko egiaztapena. Knuth-ek benetako txekeak bidaltzen zituen, baina 2008an gelditu zen horregatik iruzur zabala. Orain "gordailuaren ziurtagiri pertsonalak" bidaltzen ditu San Serriff bankua (BOSS). Beharrezkoa bada benetako dirua bidaltzeko prest dagoela dio, baina badirudi traba handiegia dela.

Bi akats eta akats historiko bat aurkitu ditut. Zerrendatuko ditut txikikotasun txikiagoko ordenan.

Akatsa #1

Lehen idazkera "Ordenatzea eta Bilatzea"ren hirugarren liburukiko 392. orrialdean dago, behetik zortzigarren lerroan: "Bilaketa arrakastatsu baten ondoren, batzuetan (batzuetan) komeni da erregistro berri bat sartzea jasotzen duen taulan. K; hori egiten duen metodoari bilaketa eta txertatzeko algoritmoa deitzen zaio. Akatsa hori da noizbait izan beharko luke batzuetan.

Jakina, horrelako akats bat ez da harritzekoa. Artikulu honetan bakarrik akats batzuk egongo dira (ez dago saririk aurkitzeagatik). Benetan harrigarria dena da hainbeste denboraz oharkabean igaro izana. 392. orrialdea ez dago matematika atalean sakon lurperatuta, bai oso lehen orrialdea 6. kapitulua "Bilatu"! Beharbada, liburuaren atal irakurrienetako bat. Teorian, akats gutxien egon beharko litzateke, baina ez.

Bide batez, inoiz TAOCP irakurtzea pentsatu baduzu, proba ezazu. Askok esango dute hori dela direktorioa, ez irakurketa zuzenerako pentsatua, baina ez da egia. Ikuspuntu argia eta estilo bereizgarria du egileak. Irakurgarritasuna oztopatzen duen bakarra matematikaren konplexutasuna da. Hala ere, irtenbide sinple bat dago: irakurri ulertzen ez duzun matematikara iritsi arte, saltatu eta ulertu dezakezun hurrengo atalera joan. Horrela irakurrita, liburuaren %80 gutxienez galdu dut, baina beste %20 bikaina da!

TAOCP dela ere esaten da garrantzirik gabekoa, zaharkituta dago edo bestela ez da aplikagarria "programazio errealean". Hau ere ez da egia. Esate baterako, sarreraren ondorengo lehen atalean sailkatu gabeko array batean elementu bat aurkitzeari begiratzen da. Algoritmorik errazena programatzaile guztientzat ezaguna da. Hasi erakuslea matrizearen hasieran, eta egin ondorengoa begizta batean:

1. Egiaztatu uneko elementua nahi duzuna den. Hala bada, itzultzen dugu; bestela
2. Egiaztatu erakuslea matrizearen mugatik kanpo dagoen. Hala bada, itzuli errore bat; bestela
3. Handitu eta jarraitu.

Orain kontuan hartu: zenbat muga egiaztapen behar ditu algoritmo honek, batez beste? Kasurik txarrenean, matrizeak elementurik ez duenean, zerrendako elementu bakoitzak egiaztapen bat beharko du, eta, batez beste, antzeko zerbait izango da. . Bilaketa-algoritmo adimentsu batek mugen egiaztapen bakarrarekin ihes egin lezake. Erantsi nahi duzun elementua matrizearen amaieran, ondoren hasi erakuslea matrizearen hasieran eta egin hurrengoa begizta batean:

1. Egiaztatu uneko elementua nahi duzuna den. Hala bada, erantzun bat itzultzen dugu erakuslea array barruan badago, edo errore bat ez bada. Bestela
2. Handitu eta jarraitu.

Modu batera edo bestera, elementua aurkitzea bermatuta dago, eta mugak egiaztatzea behin bakarrik egiten da hori gertatzen denean. Ideia sakona da, baina nahikoa sinplea da programatzaile hasiberri batentzat ere. Ziurrenik ezin dut hitz egin lanak besteentzat duen garrantziaz, baina berehala lortu nuen jakinduria hori kode pertsonal zein profesionalean aplikatzeko. TAOCP liburua halako harribitxiz beteta dago (zuzena izateko, gauza bitxi asko ere badaude bertan, hala nola burbuila sorta).

"Bilatu, bilatu
Hain luzea
Bilatu, bilatu
dantza egin nahi nuen"
- Luther Vandross, "The Search" (1980)

Akatsa #2

Bigarren akatsa 4A liburukian dago, Algoritmo konbinatzaileak, 1. zatian. 60. orrialdeak hainbat kasinotan jotzeko umoristak antolatzeak dakarren arazo bat deskribatzen du. Bizitza errealeko hainbat umorista aipatzen dira adibide gisa, besteak beste, Lily Tomlin, Weird Al Yankovic eta Robin Williams, liburua argitaratu zenean oraindik bizirik zegoena. Knuth-ek beti zerrendatzen ditu izen-abizenak aurkibidean, beraz, Williams 882. orrialdean agertzen da "Williams, Robin McLorim". Baina bere bigarren izena “n”-z amaitzen da eta ez “m”, hau da, McLaurin.

McLaurin bere amaren neska-izena zen. Anselm Joseph McLaurin, Mississippiko 34. gobernadorearen birbiloba zen. Bere erregealdia, itxuraz, ez zen ezer onerako gogoratu. Liburutik "Mississippi: Historia":

«McLaurin administrazioan izandako gertaerarik garrantzitsuena Estatu Batuek Espainiari 1898ko udaberrian gerra deklaratzea izan zen... Zoritxarrez, baliteke gerrak gobernuko funtzionario batzuei eroskerian aritzeko aukera eman zien. McLaurin hainbat praktika zalantzagarri leporatu zizkioten, besteak beste, nepotismoa eta barkamen ahalmenen gehiegizko erabilera. Tenperantza mugimenduan, kritikariek mozkor bat izatea leporatu zioten gobernariari, eta hori publikoki onartu zuen».

Akats historikoa

Demagun biderketa algoritmo tradizionala eskolako curriculumetik. Zenbat zifra bakarreko biderketa behar ditu? Demagun biderkatu egiten duzula - zifra zenbakia on -bit . Lehenik eta behin biderkatu lehen zifra zifra bakoitzeko banan-banan. Ondoren, biderkatu bigarren zifra zifra bakoitzeko banan-banan eta horrela zenbaki guztiak pasatu arte . Horrela biderketa tradizionalak eskatzen du biderketa primitiboak. Bereziki, bi zenbakiz biderkatuz behar diren mailak zifra bakarreko biderketak.

Hau txarra da, baina posible da prozesua optimizatzea Anatoly Alekseevich Karatsuba sobietar matematikariak garatutako metodo bat erabiliz. Itxura dezagun hori и  - bi zifrako zenbaki hamartar; hau da, zenbakiak daude , , , hala nola и (Algoritmo hau zenbaki handiagoetara orokortzeak nolabaiteko manipulazioa eskatzen du; oso zaila ez den arren, xehetasunetan akatsik ez egiteko, hobe dut adibide sinple bati eutsiko diot). Gero , , . Binomioak biderkatzeak ematen du . Momentuz oraindik badugu zifra bakarreko biderketa: , , , . Orain batu eta ken ditzagun . Berrantolaketa batzuen ondoren, irakurleari ariketa gisa utziko ditudanak, ateratzen da  - hiru zifra bakarreko biderketa baino ez! (Koefiziente konstante batzuk daude, baina zifrak gehituz eta lekuz aldatuz bakarrik kalkula daitezke).

Ez eskatu frogarik, baina Karatsuba algoritmoa (Goiko adibidetik errekurtsiboki orokortua) biderketa metodo tradizionala hobetzen du eragiketak aurretik . Kontuan izan hau algoritmoaren benetako hobekuntza bat dela, ez kalkulu mentaletarako optimizazio bat. Izan ere, algoritmoa ez da egokia aritmetika mentalerako, gastu orokor handiak eskatzen baititu eragiketa errekurtsiboetarako. Horrez gain, efektua ez da guztiz agertuko zenbakiak nahikoa handiak izan arte (zorionez, Karatsubaren algoritmoa are metodo azkarragoekin ordezkatu da: 2019ko martxoan, algoritmo bat argitaratu zen, soilik eskatzen duena). n log n biderketak; azelerazioa imajina ezin diren kopuru handiei bakarrik aplikatzen zaie).

Algoritmo hau 295. liburukiko XNUMX. orrialdean deskribatzen da, Algoritmo erdi-zenbakikoak. Bertan Knuthek idazten du: “Bitxia da ideia hau urtean bakarrik aurkitu izana 1962 urtean", Karatsuba-ren algoritmoa deskribatzen zuen artikulu bat argitaratu zenean. Baina! 1995ean, Karatsubak "Konplexutasun Konputazionala"ri buruzko artikulu bat argitaratu zuen, eta hainbat gauza esaten zituen: 1) 1956 inguruan, Kolmogorovek iradoki zuen biderketa ezin zela egin baino gutxiagotan. urratsak; 2) in 1960 urtean Karatsuba mintegira joan zen non Kolmogorov-ek bere hipotesia n² aurkeztu zuen. 3) "Aste batean zehazki", Karatsubak "zatitu eta konkistatu" algoritmoa garatu zuen; 4) 1962an, Kolmogorovek artikulu bat idatzi eta argitaratu zuen Karatsubaren izenean algoritmoaren deskribapenarekin. "Artikulu hau berriro argitaratu ondoren bakarrik jakin nuen".

Beraz, akatsa da horren ordez 1962 zehaztu behar da 1960 urtean. Hori da dena.

Analisia

Akatsak aurkitzeko ez zen trebetasun berezirik behar.

1. Lehen akatsa ahalik eta hutsala izan zen eta leku nahiko ikusgai batean zegoen (kapituluaren hasieran). Edozein idiotak aurkituko zuen; Itzuli hori izan naiz.
2. Bigarren akatsa aurkitzeko zortea eta ardura eskatzen zuen, baina ez trebetasuna. "Williams"-en aurkibidea liburukiaren azkenaurreko orrialdean dago, liburuaren zati nahiko nabarmena. Aurkibidea arakatzen ari nintzen (ez da dirudien bezain patetikoa, Knuth-en aurkibideetan ezkutatuta daudelako Pazko arrautzak. Adibidez, arabieraz eta hebreeraz dauden sarrerak daude, biak 66. orrialdea seinalatzen dutenak. Baina orrialde horrek ez du aipatzen. bi hizkuntzak; horren ordez, "eskuinetik ezkerrera irakurtzen diren hizkuntzak" aipatzen ditu). Eta bigarren izenak atentzioa eman zidan. Normalean Wikipedia irakurtzen dudanez, Robin Williams egiaztatu nuen eta desadostasun bat nabaritu nuen.
3. Akats historiko bat aurkitzeko ikerketa serioak egin ditudala esan nahiko nuke, baina benetan begiratu besterik ez dut egin Karatsuba-ren algoritmoari buruzko Wikipedia orria. Lehenengo lerroek esaten dute: "Karatsuba algoritmoa biderkatze algoritmo azkarra da. Anatoly Karatsubak aurkitu zuen 1960an eta 1962an argitaratua". Horren ostean bi eta bi gehitzea besterik ez zen falta.

Etorkizunean akats esanguratsuago bat aurkitu nahiko nuke, batez ere Knuth-en kodean. Oinarrizko Algoritmoen lehen liburukian ere akats bat aurkitu nahiko nuke. Agian aurkituko nuen, baina arrazoiren batengatik bertako liburutegiak 2., 3. eta 4A liburukiak baino ez ditu.

Datu finantzarioak:

• Guztira, TAOCP-ri egindako ekarpena hiru pertsonaia baino ez du osatzen: gehigarri bat s, ordezkoa m on n и 2 on 0. 2,56 $-tan, ikur nahiko irabaziak dira hauek; Horrelako dirua kobratuko bazenu, 1000 hitzeko artikulu batek (batez beste lau karaktere) hamar mila irabaziko zizkizuke.
• Hiru hamaseitar dolarrekin, ni, beste 29 herritarrekin batera, 69. postuan berdinduta nago San Serriff Bankuko gordailu aberatsenen zerrendan (1ko maiatzaren 2019etik aurrera).

Knuth-en txekeei buruzko beste eztabaida batzuk

• Knuth-en txekea nola lortu

  Knuth-en liburuetan akatsak aurkitzeko gomendio orokorrak. Gehienbat akats teknikoak dira, nik ez ditudanak. Badago hor serio hartu nuen iradokizun bat:

  Hobe da errore multzo bat bildu arte itxarotea bidaltzeko. Akats errealak baina ez oso baliotsuak konbinatuz, horietako bat akats edo aholkutzat hartzeko aukera handitzen duzu. Akatsak banan-banan bidaltzen badituzu, bakoitza banan-banan baztertu daiteke.

  Ez nuen txorakeria hutsik bidali nahi, baina aholkua hartu eta gutuna nahikoa larria zirudien akats historiko bat aurkitu nuenean bakarrik bidali nuen.

• Ashutosh Mehraren txekeak

  Ashutosh Mehra San Serriffeko hirugarren inbertitzaile aberatsena da 0x207.f0 $-ko balio garbiarekin BoSS-en.

• Egiaztatu TeX kode errealeko akats ez-funtzionalak dauden
• Denetarik: #1 #2 #3 #4 #5 #6

Iturria: www.habr.com