Donald Knuth musayendisiti wekombiyuta ane hanya zvikuru nokururama kwemabhuku ake ayo anokarakadza imwe hex dhora ($2,56, 0x$1,00) chero "chikanganiso" chawanikwa, apo kukanganisa kunotsanangurwa sechinhu chipi nechipi "chine ruzivo, nhoroondo, typographically, kana zvematongerwo enyika zvisiri izvo." Ini ndaida chaizvo kuwana cheki kubva kuKnuth, saka ndakafunga kutsvaga zvikanganiso mune yake magnum opus "Art of Programming" (TAOCP). Takakwanisa kuwana matatu. Seshoko rake, Knut akatumira cheki 0x$3,00.

Sezvaunogona kuona, iyi haisi cheki chaiyo. Knuth aimbotumira macheki chaiwo, asi akamira muna 2008 nekuda kwe hutsotsi hwatekeshera. Iye zvino anotumira "personal certificate of deposit" kuna Bhanga reSan Serriff (BoSS). Anoti anoda kutumira mari chaiyo kana zvichidiwa, asi zvinoita sekunge zvakanyanya kunetsa.

Ndakawana maviri typos uye imwe nhoroondo kukanganisa. Ndichaanyora muhurongwa hwekudzikira nhando.

Typo #1

Yekutanga typo iri papeji 392 yevhoriyamu yechitatu "Kuronga uye Kutsvaga", mutsara wechisere kubva pasi: "Mushure mekutsvaga kusingabudiriri, dzimwe nguva (dzimwe nguva) zvinodikanwa kuisa rekodhi nyowani mutafura ine. K; nzira inoita izvi inonzi yekutsvaga uye kuisa algorithm. Chikanganiso ndechekuti pane kudaro imwe nguva dzinofanira kuva dzimwe nguva.

Zvechokwadi, kukanganisa kwakadaro hakushamisi. Panofanira kunge paine mashoma typos muchinyorwa ichi chete (hapana mibairo yekuawana). Chinonyanya kushamisa ndechekuti yakaenda isingazivikanwi kwenguva yakareba. Peji 392 haina kuvigwa zvakadzika muchikamu chesvomhu, ndizvo peji rekutanga chairo Chitsauko 6 "Tsvaga"! Zvichida chimwe chezvikamu zvinoverengwa zvakanyanya mubhuku racho. Muchirevo, panofanira kunge paine mashoma typos, asi kwete.

Nenzira, kana iwe wakambofunga nezve kuverenga TAOCP, edza. Vazhinji vachati ndizvozvo dhairekitori, isina kuitirwa kuverenga zvakananga, asi ichi hachisi chokwadi. Munyori ane maonero akajeka uye maitiro akasiyana. Chinhu chimwe chete chinotadzisa kuverenga ndiko kuoma kwesvomhu. Zvisinei, pane mhinduro iri nyore: verenga kusvika wasvika pasvomhu dzausinganzwisise, svetuka, uye enda kuchikamu chinotevera chaunogona kunzwisisa. Kuverenga nenzira iyi, ndinosuwa kanenge 80% yebhuku, asi imwe 20% yakanaka!

Zvinonzi zvakare TAOCP zvisina basa, ndeyechinyakare kana neimwe nzira isingashande kune "chaiyo programming". Ichi hachisiwo chokwadi. Semuenzaniso, chikamu chekutanga mushure mekusuma chinotarisa kutsvaga chinhu mune isina kurongedzwa. Iyo yakapfava algorithm inozivikanwa kune vese programmers. Tanga chinongedzo pakutanga kwehurongwa, wozoita zvinotevera muchiuno:

1. Tarisa kana chinhu chazvino chiri icho chinodiwa. Kana zvakadaro, tinoidzorera; zvimwe
2. Tarisa kana chinongedzo chiri kunze kwemuganho wehurongwa. Kana zvakadaro, dzorera kukanganisa; zvimwe
3. Zoom in uye enderera mberi.

