Donald Knuth ndi katswiri wa sayansi ya makompyuta amene amasamala kwambiri za kulondola kwa mabuku ake moti amanena hex dollar imodzi ($2,56, 0x$1,00) pa "cholakwika" chilichonse chomwe chapezeka, pomwe cholakwika chimatanthauzidwa ngati chilichonse "cholakwika mwaukadaulo, mbiri yakale, zolemba, kapena ndale." Ndinkafuna kwambiri kupeza cheke kuchokera kwa Knuth, kotero ndinaganiza zoyang'ana zolakwika mu magnum opus yake "Art of Programming" (TAOCP). Tinakwanitsa kupeza atatu. Monga momwe adanenera, Knut adatumiza cheke 0x $3,00.

Monga mukuonera, iyi si cheke chenicheni. Knuth ankatumiza macheke enieni, koma anasiya mu 2008 chifukwa chinyengo chofala. Tsopano akutumiza "zikalata zanu za depositi" kwa Bank of San Serriff (BOSS). Akuti ndi wokonzeka kutumiza ndalama zenizeni ngati kuli kofunikira, koma zikuwoneka ngati zovuta kwambiri.

Ndinapeza typos ziwiri ndi cholakwika chimodzi cha mbiriyakale. Ndidzawalemba m'ndondomeko yochepetsera zachabechabe.

Mtundu #1

Kulemba koyamba kuli patsamba 392 la voliyumu yachitatu ya "Kusanja ndi Kusaka", mzere wachisanu ndi chitatu kuchokera pansi: "Pambuyo posaka osachita bwino, nthawi zina (nthawi zina) ndikofunikira kuti mulowetse mbiri yatsopano patebulo lomwe muli. K; njira yomwe imachita izi imatchedwa kufufuza ndi kuyika algorithm. Cholakwika ndichoti m'malo mwake nthawi ina ziyenera kukhala nthawizina.

Ndithudi, kulakwa koteroko nkosadabwitsa. Payenera kukhala ma typos ochepa m'nkhaniyi yokha (palibe mphotho yowapeza). Chodabwitsa kwambiri ndichakuti sichinadziwike kwa nthawi yayitali. Tsamba 392 silinakwiridwe mozama mu gawo la masamu, ndi tsamba loyamba kwambiri Mutu 6 "Fufuzani"! Mwina ndi limodzi mwa magawo omwe amawerengedwa kwambiri m'bukuli. Mwachidziwitso, payenera kukhala typos ochepa kwambiri, koma ayi.

Mwa njira, ngati mudaganizapo zowerenga TAOCP, yesani. Ambiri anganene kuti ndi choncho directory, osati kuti awerenge mwachindunji, koma izi si zoona. Wolembayo ali ndi malingaliro omveka bwino komanso kalembedwe kosiyana. Chomwe chimalepheretsa kuwerenga ndizovuta za masamu. Komabe, pali yankho losavuta: werengani mpaka mutafika masamu omwe simukumvetsetsa, lumphani, ndikupita ku gawo lotsatira lomwe mungamvetse. Kuwerenga motere, ndikuphonya osachepera 80% ya bukuli, koma 20% ina ndiyabwino!

Amanenedwanso kuti TAOCP zosafunika, ndi zachikale kapena sizikugwira ntchito pa "mapulogalamu enieni". Izinso sizowona. Mwachitsanzo, gawo loyamba pambuyo pa mawu oyamba limayang'ana kupeza chinthu mumndandanda wosasankhidwa. Algorithm yosavuta kwambiri ndiyodziwika kwa onse opanga mapulogalamu. Yambitsani cholozera kumayambiriro kwa gululo, kenako chitani zotsatirazi mu lupu:

1. Onani ngati chinthu chapano ndicho chomwe mukufuna. Ngati ndi choncho, tikubweza; mwinamwake
2. Onani ngati cholozeracho chili kunja kwa malire a gulu. Ngati ndi choncho, bwezerani cholakwika; mwinamwake
3. Onerani pafupi ndikupitiliza.

