Donald Knuth waa saynisyahan kombuyuutar oo aad u daneeya saxnaanta buugaagtiisa oo uu soo jeediyo hal dollar hex ($2,56, 0x$1,00) wixii "qalad" la helo, halkaasoo qaladka lagu qeexo wax kasta oo "farsamo ahaan, taariikh ahaan, qoraal ahaan, ama siyaasad ahaan khaldan." Runtii waxaan rabay inaan jeeg ka helo Knuth, sidaa darteed waxaan go'aansaday inaan khaladaad ka raadiyo magnum opuskiisa "Farshaxanka Barnaamijyada" (TAOCP). Waxaan ku guuleysanay inaan helno saddex. Sida uu hadalka u dhigay, Knut waxa uu soo diray jeeg 0x$3,00.
Sida aad arki karto, tani maaha jeeg dhab ah. Knuth wuxuu diri jiray jeegaga dhabta ah, laakiin wuxuu joojiyay 2008 sababtoo ah . Hadda wuxuu u soo diraa "shahaadada deebaajiga" shakhsi ahaaneed (BoSS). Wuxuu sheegay inuu diyaar u yahay inuu soo diro lacag dhab ah haddii loo baahdo, laakiin waxay u muuqataa inay tahay mid aad u dhib badan.
Waxaan helay laba qoraal iyo hal khalad taariikheed. Waxaan u tixgalin doonaa siday u kala horreeyaan wax-u-dhimista.
Nooca #1
Qormada koowaad waxay ku taal bogga 392 ee mugga saddexaad ee "Sayid iyo Raadin", xariiqda siddeedaad ee hoose: "Baadi goob aan lagu guulaysan ka dib, mararka qaarkood (mararka qaarkood) waxaa la jecel yahay in la galo rikoodh cusub miiska oo ka kooban K; Habka tan sameeya waxaa loo yaqaannaa raadinta iyo geli algorithm. Qaladku waa taas bedelkeeda marna waa in mararka qaarkood.
Dabcan, qaladka noocan oo kale ah maaha mid la yaab leh. Waxaa hubaal ah in ay jiraan qoraallo kooban oo maqaalkan oo keliya ah (wax abaal-marin ah oo lagu helo iyaga ma jiraan). Waxa runtii la yaab leh waa iyada oo aan la dareemin muddo dheer. Bogga 392 si qoto dheer uguma aasan qaybta xisaabta, waa bogga ugu horeeya Cutubka XNUMX "Raadi"! Malaha waa mid ka mid ah qaybaha ugu akhriska badan ee buugga. Aragti ahaan, waa inay jiraan kuwa ugu yar, laakiin maya.
Jid ahaan, haddii aad waligaa ka fikirtay akhrinta TAOCP, isku day. Qaar badan ayaa odhan doona tani waa hagaha, looguma talagalin akhris toos ah, laakiin tani run maaha. Qoraagu waxa uu leeyahay aragti cad iyo qaab gaar ah. Waxa kaliya ee wax u akhriyi kara waa kakanaanta xisaabta. Si kastaba ha ahaatee, waxaa jira xal fudud: akhri ilaa aad ka timaaddo xisaabta ma fahmin, ka bood, oo aad qaybta xigta oo aad fahmi karto. Akhrinta habkan, waxaan tabayaa ugu yaraan 80% buugga, laakiin 20% kale ayaa weyn!
Waxa kale oo la sheegay in TAOCP aan khusayn, waa duugoobay ama haddii kale aan lagu dabaqi karin "barnaamijka dhabta ah". Tani sidoo kale run maaha. Tusaale ahaan, qaybta koowaad ee hordhaca ka dib waxay eegaysaa helida curiye ku jira hannaan aan la kala soocin. Algorithm-ka ugu fudud waa mid ay yaqaanaan dhammaan barnaamijyada. Ka bilow tilmaanta bilowga shaxanka, ka dib samee waxa soo socda si wareeg ah:
- Hubi haddii curiyaha hadda uu yahay midka la doonayo. Hadday sidaas tahay, waanu u celinaynaa; haddii kale
- Hubi haddii tilmaamuhu uu ka baxsan yahay xuduudka diyaarinta. Hadday sidaas tahay, soo celi khalad; haddii kale
- Soo dhawaaw oo sii wad
Hadda ka fiirso: immisa xadduud jeegag ah ayaa algorithmisku u baahan yahay, celcelis ahaan? Xaaladda ugu xun, halka shaxdu aanay ku jirin curiye, xubin kasta oo liiska ku jirta waxay u baahan tahay hal jeeg, celcelis ahaanna waxay noqon doontaa wax la mid ah. 
. Algorithm raadinta ka xariifsan ayaa laga yaabaa inay ku dhaafto hal hubin oo kaliya. Ku dheji cutubka la rabo dhamaadka shaxanka, ka dibna billow tilmaanta bilowga shaxanka oo samee waxa soo socda si wareeg ah:
- Hubi haddii curiyaha hadda uu yahay midka la doonayo. Hadday sidaas tahay, waxaanu soo celinaynaa jawaabta haddii tilmaamuhu uu ku dhex jiro shaxanka, ama khalad haddii aanay ahayn. Hadii kale
- Soo dhawaaw oo sii wad
Si kastaba ha ahaatee, curiyaha waa la dammaanad qaaday in la helo, iyo hubinta xuduudaha ayaa la sameeyaa hal mar oo keliya marka tani dhacdo. Tani waa fikrad qoto dheer, laakiin waa u fududahay xitaa barnaamij-yaqaanka cusub. Waxaa laga yaabaa inaanan la hadli karin khusaynta shaqada kuwa kale, laakiin isla markiiba waxaan awooday inaan xikmaddan ku dabaqo xeerka shakhsi ahaaneed iyo kan xirfadda labadaba. Buugga TAOCP waxaa ka buuxa dhagaxyo noocan oo kale ah (si aad u noqoto mid caddaalad ah, waxaa sidoo kale jira waxyaabo badan oo la yaab leh, sida ).
"Raadi, raadi
Aad u fog
Raadi, raadi
Waxaan rabay inaan dheelo"
- Luther Vandross, "Raadinta" (1980)
Nooca #2
Nooca labaad waxa uu ku yaalaa Volume 4A, Combinatorial Algorithms, Qaybta 1. Bogga 60 waxa uu qeexayaa dhibaato ku lug leh jadwalka majaajilaystayaasha si ay uga qabtaan casinos kala duwan. Dhowr majaajilaysteyaal nolosha dhabta ah ayaa tusaale loo soo qaatay, oo ay ku jiraan Lily Tomlin, Weird Al Yankovic, iyo Robin Williams, oo weli noolaa markii buugga la daabacay. Knuth wuxuu had iyo jeer liis gareeyaa magacyo buuxa oo ku jira tusmada, sidaa darteed Williams waxa uu bogga 882 ugu qoran yahay "Williams, Robin McLorim." Laakiin magaciisa dhexe wuxuu ku dhamaanayaa "n" ee maaha "m", taas oo ah, McLaurin.
McLaurin wuxuu ahaa magaca gabadha hooyadiis. Waxay ahayd ina- ayeeyo-weyn u tahay Anselm Joseph McLaurin, Guddoomiyaha 34-aad ee Mississippi. Xukunkiisa, sida muuqata, laguma xasuusan wax wanaagsan. Laga soo bilaabo buug :
"Dhacdadii ugu muhiimsaneyd ee xilligii maamulka McLaurin waxay ahayd ku dhawaaqistii Mareykanka ee dagaalka Spain gu'gii 1898... Nasiib darro, dagaalku waxaa laga yaabaa inuu siiyay qaar ka mid ah saraakiisha dawladda fursad ay ku galaan laaluush. McLaurin waxaa lagu eedeeyay dhaqamo kala duwan oo su'aalo la iska weydiin karo, oo ay ku jiraan qaraabo kiil iyo isticmaalka xad dhaafka ah ee awoodaha cafiska. Intii lagu guda jiray dhaqdhaqaaqa dabeecadda, dhaleecayntu waxay ku eedeeyeen guddoomiyaha inuu yahay sakhraan, taas oo uu si cad u qirtay. "
Khalad taariikhi ah
Tixgeli isku dhufashada dhaqanka ee algorithm laga bilaabo manhajka dugsiga. Immisa isku dhufasho hal-god ah ayay u baahan tahay? Ka soo qaad inaad taranto 
-lambarka nambarka 
on 
-yar 
. Marka hore ku dhufo lambarka koowaad 
nambar kasta 
mid mid. Kadibna ku dhufo lambarka labaad 
nambar kasta 
mid mid iyo wixii la mid ah ilaa aad ka gudubto dhammaan tirooyinka 
. Markaa isku dhufashada dhaqanka ayaa u baahan 
dhufashada hore. Gaar ahaan, laba tiro oo lagu dhufto 
darajooyinka loo baahan yahay 
isku dhufashada hal-god.
Tani waa mid xun, laakiin waxaa suurtagal ah in la hagaajiyo habka iyadoo la adeegsanayo habka uu sameeyay xisaabiyaha Soviet Anatoly Alekseevich Karatsuba. Aan iska dhigno taas 
и 
- tirooyinka jajab tobanle ee laba-god; taas oo ah, waxaa jira tirooyin 
, 
, 
, 
sidaas oo kale 
и 
(guud ahaan algorithm-ka tirooyinka waaweyn waxay u baahan tahay wax-is-daba-marin, inkastoo aysan ahayn mid aad u adag, si aan loo khaladin faahfaahinta, waxaan si fiican ugu dhejin doonaa tusaale fudud). Markaa 
, 
, 
. Isku dhufashada laba-geesoodka ayaa bixisa 
. Waqtigan xaadirka ah weli waan haynaa 
isku dhufashada hal-god: 
, 
, 
, 
. Imika aynu ku darno oo ka jarno 
. Dhawr dib-u-habayn ka dib, oo aan u dhaafi doono layliga akhristaha, waxa soo baxaysa 
- kaliya saddex isku dhufasho hal-god ah! (Waxaa jira qaar isku-dhafan oo joogto ah, laakiin waxa lagu xisaabin karaa oo keliya in lagu daro oo la beddelo tirooyinka).
Ha waydiin caddayn, laakiin Karatsuba algorithm (oo si isdaba joog ah loo soo koobay tusaalaha kore) waxay horumarisaa habka isku dhufashada ee soo jireenka ah 
hawlgallada ka hor 
. Fadlan ogow in tani ay tahay horumar dhab ah oo algoorithm ah, ma aha hagaajinta xisaabinta maskaxda. Runtii, algorithmku kuma habboona xisaabinta maskaxda, maadaama ay u baahan tahay kharashyo badan oo dheeraad ah oo loogu talagalay hawlgallada soo noqnoqda. Intaa waxaa dheer, saameyntu si buuxda uma muujin doonto ilaa tirooyinka ay noqdaan kuwo ku filan (nasiib wanaag, Karatsuba's algorithm waxaa lagu beddelay xitaa habab degdeg ah: Maarso 2019, algorithm ayaa la daabacay oo u baahan kaliya isku dhufashada; dardargelinta waxay khusaysaa oo keliya tirooyinka aan la malayn karin).
Algorithm-kan waxa lagu sifeeyay bogga 295 ee Volume XNUMX, Algorithms Semi-numerical. Halkaa Knuth waxa uu qoray: “Waxaa cajiib ah in fikraddan laga helay oo keliya 1962 sanadka,” markii maqaal qeexaya algorithm Karatsuba la daabacay. Laakiin! Sannadkii 1995kii, Karatsuba waxa uu daabacay warqad ku saabsan "Computational Complexity," oo leh dhowr waxyaalood: 1) Qiyaastii 1956, Kolmogorov waxa uu soo jeediyay in isku dhufashada aan lagu samayn karin wax ka yar. 
talaabooyinka; 2) in 1960 sanadka Karatsuba waxa uu ka qayb galay siminaarka halkaas oo Kolmogorov uu ku soo bandhigay fikradiisa n². 3) "Si sax ah hal usbuuc," Karatsuba wuxuu sameeyay "qaybi oo guulaysta" algorithm; 4) 1962, Kolmogorov ayaa qoray oo daabacay maqaal anigoo ku hadlaya magaca Karatsuba oo leh sharaxaad algorithm. "Waxaan ka war helay maqaalkan ka dib markii dib loo daabacay."
Markaa khaladku waa taas beddelkeeda 1962 waa in la qeexaa 1960 sanad. Waa intaas.
Анализ
Helitaanka khaladaadka uma baahna xirfad gaar ah.
- Qaladka hore waxa uu ahaa mid fudud intii suurtagal ah oo waxa uu ahaa meel muuqata (bilawga cutubka). Doqon kasta wuu heli lahaa; Waxaan noqday doqonkaas.
- Helitaanka typo labaad waxay u baahan tahay nasiib iyo dadaal, laakiin xirfad uma baahna. Tusmada "Williams" waxay ku taal bogga ugu sarreeya ee mugga, qayb caan ah oo buugga ah. Waxa aan iska dhex rog-rogayay tusmada (ma aha sida ay u muuqato naxariis, sababtoo ah waxaa jira ukumo Easter ah oo ku qarsoon tusmooyinka Knuth. Tusaale ahaan, waxaa jira qoraallo ku qoran Carabi iyo Cibraaniga, labaduba waxay tilmaamayaan bogga 66. Laakiin boggaas ma sheegin Luqadaha midkood; beddelkeeda waxay tilmaamaysaa "luqadaha laga akhriyo midig ilaa bidix"). Magaca labaadna wuxuu soo jiitay dareenkayga. Maadaama aan inta badan akhriyo Wikipedia, waxaan hubiyay Robin Williams oo waxaan arkay farqi.
- Waxaan jeclaan lahaa inaan dhihi karo waxaan sameeyay cilmi baaris dhab ah si aan u helo khalad taariikhi ah, laakiin runtii waan eegay . Sadarka ugu horreeya waxay leeyihiin: "Algorithm-ka Karatsuba waa algorithm isku dhufasho degdeg ah. Waxaa helay Anatoly Karatsuba 1960-kii oo la daabacay 1962-kii." Intaa ka dib waxa hadhay oo dhan waa in laba iyo laba lagu daro.
Mustaqbalka waxaan jeclaan lahaa inaan helo bug ka sii muhiimsan, gaar ahaan koodhka Knuth. Waxa kale oo aan jeclaan lahaa in aan ka helo bug mugga koowaad ee Algorithms Asaasiga ah. Waxaa laga yaabaa inaan heli lahaa, laakiin sabab qaar ka mid ah maktabadda maxalliga ahi waxay leedahay oo keliya mugga 2, 3 iyo 4A.
Xaqiiqooyinka maaliyadeed:
- Wadar ahaan, wax ku biirintayda TAOCP waxay ka kooban tahay saddex xaraf oo keliya: hal ku dar s, beddelka m on n и 2 on 0. Markay tahay $2,56, kuwani waa calaamado faa'iido badan leh; Haddii lagu siiyo lacagta noocaas ah, qodob ka kooban 1000 kelmadood (celcelis ahaan afar xaraf) ayaa ku heli doona toban weyn.
- Iyada oo leh saddex dollar oo hexadecimal ah, aniga, oo ay weheliyaan 29 muwaadin oo kale, waxa aan ku xidhanahay kaalinta 69-aad ee liiska dhigaaliyayaasha ugu qanisan San Serriff Bank (laga bilaabo Maajo 1, 2019).
Wadahadalo kale oo ku saabsan jeegaga Knuth
Talooyinka guud ee lagu heli karo khaladaadka buugaagta Knuth. Inta badan waxay khuseeyaan khaladaad farsamo, oo aanan haysan. Halkaa waxaa jirta hal talo oo aan si dhab ah u qaatay:
Way fiicantahay inaad sugto ilaa aad ka soo ururinayso khaladaadyo aad gudbinayso. Marka la isku daro dhowr khaladaad oo dhab ah balse aan qiimo badan lahayn, waxaad kordhinaysaa suurtogalnimada in mid iyaga ka mid ah loo arko khalad ama talo. Haddii aad khaladaadka hal mar u soo gudbiso, mid walba si gaar ah ayaa loo diidi karaa.
Ma rabin inaan diro qoraallo aan macno lahayn, laakiin waan qaatay oo warqadda u diray markii aan helay khalad taariikhi ah oo u muuqday mid culus.
Ashutosh Mehra waa maalgeliyaha saddexaad ee ugu qanisan San Serriff oo leh qiimihiisu yahay 0x$207.f0 gudaha BoSS.
- Waxyaabo kala duwan:
Source: www.habr.com