Zvino funga: mangani macheki anodiwa nealgorithm iyi, paavhareji? Muchiitiko chakaipisisa, apo hurongwa husina chinhu, chinhu chimwe nechimwe chiri muchirongwa chinoda cheki imwe, uye paavhareji chichava chimwe chinhu chakadai. . Iyo yakangwara yekutsvaga algorithm inogona kupukunyuka necheki imwe chete yemiganhu. Natanidza chinhu chaunoda kusvika kumagumo ehurongwa, wobva watanga chinongedzo pakutanga kweiyo array uye ita zvinotevera mu loop:

1. Tarisa kana chinhu chazvino chiri icho chinodiwa. Kana zvakadaro, tinodzosera mhinduro kana chinongedzo chiri mukati mehurongwa, kana kukanganisa kana zvisiri. Zvikasadaro
2. Zoom in uye enderera mberi.

Imwe nzira kana imwe, chinhu chinovimbiswa kuwanikwa, uye cheki yemiganhu inoitwa kamwe chete kana izvi zvaitika. Iyi ipfungwa yakadzama, asi iri nyore zvakakwana kunyange kune novice programmer. Ini pamwe handigone kutaura kune kukosha kwebasa kune vamwe, asi ini ndakabva ndakwanisa kushandisa huchenjeri uhu kune zvese zvemunhu nehunyanzvi kodhi. Bhuku reTAOCP rizere nematombo akadaro (kutaura zvakanaka, kunewo zvinhu zvakawanda zvinoshamisa imomo, senge. bubble sort).

"Tsvaga, tsvaga
Kwazvino
Tsvaga, tsvaga
ndaida kutamba chete"
- Luther Vandross, "The Search" (1980)

Typo #2

Yechipiri typo iri muVhoriyamu 4A, Combinatorial Algorithms, Chikamu 1. Peji 60 inotsanangura dambudziko rinosanganisira kuronga vanoseka kuti vaite pamakasino akasiyana. Vati wandei vehupenyu vanosetsa vanotaurwa semienzaniso, kusanganisira Lily Tomlin, Weird Al Yankovic, naRobin Williams, uyo akange achiri mupenyu pakadhindwa bhuku. Knuth anogara achinyora mazita akazara muindex, saka Williams akanyorwa papeji 882 se "Williams, Robin McLorim." Asi zita rake repakati rinopera ne "n" uye kwete "m", kureva, McLaurin.

McLaurin raive zita remhandara raamai vake. Aive muzukuru-muzukuru waAnselm Joseph McLaurin, 34th Gavhuna weMississippi. Kutonga kwake, sezviri pachena, hakuna kuyeukwa nokuda kwechinhu chipi nechipi chakanaka. Kubva mubhuku "Mississippi: Nhoroondo":

“Chiitiko chinonyanya kukosha panguva yekutonga kweMcLaurin chaiva kuzivisa kweUnited States kwehondo kuSpain muchirimo cha1898... Zvinosuruvarisa kuti hondo yacho ingave yakapa vamwe vakuru vakuru vehurumende mukana wokuita chiokomuhomwe. McLaurin akapomerwa maitiro akasiyana-siyana asina chokwadi, kusanganisira kushamwaridzana uye kushandisa zvakanyanya masimba ekuregererwa. Mukati mesangano rokuzvidzora, vatsoropodzi vakapomera gavhuna wacho kuva chidhakwa, izvo akabvuma pachena.”

Kukanganisa kwenhoroondo

Funga zvechinyakare kuwanda algorithm kubva kuzvidzidzo zvechikoro. Inoda kuwanda kwemanhamba mangani? Tomboti wawanza -nhamba yenhamba pamusoro -bit . Tanga wawedzera nhamba yekutanga yedijiti imwe neimwe mumwe nemumwe. Wowedzera nhamba yechipiri yedijiti imwe neimwe one by one and so on kusvika mapinda manhamba ese . Saka kuwanda kwechinyakare kunoda kuwanda kwepakutanga. Kunyanya, kuwedzera nhamba mbiri ne masanji anodiwa kuwanda kwenhamba imwe.