Tsopano ganizirani: ndi malire angati omwe algorithm iyi imafunikira, pafupifupi? Zikafika poyipa kwambiri, pomwe gulu lilibe chinthu, chinthu chilichonse pamndandanda chimafuna cheke chimodzi, ndipo pafupifupi chizikhala chonga. . Katswiri wofufuza mwanzeru atha kukhala ndi cheke chimodzi chokha. Gwirizanitsani chinthu chomwe mukufuna kumapeto kwa gululo, kenako yambani cholozera kumayambiriro kwa gululo ndikuchita zotsatirazi mu lupu:

1. Onani ngati chinthu chapano ndicho chomwe mukufuna. Ngati ndi choncho, timabwezera yankho ngati cholozeracho chili mkati mwa gulu, kapena cholakwika ngati sichoncho. Apo ayi
2. Onerani pafupi ndikupitiliza.

Njira imodzi kapena imzake, chinthucho chimatsimikizika kuti chipezeka, ndipo kuwunika kwa malire kumachitika kamodzi kokha izi zikachitika. Ili ndi lingaliro lakuya, koma ndi losavuta mokwanira ngakhale kwa pulogalamu ya novice. Mwina sindingathe kuyankhula za kufunika kwa ntchitoyi kwa ena, koma nthawi yomweyo ndinatha kugwiritsa ntchito nzeruzi pazida zanga komanso zaukadaulo. Buku la TAOCP ladzaza ndi miyala yamtengo wapatali yotere (kunena chilungamo, mulinso zinthu zachilendo zambiri mmenemo, monga mtundu wa bubble).

"Fufuzani, fufuzani
Tidzaonana
Sakani, fufuzani
Ndimangofuna kuvina"
- Luther Vandross, "The Search" (1980)

Mtundu #2

Kutayira kwachiwiri kuli mu Volume 4A, Combinatorial Algorithms, Gawo 1. Tsamba 60 likufotokoza vuto lomwe likukhudza kukonza ochita sewero kuti aziimba m'makasino osiyanasiyana. Oseketsa angapo amoyo weniweni amatchulidwa ngati zitsanzo, kuphatikizapo Lily Tomlin, Weird Al Yankovic, ndi Robin Williams, yemwe anali adakali moyo pamene bukuli linasindikizidwa. Knuth nthawi zonse amalemba mayina athunthu muzolozera, kotero Williams amalembedwa patsamba 882 ngati "Williams, Robin McLorim." Koma dzina lake lapakati limatha ndi "n" osati "m", ndiye McLaurin.

McLaurin anali dzina lachibwana la amayi ake. Anali mdzukulu wa Anselm Joseph McLaurin, Bwanamkubwa wa 34 wa Mississippi. Ulamuliro wake, mwachiwonekere, sunakumbukiridwe pa chilichonse chabwino. Kuchokera m'buku "Mississippi: Mbiri":

“Chochitika chofunika kwambiri pa nthawi ya ulamuliro wa McLaurin chinali chilengezo cha nkhondo cha United States ku Spain m’chaka cha 1898... Mwatsoka, nkhondoyo mwina inapatsa akuluakulu ena a boma mpata wochita chiphuphu. McLaurin anaimbidwa mlandu wa machitidwe osiyanasiyana okayikitsa, kuphatikiza kukondera komanso kugwiritsa ntchito monyanyira mphamvu zokhululukira. M’kati mwa gulu la kudziletsa, otsutsawo anaimba mlandu bwanamkubwayo kukhala chidakwa, chimene anavomereza poyera.”

Kulakwitsa kwa mbiriyakale

