Donald Knuth masanin kimiyyar kwamfuta ne wanda ya damu sosai game da daidaiton littattafansa da ya ba da shawara dala hex daya ($2,56, 0x$1,00) ga duk wani "kuskure" da aka samu, inda aka bayyana kuskure a matsayin duk wani abu da yake "a zahiri, tarihi, rubutu, ko siyasa ba daidai ba." Ina matukar son samun cak daga Knuth, don haka sai na yanke shawarar neman kurakurai a cikin opus na magnum "The Art of Programming" (TAOCP). Mun yi nasarar gano guda uku. Gaskiya da maganarsa, Knut ya aika da cak 0 x $ 3,00.

Kamar yadda kuke gani, wannan ba gaskiya ba ne. Knuth ya kasance yana aika cak na gaske, amma ya tsaya a 2008 saboda m zamba. Yanzu ya aika da "takardar shaidar ajiya na sirri" zuwa Bank of San Serriff (BoSS). Ya ce a shirye yake ya aika da kudi na gaske idan ya cancanta, amma da alama abin ya yi yawa.

Na sami rubutu guda biyu da kuskuren tarihi daya. Zan lissafta su a cikin tsari na raguwar ƙaranci.

Nau'in #1

Buga na farko yana kan shafi na 392 na juzu'i na uku na "Sarfafawa da Bincike", layi na takwas daga ƙasa: "Bayan binciken da bai yi nasara ba, wani lokaci (wani lokaci) yana da kyau a shigar da sabon rikodin a cikin tebur mai dauke da shi. K; hanyar da ke yin haka ita ake kira search and saka algorithm. Kuskuren shine a maimakon haka wani lokaci yakamata ya kasance wani lokacin.

Tabbas, irin wannan kuskuren ba abin mamaki bane. Babu shakka za a sami 'yan buga rubutu a cikin wannan labarin kadai (babu ladan gano su). Wani abin mamaki shi ne yadda aka dade ba a san shi ba. Ba a binne mai zurfi a sashin lissafi ba, haka ne shafin farko Babi na XNUMX "Bincike"! Wataƙila ɗaya daga cikin sassan littafin da aka fi karantawa. A ka'idar, yakamata a sami mafi ƙarancin buga rubutu, amma a'a.

Af, idan kun taɓa tunanin karanta TAOCP, gwada shi. Mutane da yawa za su ce haka ne directory, ba a yi niyya don karantawa kai tsaye ba, amma wannan ba gaskiya ba ne. Marubucin yana da ma’ana bayyananne da salo na musamman. Abinda kawai ke hana karantawa shine rikitarwar lissafi. Duk da haka, akwai mafita mai sauƙi: karanta har sai kun zo lissafin ba ku fahimta ba, ku tsallake shi, kuma ku je sashe na gaba da za ku fahimta. Karatun wannan hanyar, Na rasa aƙalla 80% na littafin, amma sauran 20% yana da kyau!

An kuma ce TAOCP maras dacewa, ya tsufa ko in ba haka ba ba a zartar da "ainihin shirye-shirye". Wannan kuma ba gaskiya ba ne. Misali, sashe na farko bayan gabatarwar yana duba nemo wani abu a cikin tsararrun da ba a daidaita su ba. Algorithm mafi sauƙi ya san duk masu shirye-shirye. Fara mai nuni a farkon tsararrun, sa'an nan kuma yi haka a cikin madauki:

1. Bincika idan kashi na yanzu shine wanda ake so. Idan haka ne, mu mayar da shi; in ba haka ba
2. Bincika idan mai nunin yana wajen iyakar tsararru. Idan haka ne, mayar da kuskure; in ba haka ba
3. Zuƙowa kuma ci gaba.

Yanzu la'akari: adadin iyakoki nawa ne wannan algorithm ke buƙata, a matsakaita? A cikin mafi munin yanayi, inda tsararrun ba ta ƙunshi wani abu ba, kowane kashi a cikin jerin zai buƙaci rajistan guda ɗaya, kuma a matsakaita zai zama wani abu kamar haka. . Algorithm bincike mafi wayo zai iya fita tare da duba iyakoki guda ɗaya kawai. Haɗa abin da ake so zuwa ƙarshen tsararrun, sannan fara mai nuni a farkon tsararrun kuma yi haka cikin madauki:

1. Bincika idan kashi na yanzu shine wanda ake so. Idan haka ne, muna mayar da martani idan mai nuni yana cikin tsararru, ko kuskure idan ba haka ba. In ba haka ba
2. Zuƙowa kuma ci gaba.

