Donald Knuth usosayensi wama-computer okukhathalela kakhulu ukunemba kwezincwadi zakhe aze asikisele idola elilodwa le-hex ($2,56, 0x$1,00) nganoma yiliphi "iphutha" elitholiwe, lapho iphutha lichazwa njenganoma yini "engalungile ngokobuchwepheshe, ngokomlando, ngokubhala, noma ngokwepolitiki." Bengifuna ngempela ukuthola isheke ku-Knuth, ngakho nginqume ukubheka amaphutha ku-magnum opus yakhe "I-Art of Programming" (TAOCP). Sikwazile ukuthola ezintathu. Ngokuvumelana nezwi lakhe, u-Knut wathumela isheke 0x$3,00.
Njengoba ubona, lokhu akulona isheke langempela. U-Knuth wayevame ukuthumela amasheke angempela, kodwa wayeka ngo-2008 ngenxa . Manje usethumela "izitifiketi zomuntu siqu zediphozi" ku (BoSS). Uthi uzimisele ukuthumela imali yangempela uma kunesidingo, kodwa kubonakala sengathi kunzima kakhulu.
Ngithole ama-typos amabili nephutha elilodwa lomlando. Ngizowabala ngokulandelana kokuncipha kwezinto ezincane.
Uhlobo #1
I-typo yokuqala isekhasini 392 lomqulu wesithathu othi "Ukuhlunga Nokusesha", umugqa wesishiyagalombili ukusuka phansi: "Ngemuva kokusesha okungaphumelelanga, ngezinye izikhathi (ngezinye izikhathi) kuyafiseleka ukufaka irekhodi elisha etafuleni eliqukethe. K; indlela eyenza lokhu ibizwa ngokuthi i-algorithm yokusesha nokufaka. Iphutha ukuthi esikhundleni ngesinye isikhathi kufanele ngezinye izikhathi.
Yiqiniso, iphutha elinjalo alimangalisi. Kuzoba nama-typos ambalwa kulesi sihloko kuphela (ayikho imivuzo yokuwathola). Okumangazayo kakhulu ukuthi akwenzekanga isikhathi eside kangaka. Ikhasi 392 alingcwatshwa ekujuleni kwesigaba sezibalo, kunjalo ikhasi lokuqala Isahluko 6 "Sesha"! Mhlawumbe esinye sezigaba ezifundwa kakhulu zencwadi. Ngokombono, kufanele kube nama-typos ambalwa kakhulu, kodwa cha.
Nokho, uma uke wacabanga ngokufunda i-TAOCP, izame. Abaningi bazothi lokhu umkhombandlela, akuhloselwe ukufundwa okuqondile, kodwa lokhu akulona iqiniso. Umbhali unombono ocacile kanye nesitayela esihlukile. Okuwukuphela kwento evimbela ukufunda ubunkimbinkimbi bezibalo. Nokho, kunesixazululo esilula: funda uze ufike ezibalweni ongaziqondi, weqe, bese uya esigabeni esilandelayo osiqondayo. Ukufunda ngale ndlela, ngiphuthelwa okungenani i-80% yencwadi, kodwa enye i-20% yinhle!
Kuthiwa futhi i-TAOCP okungabalulekile, isiphelelwe yisikhathi noma ayisebenzi "ekuhlelweni lwangempela". Lokhu nakho akulona iqiniso. Isibonelo, isigaba sokuqala ngemva kwesingeniso sibheka ukuthola i-elementi kumalungu afanayo angahlungiwe. I-algorithm elula ijwayelekile kubo bonke abahleli bohlelo. Qala i-pointer ekuqaleni kwamalungu afanayo, bese wenza okulandelayo ku-loop:
- Hlola ukuthi i-elementi yamanje iyona efiselekayo yini. Uma kunjalo, siyayibuyisela; kungenjalo
- Hlola ukuthi isikhombi singaphandle komngcele wamalungu afanayo. Uma kunjalo, buyisela iphutha; kungenjalo
- Sondeza futhi uqhubeke.
Manje cabanga: zingaki amasheke emingcele adingwa yile algorithm, ngokwesilinganiso? Esimeni esibi kakhulu, lapho uhlu lungenayo i-elementi, i-elementi ngayinye ohlwini izodinga isheke elilodwa, futhi ngokwesilinganiso izoba into efana nalena. 
. I-algorithm yosesho ehlakaniphe kakhudlwana ingase ibaleke nokuhlolwa kwemingcele okukodwa. Namathisela into oyifunayo ekugcineni kwamalungu afanayo, bese uqala isikhombi ekuqaleni kwamalungu afanayo futhi wenze okulandelayo ku-loop:
- Hlola ukuthi i-elementi yamanje iyona yini oyifunayo. Uma kunjalo, sibuyisela impendulo uma isikhombisi singaphakathi kwamalungu afanayo, noma iphutha uma lingekho. Kungenjalo
- Sondeza futhi uqhubeke.
Ngandlela thize, isici siqinisekisiwe ukuthi sizotholakala, futhi ukuhlolwa kwemingcele kwenziwa kanye kuphela uma lokhu kwenzeka. Lona umqondo ojulile, kodwa ulula ngokwanele ngisho nakumhleli we-novice. Cishe angikwazi ukukhuluma nokuhlobana komsebenzi kwabanye, kodwa ngikwazile ngokushesha ukusebenzisa lokhu kuhlakanipha kukho kokubili ikhodi yomuntu siqu neyomsebenzi. Incwadi ye-TAOCP igcwele amagugu anjalo (ukukhuluma iqiniso, kunezinto eziningi eziyinqaba lapho, njengokuthi ).
"Sesha, sesha
Isikhathi eside kangaka
Sesha, sesha
Bengifuna ukudansa"
- ULuther Vandross, "Usesho" (1980)
Uhlobo #2
I-typo yesibili ikuVolumu 4A, I-Combinatorial Algorithms, Ingxenye 1. Ikhasi 60 lichaza inkinga ehlanganisa ukuhlela osomahlaya ukuthi bacule emakhasino ahlukahlukene. Osomahlaya abaningana abaphila ngokoqobo okubalulwe njengezibonelo, okuhlanganisa uLily Tomlin, Weird Al Yankovic, noRobin Williams, owayesaphila ngesikhathi kushicilelwa le ncwadi. U-Knuth uhlale ebhala amagama aphelele kunkomba, ngakho-ke uWilliams ubalwe ekhasini 882 njengo-"Williams, Robin McLorim." Kodwa igama lakhe eliphakathi liphetha ngokuthi "n" hhayi "m", okungukuthi, McLaurin.
UMcLaurin kwakuyigama likamama wakhe. Wayengumzukulu ka-Anselm Joseph McLaurin, uMbusi wama-34 waseMississippi. Ukubusa kwakhe, ngokusobala, akuzange kukhunjulwe nganoma yini enhle. Kusuka encwadini :
“Isenzakalo esibaluleke kakhulu phakathi nokuphatha kukaMcLaurin kwakuyisimemezelo sempi sase-United States eSpain entwasahlobo ka-1898... Ngeshwa, kungenzeka ukuthi impi yanikeza ezinye izikhulu zikahulumeni ithuba lokuhileleka ekugwaziseni. UMcLaurin wayesolwa ngemikhuba ehlukahlukene engabazekayo, ehlanganisa ukucwasana kanye nokusebenzisa ngokweqile amandla okuxolela. Ngesikhathi kuqhubeka le nhlangano, abagxeki basola umbusi ngokuthi uyisidakwa, okuyinto ayivuma obala.”
Iphutha elingokomlando
Cabanga i-algorithm yokuphindaphinda yendabuko kusukela kukharikhulamu yesikole. Kudingeka ukuphindaphinda okungaki kwedijithi eyodwa? Ake sithi uyaphindaphinda 
-inombolo yedijithi 
on 
- kancane 
. Qala ngokuphindaphinda idijithi yokuqala 
ngedijithi ngayinye 
kunye ngakunye. Bese uphindaphinda idijithi yesibili 
ngedijithi ngayinye 
ngamunye ngamunye njalonjalo uze udlule kuzo zonke izinombolo 
. Ngakho ukuphindaphinda okungokwesiko kudinga 
ukuphindaphindeka kwakudala. Ikakhulukazi, ukuphindaphinda izinombolo ezimbili nge 
amazinga adingekayo 
ukuphindaphinda kwedijithi eyodwa.
Lokhu kubi, kodwa kungenzeka ukwandisa inqubo ngokusebenzisa indlela eyakhiwe isazi sezibalo saseSoviet u-Anatoly Alekseevich Karatsuba. Ake senze sengathi 
и 
- izinombolo zamadesimali ezinamadijithi amabili; okungukuthi, kukhona izinombolo 
, 
, 
, 
kanjalo 
и 
(ukwenza le-algorithm ibe izinombolo ezinkulu kudinga ukukhwabanisa okuthile; nakuba kungenzima kakhulu, ukuze ungenzi amaphutha emininingwaneni, ngizonamathela kangcono esibonelweni esilula). Khona-ke 
, 
, 
. Ukuphindaphinda ama-binomials kunikeza 
. Okwamanje sisenayo 
ukuphindaphinda kwedijithi eyodwa: 
, 
, 
, 
. Manje ake sengeze futhi sisuse 
. Ngemuva kokuhlela kabusha okumbalwa, engizokushiya njengomsebenzi womfundi, kuvele 
- ukuphindaphindeka kwedijithi eyodwa ezintathu kuphela! (Kunamanye ama-coefficients angashintshi, kodwa angabalwa kuphela ngokungeza nokugudluza amadijithi).
Ungabuzi ubufakazi, kodwa I-algorithm ye-Karatsuba (okwenziwa ngokuphindaphindiwe kusuka kusibonelo esingenhla) ithuthukisa indlela yokuphindaphinda evamile nge 
imisebenzi ngaphambili 
. Sicela uqaphele ukuthi lokhu ukuthuthukiswa kwangempela ku-algorithm, hhayi ukulungiselelwa kokubala kwengqondo. Ngempela, i-algorithm ayifanele i-arithmetic yengqondo, ngoba idinga izindleko ezinkulu zemisebenzi ephindaphindayo. Ngaphezu kwalokho, umphumela ngeke uzibonakalise ngokugcwele kuze kube yilapho izinombolo ziba zikhulu ngokwanele (ngenhlanhla, i-algorithm ye-Karatsuba ithathelwe indawo nezindlela ezisheshayo: ngoMashi 2019, i-algorithm yashicilelwa edinga kuphela. ukuphindaphindeka; ukusheshisa kusebenza kuphela ezinombolweni ezinkulu ngendlela engakholeki).
Le algorithm ichazwe ekhasini 295 loMqulu XNUMX, Ama-Semi-Numerical Algorithms. Lapho uKnuth uyabhala: “Kuyathakazelisa ukuthi lo mbono watholakala kuphela 1962 unyaka,” lapho i-athikili echaza i-algorithm ye-Karatsuba ishicilelwa. Kodwa! Ngo-1995, uKaratsuba washicilela iphepha elithi "Computational Complexity", elisho izinto ezimbalwa: 1) cishe ngo-1956, u-Kolmogorov waphakamisa ukuthi ukuphindaphinda ngeke kwenziwe ngaphansi kwe 
izinyathelo; 2) phakathi 1960 ngonyaka uKaratsuba waya emhlanganweni lapho uKolmogorov ethula khona umbono wakhe othi n². 3) “Ngesonto elilodwa impela,” uKaratsuba wasungula i-algorithm ethi “hlukanisa futhi unqobe”; 4) ngo-1962 uKolmogorov wabhala futhi washicilela isihloko egameni likaKaratsuba ngencazelo ye-algorithm. “Ngaze ngathola ngalesi sihloko ngemva kokuba siphinde sanyatheliswa.”
Ngakho iphutha liwukuthi esikhundleni 1962 kufanele icaciswe 1960 unyaka. Yilokho kuphela.
Анализ
Ukuthola amaphutha kwakungadingi ikhono elikhethekile.
- Iphutha lokuqala laliyinto encane ngangokunokwenzeka futhi lalisendaweni ebonakalayo (ekuqaleni kwesahluko). Noma yisiphi isiphukuphuku ngabe usitholile; Ngivele ngibe yileso silima.
- Ukuthola uhlobo lwesibili lokuthayipha kudinga inhlanhla nokukhuthala, kodwa hhayi ikhono. Inkomba ye-"Williams" isekhasini lokugcina levolumu, ingxenye evelele yencwadi. Bengimane ngiphenya inkomba (ayidabuki njengoba izwakala, ngoba kunamaqanda ePhasika afihlwe ezikhombeni zika-Knuth. Ngokwesibonelo, kukhona okubhalwe ngesi-Arabhu nesiHebheru, zombili zikhomba ekhasini 66. Kodwa lelo khasi alisho noma yiziphi izilimi; esikhundleni salokho isho “izilimi ezifundwa ukusuka kwesokudla kuye kwesobunxele”). Negama lesibili langibamba. Njengoba ngivame ukufunda i-Wikipedia, ngibheke uRobin Williams futhi ngabona ukungafani.
- Ngifisa sengathi ngingathi ngenze ucwaningo olunzulu ukuze ngithole iphutha lomlando, kodwa empeleni ngivele ngabheka . Imigqa yokuqala ithi: “I-algorithm ye-Karatsuba iyi-algorithm yokuphindaphinda okusheshayo. Itholwe ngu-Anatoly Karatsuba ngo-1960 futhi yanyatheliswa ngo-1962. Emva kwalokho osekusele ukuthi kwengezwe amabili nambili.
Ngokuzayo ngingathanda ukuthola iphutha elibaluleke kakhulu, ikakhulukazi kukhodi ka-Knuth. Ngingathanda futhi ukuthola iphutha kuvolumu yokuqala ye-Fundamental Algorithms. Mhlawumbe ngabe ngiyitholile, kodwa ngesizathu esithile umtapo wolwazi wendawo unemiqulu 2, 3 kanye no-4A kuphela.
Amaqiniso ezezimali:
- Sekukonke, umnikelo wami ku-TAOCP unezinhlamvu ezintathu kuphela: ukuhlanganisa okukodwa s, esikhundleni m on n и 2 on 0. Ku-$2,56, lezi ezinye zezimpawu ezinenzuzo enhle; Uma ukhokhelwe lolo hlobo lwemali, isiqephu sendatshana samagama ayi-1000 (isilinganiso sezinhlamvu ezine) singakuzuzela okuhle okuyishumi.
- Ngamadola amathathu e-hexadecimal, mina, kanye nezinye izakhamizi ezingama-29, siboshelwe endaweni yama-69 ohlwini lwabacebe kakhulu bama-depositors e-San Serriff Bank (kusukela ngoMeyi 1, 2019).
Ezinye izingxoxo mayelana namasheke avela e-Knuth
Izincomo ezijwayelekile zokuthola amaphutha ezincwadini zika-Knuth. Ikakhulukazi athinta amaphutha ezobuchwepheshe, engingenawo. Kunesiphakamiso esisodwa lapho engisithathe ngokungathí sina:
Kungcono ukulinda uze uqoqe isethi yamaphutha ukuze uyihambise. Ngokuhlanganisa amaphutha amaningana angempela kodwa angabalulekile kakhulu, wandisa amathuba okuthi elinye lawo lizothathwa njengephutha noma iseluleko. Uma uthumela amaphutha elilodwa ngesikhathi, ngalinye lingase linqatshwe.
Ngangingafuni ukuthumela ama-typos angenangqondo, kodwa ngathatha iseluleko futhi ngathumela incwadi kuphela lapho ngithola iphutha lomlando elalibonakala libucayi ngokwanele.
U-Ashutosh Mehra ungumtshalizimali wesithathu ocebe kakhulu e-San Serriff onenani eliphelele elingu-0x$207.f0 ku-BoSS.
- Okuhlukahlukene:
Source: www.habr.com