Taganizirani chikhalidwe kuchulutsa aligorivimu kuchokera ku maphunziro a sukulu. Kodi pamafunika kuchulutsa kangati kamodzi? Tiyerekeze kuti mwachulukitsa - nambala ya nambala pa - pang'ono . Choyamba chulukitsani manambala oyamba pa digito iliyonse mmodzi ndi mmodzi. Kenako chulukitsa nambala yachiwiri pa digito iliyonse chimodzi ndi chimodzi mpaka mutadutsa manambala onse . Chifukwa chake kuchulukitsa kwachikhalidwe kumafunikira kuchulukitsa koyambirira. Makamaka, kuchulukitsa manambala awiri ndi maudindo ofunikira kuchulukitsa kwa manambala amodzi.

Izi ndizoipa, koma ndizotheka kukhathamiritsa ndondomekoyi pogwiritsa ntchito njira yopangidwa ndi katswiri wa masamu wa Soviet Anatoly Alekseevich Karatsuba. Tiyeni tiyesere zimenezo и  - manambala awiri a decimal; ndiko kuti, pali manambala , , , choncho и (kuwonjezera algorithm iyi ku manambala okulirapo kumafuna kusintha kwina; ngakhale sikovuta kwambiri, kuti ndisapange zolakwika mwatsatanetsatane, nditsatire chitsanzo chosavuta). Ndiye , , . Kuchulutsa ma binomials kumapereka . Pakali pano tikanatero kuchulukitsa kwa manambala amodzi: , , , . Tsopano tiyeni tiwonjezere ndi kuchotsa . Pambuyo rearrangements angapo, amene ine kusiya monga zolimbitsa thupi owerenga, likukhalira  - kuchulukitsa kwa manambala atatu okha! (Pali ma coefficients okhazikika, koma amatha kuwerengedwa powonjezera ndikusintha manambala).

Osafunsa umboni, koma Karatsuba algorithm (mobwerezabwereza kuchokera ku chitsanzo pamwambapa) imawongolera njira yochulukitsira yachikhalidwe ndi ntchito kale . Chonde dziwani kuti uku ndikuwongolera kwenikweni kwa ma aligorivimu, osati kukhathamiritsa kuwerengera kwamalingaliro. Zowonadi, ma aligorivimu si oyenera masamu amisala, chifukwa amafunikira ndalama zambiri zogwirira ntchito mobwerezabwereza. Kuphatikiza apo, zotsatira zake sizingadziwonetsere kwathunthu mpaka ziwerengero zitakula mokwanira (mwamwayi, algorithm ya Karatsuba yasinthidwa ndi njira zofulumira kwambiri: mu Marichi 2019, algorithm idasindikizidwa yomwe imafuna kokha. n logi n kuchulukitsa; kuthamangitsa kumangokhudza ziwerengero zazikulu kwambiri).

Izi zafotokozedwa patsamba 295 la Volume XNUMX, Semi-Numerical Algorithms. Kumeneko Knuth analemba kuti: “N’zochititsa chidwi kuti mfundo imeneyi inangopezeka m’bukuli 1962 chaka," pomwe nkhani yofotokoza algorithm ya Karatsuba idasindikizidwa. Koma! Mu 1995, Karatsuba adasindikiza pepala lonena za "Computational Complexity," yomwe ikunena zinthu zingapo: 1) Cha m'ma 1956, a Kolmogorov ananena kuti kuchulukitsa sikungachitike mochepera masitepe; 2) inu 1960 Chaka Karatsuba anapita ku semina kumene Kolmogorov anapereka maganizo ake n². 3) "Mu sabata imodzi ndendende," Karatsuba adapanga "gawani ndikugonjetsa" algorithm; 4) mu 1962, Kolmogorov analemba ndi kufalitsa nkhani m'malo mwa Karatsuba ndi kufotokozera kwa algorithm. “Nkhaniyi ndinaidziŵa pambuyo poisindikizanso.”

Choncho cholakwika ndi chakuti m'malo 1962 ziyenera kufotokozedwa 1960 chaka. Ndizomwezo.

Kufufuza

Kupeza zolakwika sikunafune luso lapadera.