Wata hanya ko wata, kashi yana da tabbacin samunsa, kuma ana yin binciken iyakoki sau ɗaya kawai lokacin da wannan ya faru. Wannan ra'ayi ne mai zurfi, amma yana da sauƙi isa ko da ga novice shirye-shirye. Wataƙila ba zan iya yin magana game da dacewar aikin ga wasu ba, amma nan da nan na sami damar yin amfani da wannan hikimar ga lambar sirri da ta sana'a. Littafin TAOCP yana cike da irin waɗannan duwatsu masu daraja (don yin adalci, akwai kuma abubuwa masu ban mamaki da yawa a ciki, kamar su. nau'in kumfa).

"Bincika, bincika
Sai anjima
Bincika, bincika
rawa kawai nake so"
- Luther Vandross, "Binciken" (1980)

Nau'in #2

Buga na biyu yana cikin Volume 4A, Combinatorial Algorithms, Sashe na 1. Shafi na 60 yana bayyana wata matsala da ta shafi tsara tsarin wasan barkwanci don yin wasan kwaikwayo a gidajen caca daban-daban. An ba da misali da wasu ƴan wasan barkwanci na zahiri, waɗanda suka haɗa da Lily Tomlin, Weird Al Yankovic, da Robin Williams, waɗanda har yanzu suna raye lokacin da aka buga littafin. Knuth koyaushe yana lissafta cikakkun sunaye a cikin ma'auni, don haka an jera Williams a shafi na 882 a matsayin "Williams, Robin McLorim." Amma sunansa na tsakiya ya ƙare da "n" ba "m", wato, McLaurin.

McLaurin shine sunan budurwar mahaifiyarsa. Ita ce babbar jikanyar Anselm Joseph McLaurin, Gwamna na 34 na Mississippi. Mulkinsa, a fili, ba a tuna da wani abu mai kyau ba. Daga littafi "Mississippi: Tarihi":

“Babban abin da ya fi muhimmanci a lokacin gwamnatin McLaurin shi ne shelanta yaki da Amurka ta yi kan Spain a cikin bazarar shekara ta 1898... Abin takaici, yakin na iya baiwa wasu jami’an gwamnati damar shiga cin hanci. An tuhumi McLaurin da ayyuka daban-daban da ake tambaya, da suka haɗa da son zuciya da yin amfani da ikon yin afuwa fiye da kima. A lokacin da ake yin tazarce, masu sukar sun zargi gwamnan da zama mashayi, wanda ya yarda da shi a bainar jama’a.”

Kuskuren tarihi

Ka yi la'akari al'ada multiplication algorithm daga tsarin karatun makaranta. Lambobin lambobi nawa nawa yake buƙata? A ce kun ninka -lambar lambobi a kan -bit . Da farko ninka lamba ta farko ga kowane lambobi daya bayan daya. Sannan ninka lambobi na biyu ga kowane lambobi daya bayan daya da sauransu har sai kun bi dukkan lambobi . Don haka yawaitar al'ada yana buƙatar m multiplications. Musamman, ninka lambobi biyu ta matsayi da ake bukata ninka lambobi guda ɗaya.

Wannan mummunan abu ne, amma yana yiwuwa a inganta tsarin ta amfani da hanyar da masanin lissafi na Soviet Anatoly Alekseevich Karatsuba ya tsara. Bari mu yi kamar haka и  - lambobi masu lamba biyu; wato akwai lambobi , , , irin haka и (gabaɗaya wannan algorithm zuwa lambobi masu girma yana buƙatar wasu magudi; ko da yake ba shi da wahala sosai, don kada ku yi kuskure a cikin cikakkun bayanai, zan fi dacewa da misali mai sauƙi). Sannan , , . Maɓallin binomial yana ba da . A halin yanzu har yanzu muna da ninka lambobi ɗaya: , , , . Yanzu bari mu ƙara mu rage . Bayan wasu gyare-gyare, wanda zan bari a matsayin motsa jiki ga mai karatu, ya zama  - ninka lambobi guda uku kawai! (Akwai wasu ƙididdiga akai-akai, amma ana iya ƙididdige su ta ƙara da canza lambobi).

Kar ku nemi hujja, amma Karatsuba algorithm (wanda aka maimaita akai-akai daga misalin da ke sama) yana haɓakawa akan hanyar yawaitar gargajiya tare da ayyuka kafin . Da fatan za a lura cewa wannan haɓakawa ne na gaske ga algorithm, ba haɓakawa don ƙididdige tunani ba. Lallai, algorithm ɗin bai dace da ƙididdiga na tunani ba, tunda yana buƙatar babban farashi mai ƙima don ayyukan maimaitawa. Bugu da ƙari, tasirin ba zai bayyana kansa sosai ba har sai lambobin sun yi girma sosai (sa'a, an maye gurbin algorithm na Karatsuba ta hanyoyi masu sauri: a cikin Maris 2019, an buga algorithm wanda ke buƙatar kawai. n log n yawaita; hanzari ya shafi manyan lambobi ne kawai waɗanda ba za a iya tunaninsu ba).

An kwatanta wannan algorithm a shafi na 295 na Juzu'i na XNUMX, Algorithms Semi-Lambobi. A can Knuth ya rubuta: “Yana da sha’awar cewa an gano wannan ra’ayin ne kawai a ciki 1962 shekara," lokacin da aka buga labarin da ke kwatanta algorithm na Karatsuba. Amma! A cikin 1995, Karatsuba ya buga wata takarda "Computational Complexity", wanda ya ce abubuwa da yawa: 1) a kusa da 1956, Kolmogorov ya ba da shawarar cewa ba za a iya yin ninkawa cikin ƙasa da ƙasa ba. matakai; 2) in 1960 shekara Karatsuba ya halarci taron karawa juna sani inda Kolmogorov ya gabatar da hasashe n². 3) "A daidai mako guda," Karatsuba ya haɓaka algorithm "raba da nasara"; 4) a 1962 Kolmogorov ya rubuta da kuma buga wani labarin a madadin Karatsuba tare da bayanin algorithm. "Na sami labarin wannan labarin ne kawai bayan an sake buga shi."

Don haka kuskuren shine maimakon haka 1962 dole ne a kayyade 1960 shekara. Shi ke nan.

Анализ

Gano kurakurai baya buƙatar fasaha ta musamman.

1. Kuskure na farko ba shi da yawa kamar yadda zai yiwu kuma ya kasance a wurin da ake iya gani sosai (farkon babin). Duk wawa da ya same shi; Na zama wawan nan.
2. Nemo bugun rubutu na biyu yana buƙatar sa'a da himma, amma ba fasaha ba. Fihirisar “Williams” tana kan babban shafi na ƙarar, wani fitaccen ɓangaren littafin. Sai kawai nake jujjuyawa cikin index (ba abin tausayi bane kamar yadda ake sauti, domin akwai ƙwai na Easter da ke ɓoye a cikin ma'anar Knuth. Misali, akwai abubuwan da aka shigar a cikin Larabci da Ibrananci, duka suna nuni zuwa shafi na 66. Amma wannan shafin bai faɗi ba. ko dai harsuna; maimakon haka yana nufin “harsunan da ake karantawa daga dama zuwa hagu”). Kuma suna na biyu ya dauki hankalina. Tun da na saba karanta Wikipedia, na duba Robin Williams kuma na lura da rashin daidaituwa.
3. Da ma in ce na yi bincike mai zurfi don gano kuskuren tarihi, amma da gaske na duba Shafin Wikipedia game da algorithm na Karatsuba. Layukan farko sun ce: “Algorithm na Karatsuba algorithm ne mai saurin ninkawa. An gano ta Anatoly Karatsuba a cikin 1960 kuma aka buga a 1962." Bayan haka abin da ya rage shi ne a kara biyu da biyu.

A nan gaba zan so in sami wani muhimmin kwaro, musamman a lambar Knuth. Ina kuma so in sami kwaro a cikin juzu'in farko na Algorithms na Asali. Wataƙila da zan same shi, amma saboda wasu dalilai ɗakin karatu na gida yana da kundin 2, 3 da 4A kawai.

Bayanan kudi:

• Gabaɗaya, gudunmawata ga TAOCP ta ƙunshi haruffa uku kawai: ƙari ɗaya s, sauyawa m a kan n и 2 a kan 0. A $2,56, waɗannan wasu kyawawan alamomi ne masu fa'ida; Idan an biya ku irin wannan kuɗin, labarin kalmomi 1000 (matsakaicin haruffa huɗu) zai sami babban girma goma.
• Tare da dala hexadecimal uku, Ni, tare da wasu ƴan ƙasa 29, an ɗaure ni don matsayi na 69 a cikin jerin masu ajiya mafi arziƙi na Bankin San Serriff (har daga ranar 1 ga Mayu, 2019).

Sauran tattaunawa game da cak daga Knuth

• Yadda ake samun cak daga Knuth

  Gabaɗaya shawarwari don gano kurakurai a cikin littattafan Knuth. Mafi yawa sun shafi kurakuran fasaha, waɗanda ba ni da su. Akwai wata shawara a can da na ɗauka da muhimmanci:

  Zai fi kyau a jira har sai kun tattara jerin kurakurai don ƙaddamarwa. Ta hanyar haɗa kurakurai da yawa na gaske amma ba masu kima ba, za ku ƙara yuwuwar cewa ɗaya daga cikinsu za a ɗauke shi a matsayin kuskure ko shawara. Idan kun gabatar da kurakurai ɗaya bayan ɗaya, kowane ɗayan ɗayan yana iya ƙi.

  Ba na so in aika rubutaccen rubutu na banza ba, amma na ɗauki shawara na aika wasiƙar kawai lokacin da na sami kuskuren tarihi wanda ya yi kama da tsanani.

• Ashutosh Mehra's cak

  Ashutosh Mehra shine mai saka hannun jari na uku mafi arziƙi a San Serriff tare da ƙimar darajar 0x$207.f0 a cikin BoSS.

• Bincika wasu kurakurai marasa aiki a cikin lambar TeX na gaske
• Daban: #1 #2 #3 #4 #5 #6

source: www.habr.com