Izvi zvakaipa, asi zvinokwanisika kukwidziridza maitiro uchishandisa nzira yakagadzirwa neSoviet masvomhu Anatoly Alekseevich Karatsuba. Ngatiedzei kuti и  - manhamba maviri edesimali nhamba; kureva kuti pane nhamba , , , zvakadaro и (kugonesa iyi algorithm kunhamba hombe kunoda kumwe kunyengedza; kunyangwe isina kunyanyo kuoma, kuti ndisaite zvikanganiso mune izvo, ini ndinonamatira zviri nani kumuenzaniso wakapfava). Zvadaro , , . Kuwedzera mabinomials kunopa . Parizvino tichiri kuwanza kwenhamba imwe: , , , . Zvino ngatiwedzerei nekubvisa . Mushure mekugadzirisa zvishoma, izvo zvandichasiya sechiitwa chemuverengi, zvinobuda  - matatu chete manhamba ekuwedzera! (Kune mamwe macoefficients anogara aripo, asi anogona kuverengerwa chete nekuwedzera nekuchinja manhamba).

Usabvunze humbowo, asi Karatsuba algorithm (inodzokororwa kubva pamuenzaniso uri pamusoro) inovandudza nzira yechinyakare yekuwanza ne maoparesheni pamberi . Ndokumbira utarise kuti iyi igadziriso chaiyo kune algorithm, kwete optimization yekuverenga kwepfungwa. Hongu, iyo algorithm haina kukodzera svomhu dzepfungwa, sezvo ichida mari yakawanda yepamusoro yekudzokorodza mashandiro. Uye zvakare, mhedzisiro yacho haizozviratidze zvizere kudzamara nhamba dzakura zvakakwana (nerombo rakanaka, Karatsuba's algorithm yakatsiviwa nenzira dzinokurumidza: muna Kurume 2019, algorithm yakabudiswa iyo inoda chete. n log n kuwanda; kukwidziridza kunoshanda chete kunhamba huru zvisingafungidzirwe).

Iyi algorithm inotsanangurwa papeji 295 yeVolume XNUMX, Semi-Numerical Algorithms. Ikoko Knuth anonyora kuti: “Zvinoda kuziva kuti pfungwa iyi yakawanikwa chete 1962 gore,” pakabudiswa chinyorwa chinotsanangura algorithm yaKaratsuba. Asi! Muna 1995, Karatsuba akaburitsa bepa pamusoro pe“Computational Complexity,” rinotaura zvinhu zvakati kuti: 1) Kuma 1956, Kolmogorov akataura kuti kuwandisa hakugone kuitwa zvishoma pane. matanho; 2) muri 1960 gore Karatsuba akapinda musemina uko Kolmogorov akapa pfungwa yake n². 3) "Muvhiki imwe chete," Karatsuba akagadzira "kupatsanura uye kukunda" algorithm; 4) muna 1962, Kolmogorov akanyora uye akabudisa nyaya pachinzvimbo cheKaratsuba ine tsananguro yealgorithm. “Ndakazongoziva nezvechinyorwa ichi pashure pokunge chadhindwazve.”

Saka kukanganisa ndiko kuti panzvimbo 1962 inofanira kutaurwa 1960 gore. Ndizvo zvose.

Analysis

Kutsvaga zvikanganiso zvaisada hunyanzvi hunokosha.