1. Cholakwika choyamba chinali chaching'ono momwe ndingathere ndipo chinali pamalo owoneka bwino (chiyambi cha mutuwo). Chitsiru chilichonse akanachipeza; Ndinangopezeka kuti ndine chitsiru.
2. Kupeza typo yachiwiri kumafuna mwayi ndi khama, koma osati luso. Mndandanda wa "Williams" uli patsamba lomaliza la bukuli, gawo lodziwika bwino la bukhuli. Ndinkangoyang'ana mlozera (sikumvetsa chisoni monga momwe kumamvekera, chifukwa pali mazira a Isitala obisika m'ma index a Knuth. Mwachitsanzo, pali zolemba zachiarabu ndi Chihebri, zonse zomwe zikuloza patsamba 66. Koma tsambalo silikutchulapo. zilankhulo zilizonse; m'malo mwake amatanthauza "zilankhulo zomwe zimawerengedwa kuchokera kumanja kupita kumanzere"). Ndipo dzina lachiwiri linandigwira mtima. Popeza nthawi zambiri ndimawerenga Wikipedia, ndinayang'ana Robin Williams ndikuwona kusiyana.
3. Ndikulakalaka ndikanati ndachita kafukufuku wozama kuti ndipeze cholakwika chambiri, koma kwenikweni ndidangoyang'ana Tsamba la Wikipedia la algorithm ya Karatsuba. Mizere yoyamba imati: "Karatsuba algorithm ndi njira yochulutsa mwachangu. Anapezedwa ndi Anatoly Karatsuba mu 1960 ndipo adasindikizidwa mu 1962. Pambuyo pake chomwe chidatsala ndikuwonjezera ziwiri ndi ziwiri.

M'tsogolomu ndikufuna kupeza cholakwika kwambiri, makamaka mu code ya Knuth. Ndikufunanso kupeza cholakwika mu voliyumu yoyamba ya Fundamental Algorithms. Mwina ndikanazipeza, koma pazifukwa zina laibulale yakumaloko ili ndi mavoliyumu 2, 3 ndi 4A okha.

Mfundo zachuma:

• Ponseponse, chopereka changa ku TAOCP chili ndi zilembo zitatu zokha: kuwonjezera kumodzi s, m'malo m pa n и 2 pa 0. Pa $2,56, izi ndi zizindikiro zopindulitsa kwambiri; Ngati munalipidwa ndalama zotere, nkhani ya mawu 1000 (avareji ya zilembo zinayi) ingakupangitseni kukhala wamkulu khumi.
• Ndi madola atatu a hexadecimal, ine, pamodzi ndi nzika zina 29, tamangidwa pa malo a 69 pamndandanda wa olemera kwambiri a San Serriff Bank (kuyambira pa Meyi 1, 2019).

Zokambirana zina za macheke kuchokera ku Knuth

• Momwe mungapezere cheke kuchokera ku Knuth

  Malingaliro ambiri opeza zolakwika m'mabuku a Knuth. Nthawi zambiri amakhudza zolakwika zaukadaulo, zomwe ndilibe. Pali lingaliro limodzi pamenepo lomwe ndidalilabadira:

  Ndibwino kudikirira mpaka mutatolera zolakwika zingapo kuti mupereke. Mwa kuphatikiza zolakwika zingapo zenizeni koma zosafunikira kwenikweni, mumawonjezera mwayi woti chimodzi mwazo chitha kuwonedwa ngati cholakwika kapena upangiri. Ngati mutumiza zolakwika kamodzi kamodzi, aliyense payekha akhoza kukanidwa.

  Sindinafune kutumiza zolemba zopanda pake, koma ndidalandira upangiriwo ndikutumiza kalatayo pokhapokha nditapeza cholakwika chambiri chomwe chimawoneka chachikulu mokwanira.

• Macheke a Ashutosh Mehra

  Ashutosh Mehra ndiye Investor wachitatu wolemera kwambiri ku San Serriff wokhala ndi ndalama zokwana 0x$207.f0 ku BoSS.

• Yang'anani zolakwika zina zosagwira ntchito mu code yeniyeni ya TeX
• Zosiyana: #1 #2 #3 #4 #5 #6

Source: www.habr.com