1. Chikanganiso chekutanga chaive chidiki sezvinobvira uye chaive munzvimbo inooneka (kutanga kwechitsauko). Chero idiot dai akariwana; Ndakabva ndangove benzi riya.
2. Kuwana typo yechipiri kwaida rombo rakanaka uye kushingaira, asi kwete unyanzvi. Indekisi ye "Williams" iri papeji yekupedzisira yevhoriyamu, chikamu chakatanhamara chebhuku. Ndaingopenengura indekisi (hazvisi zvinonzwisa tsitsi sezvazvinonzwika, nokuti kune mazai eIsita akavigwa mumaindekisi eKnuth. Somuenzaniso, pane zvinyorwa muArabic nechiHebheru, zvose zvichinongedzera kupeji 66. Asi peji iyoyo haitauri chero mitauro; panzvimbo pezvo zvinoreva "mitauro inoverengwa kubva kurudyi kuenda kuruboshwe"). Uye zita rechipiri rakabata pfungwa dzangu. Sezvo ini kazhinji ndaiverenga Wikipedia, ndakatarisa Robin Williams uye ndakaona mutsauko.
3. Ndinoshuva kuti dai ndaita tsvakurudzo yakakomba kuti ndiwane kukanganisa kwezvakaitika kare, asi chaizvoizvo ndakangotarisa Wikipedia peji nezve Karatsuba's algorithm. Mitsetse yekutanga inoti: "Karatsuba algorithm inokurumidza kuwanza algorithm. Yakawanikwa naAnatoly Karatsuba muna 1960 uye yakabudiswa muna 1962. Mushure mezvo chakanga changosara kuwedzera zviviri zviviri.

Mune ramangwana ndinoda kuwana akanyanya kukosha bug, kunyanya muKnuth's kodhi. Ini ndodawo kuwana bug muvhoriyamu yekutanga yeFundamental Algorithms. Pamwe ndingadai ndakaiwana, asi nokuda kwechimwe chikonzero raibhurari yeko inongova nevhoriyamu 2, 3 uye 4A.

Chokwadi chezvemari:

• Pakazara, mupiro wangu kuTAOCP une mavara matatu chete: kuwedzera kumwe s, kutsiva m pamusoro n и 2 pamusoro 0. Pa $2,56, izvi zvimwe zviratidzo zvinobhadhara; Kana iwe waibhadharwa mari yakadaro, chinyorwa chemashoko 1000 (avhareji yemabhii mana) yaizokuwanisa gumi guru.
• Nemadhora matatu ane hexadecimal, ini, pamwe nevamwe vagari makumi maviri nevapfumbamwe, takasungirirwa nzvimbo yechimakumi matanhatu nepfumbamwe pane rondedzero yevakapfuma mari yebhangi reSan Serriff Bank (kubva muna Chivabvu 29, 69).

Dzimwe nhaurirano nezve cheki kubva kuKnuth

• Nzira yekuwana cheki kubva kuKnuth

  General kurudziro yekutsvaga zvikanganiso mumabhuku aKnuth. Zvizhinji zvine chekuita nezvikanganiso zvehunyanzvi, izvo zvandisina. Pane imwe pfungwa ipapo yandakatora zvakanyanya:

  Zvakanakisa kumirira kusvika waunganidza seti yezvikanganiso kuti utumire. Nekusanganisa akati wandei chaiwo asi asiri akakosha zvikanganiso, iwe unowedzera mukana wekuti chimwe chazvo chinozoonekwa sekukanganisa kana zano. Kana ukatumira zvikanganiso chimwe panguva, chimwe nechimwe chinogona kurambwa.

  Ini ndanga ndisingadi kutumira zvisina maturo typos, asi ndakatora zano ndokutumira tsamba chete pandakawana chikanganiso chenhoroondo chaiita sechakanyanya zvakakwana.

• Ashutosh Mehra's cheki

  Ashutosh Mehra ndiye wechitatu akapfuma investor muSan Serriff ane mambure akakosha e0x$207.f0 muBoSS.

• Tarisa kune mamwe asiri-anoshanda bugs mune chaiyo TeX kodhi
• Kusiyana-siyana: #1 #2 #3 #4 #5 #6

Source: www.habr.com