Donald Knuth zanyarek kompîturê ye ku ew qas li ser rastbûna pirtûkên xwe yên ku ew pêşniyar dike girîng e yek dolar hex ($2,56, 0x$1,00) ji bo her "çewtî" ya ku hat dîtin, ku xeletî wekî tiştek "teknîkî, dîrokî, tîpografîk, an ji hêla siyasî ve nerast" tê pênase kirin. Min bi rastî dixwest ku ez ji Knuth kontrolek bistînim, ji ber vê yekê min biryar da ku li xeletiyan di xebata wî ya mezin de bigerim "Hûnera Bernamesaziyê" (TAOCP). Me karî sê kes bibînin. Li ser gotina xwe rast bû, Knut ji bo çekek şand 0x $3,00.

Wekî ku hûn dikarin bibînin, ev ne kontrolek rastîn e. Knuth berê kontrolên rastîn dişand, lê di sala 2008 de ji ber vê yekê rawestiya sextekarî berbelav. Ew naha "sertîfîkayên spartinê yên kesane" dişîne Banka San Serriff (Şef). Ew dibêje ku ew amade ye ku heke hewce bike drav rast bişîne, lê wusa dixuye ku ew pir tengasiyek e.

Min du xeletiyên tîp û yek xeletiya dîrokî dîtin. Ez ê wan bi rêza kêmbûna piçûkbûnê navnîş bikim.

Tîpa #1

Yekem xeletiya tîpê di rûpela 392 ya cilda sêyem a “Rêxistin û Lêgerîn” de, rêza heştan ji binî: “Piştî lêgerîneke neserkeftî, carinan (carinan) tê xwestin ku tomarek nû têxe tabloya ku tê de K; rêbaza ku vê dike jê re dibêjin algorîtmaya lêgerîn û têxê. Şaşî ew e ku li şûna carinan divê bibe carna.

Helbet xeletiyeke wiha ne sosret e. Di vê gotarê de tenê çend xeletiyên tîpan hene (ji bo dîtina wan xelat tune). Tiştê ku bi rastî ecêb e ev e ku ew qas dirêj ji nedîtî ve çû. Rûpel 392 di beşa matematîkê de ne kûr e, ew e rûpela yekem Beşa 6 "Lêgerîn"! Dibe ku yek ji beşên pirtûkê yên ku herî zêde têne xwendin. Di teoriyê de, divê herî kêm xeletiyên tîpan hebin, lê na.

Bi awayê, heke we carî li ser xwendina TAOCP-ê fikirî, wê biceribînin. Gelek dê bêjin ku ev e pirtûka referansê, ne ji bo xwendina rasterast, lê ev ne rast e. Nivîskar xwedî nêrîneke zelal û şêwazeke cihê ye. Tişta ku xwendinê asteng dike tevliheviya matematîkê ye. Lêbelê, çareseriyek hêsan heye: bixwînin heya ku hûn negihîjin matematîkê ku hûn fêm nakin, jê derbas bibin û biçin beşa din a ku hûn fêm dikin. Bi vî awayî dixwînim, ez bi kêmî ve 80% ji pirtûkê winda dikim, lê% 20-ê din pir xweş e!

Her weha tê gotin ku TAOCP bêqîmet, kevn e an wekî din ji bo "bernameya rastîn" nayê pêkanîn. Ev jî ne rast e. Mînakî, beşa yekem a piştî danasînê li dîtina hêmanek di nav rêzek nerêkûpêk de dinêre. Algorîtmaya herî hêsan ji hemî bernamenûsan re nas e. Nîşankerê li destpêka rêzê dest pê bikin, dûv re di hêlekê de jêrîn bikin:

1. Kontrol bikin ka hêmana heyî ya ku tê xwestin e. Eger wisa be, em wê vegerînin; wekî din
2. Kontrol bikin ka nîşander li derveyî sînorê array e. Ger wusa be, xeletiyek vegere; wekî din
3. Zêde bikin û berdewam bikin.

Naha bifikirin: ev algorîtma bi navînî çend kontrolên sînoran hewce dike? Di rewşa herî xirab de, li cihê ku array hêmanek nahewîne, her elementek di navnîşê de yek kontrolê hewce dike, û bi gelemperî ew ê tiştek mîna . Algorîtmayek lêgerînê ya jîrtir dikare bi tenê kontrolek sînoran ji holê rabe. Hêmana xwestinê bi dawiya rêzê ve girêbidin, dûv re nîşanderê li destpêka rêzê dest pê bikin û di çerçoveyek jêrîn de bikin:

1. Kontrol bikin ka hêmana heyî ya ku tê xwestin e. Ger wusa be, heke nîşanker di nav rêzê de be, em bersivek vedigerînin, an heke ne wusa be xeletiyek. Wekî din
2. Zêde bikin û berdewam bikin.

Bi vî awayî an yekî din, hêman garantî ye ku were dîtin, û dema ku ev çêbibe kontrolkirina sînoran tenê carekê tê kirin. Ev ramanek kûr e, lê ji bo bernamenûsek nûjen jî têra xwe hêsan e. Ez belkî nikarim ji yên din re têkildariya xebatê bipeyivim, lê min tavilê karî vê şehrezayiyê hem ji bo koda kesane û hem jî ya pîşeyî bicîh bikim. Pirtûka TAOCP bi gewherên weha tije ye (ji bo ku em rast bin, li wir gelek tiştên ecêb jî hene, wek mînak cureyê bubble).

"Lêgerîn, lêgerîn
Hevdem
Lêgerîn, lêgerîn
Min tenê dixwest ku dans bikim"
- Luther Vandross, "Lêgerîn" (1980)

Tîpa #2

Tîpa duyemîn di Volume 4A, Algorîtmayên Kombinatorîal, Beş 1 de ye. Rûpel 60 pirsgirêkek ku tê de komedyenên plansazkirî hene ku li gazînoyên cihêreng performansê dikin vedibêje. Çend komedyenên jiyana rast wekî mînak têne destnîşan kirin, di nav de Lily Tomlin, Weird Al Yankovic, û Robin Williams, ku hîna sax bû dema ku pirtûk hate weşandin. Knuth her gav navên tam di navnîşan de navnîş dike, ji ber vê yekê Williams di rûpela 882 de wekî "Williams, Robin McLorim" tête navnîş kirin. Lê navê wî yê navîn bi "n" diqede û ne "m", ango McLaurin.

McLaurin navê keça diya wî bû. Ew neviya Anselm Joseph McLaurin, Waliyê 34-ê Mississippi bû. Padîşahiya wî, xuya ye, ji bo tiştekî baş nehat bîra wî. Ji pirtûkê "Mississippi: Dîrok":

“Bûyera herî girîng a di dema rêveberiya McLaurin de, ragihandina şer a Dewletên Yekbûyî yên Amerîkayê li dijî Spanyayê di bihara 1898’an de bû... Mixabin, şer dibe ku derfetê bide hin rayedarên hikûmetê ku bi bertîlê re mijûl bibin. McLaurin bi kiryarên cihêreng ên gumanbar, di nav de nepotîzm û karanîna zêde ya hêzên bexşandinê, hate tawanbar kirin. Di dema tevgera nermbûnê de, rexnegiran walî bi serxweşiyê tawanbar kirin, ku wî bi eşkere qebûl kir.

Şaşiyeke dîrokî

Bifikirin algorîtmaya pirkirina kevneşopî ji mufredata dibistanê. Çend pirkirina yek-hejmarî hewce dike? Bifikirin ku hûn zêde dibin -hejmara reqemî li ser -gem . Pêşî jimareya yekem zêde bikin ji bo her hejmarê yek bi yek. Paşê reqema duyemîn zêde bikin ji bo her hejmarê yek bi yek û bi vî awayî heta ku hûn bi hemî hejmaran re derbas bibin . Ji ber vê yekê pirkirina kevneşopî hewce dike pirtengîyên primitive. Bi taybetî, du hejmaran bi zêdekirina rêzên pêwîst pirjimarên yekjimarî.

Ev xirab e, lê gengaz e ku meriv pêvajoyê bi karanîna rêbazek ku ji hêla matematîkzanê Sovyetê Anatoly Alekseevich Karatsuba ve hatî pêşve xistin xweştir bike. Werin em wisa bikin и  - hejmarên dehekî du-hejmar; yanî hejmar hene , , , wisa ku и (Gemperkirina vê algorîtmayê ji hejmarên mezintir re hin manîpulasyonê hewce dike; her çend ew ne pir dijwar e jî, ji bo ku di hûrguliyan de xeletî nebin, ez ê çêtir bimînim ser mînakek hêsan). Paşan , , . Pirkirina dubendan dide . Di vê demê de hîna me heye Pirkirina yekjimarî: , , , . Niha em lê zêde bikin û kêm bikin . Piştî çend vesazkirinan, ku ez ê wekî temrînek ji xwendevan re bihêlim, derdikeve holê  - tenê sê pirjimariyên yek-hejmar! (Hin hevserokên domdar hene, lê ew tenê bi zêdekirin û guheztina reqeman têne hesibandin).

Ji bo delîlan nexwazin, lê Algorîtmaya Karatsuba (ji mînaka li jor vegere giştî) li ser rêbaza pirkirina kevneşopî bi çêtir dike operasyonên berê . Ji kerema xwe not bikin ku ev çêtirbûnek rastîn a algorîtmê ye, ne xweşbîniyek ji bo hesabên derûnî. Bi rastî, algorîtma ji bo jimartinên derûnî ne maqûl e, ji ber ku ew ji bo operasyonên paşverû lêçûnên mezin hewce dike. Digel vê yekê, heya ku hejmar têra xwe mezin nebin, bandor dê bi tevahî xwe diyar neke (bi xweşbextane, algorîtmaya Karatsuba bi rêbazên hê zûtir hate guheztin: di Adar 2019 de, algorîtmayek hate weşandin ku tenê hewce dike n têketin n multiplications; lezkirin tenê ji bo hejmarên mezin ên ku nayê xeyal kirin derbas dibe).

Ev algorîtma li ser rûpela 295 ya cilda XNUMX, Algorîtmayên Nîv-Hejmarî tê şirove kirin. Li wir Knuth dinivîse: “Meraq e ku ev fikir tenê di nav de hat keşif kirin 1962 sal," dema ku gotarek ku algorîtmaya Karatsuba vedibêje hate weşandin. Lebê! Di sala 1995-an de, Karatsuba kaxezek li ser "Tevhevbûna Hesabkirinê" weşand, ku çend tişt dibêje: 1) Li dora sala 1956-an, Kolmogorov pêşniyar kir ku pirbûn di kêmtirî de nikare were kirin. gavên; 2) li 1960 sal Karatsuba beşdarî semînerê bû ku Kolmogorov hîpoteza xwe n² pêşkêş kir. 3) "Tam di hefteyekê de," Karatsuba algorîtmaya "parçe bike û bi ser bikeve" pêşxist; 4) di sala 1962 de, Kolmogorov gotarek nivîsand û weşand li ser navê Karatsuba bi ravekirina algorîtmayê. "Min tenê piştî ku ev gotar ji nû ve hate weşandin fêhm kir."

Ji ber vê yekê xeletî ew e ku li şûna 1962 divê bê diyarkirin 1960 sal. Navê pêger.

Analysis

Dîtina xeletiyan jêhatîbûnek taybetî hewce nedikir.

1. Çewtiya yekem bi qasî ku pêkan bû hindik bû û li cîhek berbiçav xuya bû (destpêka beşê). Her ehmeq wê ew bidîta; Ez tenê derketim ku ew ehmeq.
2. Ji bo dîtina tîpa duyemîn bextê şans û xîret lazim bû, lê ne jêhatîbûn. Indeksa "Williams" li ser rûpela paşîn a cildê ye, ku beşek berbiçav a pirtûkê ye. Min tenê li îndeksê digerand (ew ne ew qas xemgîn e ku dixuye, ji ber ku hêkên Paskalyayê di navnîşên Knuth de veşartî ne. Mînak, navnîşên bi erebî û îbranî hene, her du jî îşaret bi rûpela 66-ê dikin. Lê ew rûpel behsa wê nake. her du zimanan; li şûna wê ew "zimanên ku ji rastê ber bi çepê ve têne xwendin" vedibêje). Û navê duyemîn bala min kişand. Ji ber ku min bi gelemperî Wikipedia dixwend, min Robin Williams kontrol kir û cûdahiyek dît.
3. Xwezî ez dikarim bibêjim ku min lêkolînek cidî kir da ku xeletiyek dîrokî bibînim, lê bi rastî min tenê nihêrî Rûpela Wîkîpediya li ser algorîtmaya Karatsuba. Rêzên pêşîn dibêjin: "Algorîtmaya Karatsuba algorîtmayek pirjimara bilez e. Di sala 1960 de ji aliyê Anatoly Karatsuba ve hatiye dîtin û di sala 1962 de hatiye çapkirin." Piþtî wê tenê mabû ku du û du lê zêde bikin.

Di pêşerojê de ez dixwazim xeletiyek girîngtir bibînim, nemaze di koda Knuth de. Ez jî dixwazim di cilda yekem a Algorîtmayên Bingehîn de xeletiyek bibînim. Dibe ku min ew bidîta, lê ji ber hin sedeman pirtûkxaneya herêmî tenê cildên 2, 3 û 4A hene.

Rastiyên darayî:

• Bi tevahî, beşdariya min ji TAOCP re tenê ji sê karakteran pêk tê: yek pêvek s, cîgir m li ser n и 2 li ser 0. Bi 2,56 $, ev çend sembolên pir bikêr in; Ger we bi wî rengî pere hat dayîn, gotarek ji 1000 peyvan (bi navînî çar tîpan) dê deh gran ji we re qezenc bike.
• Bi sê dolarên hexadecimal, ez, tevî 29 hemwelatiyên din, di rêza 69emîn de li ser navnîşa depoyên herî dewlemend ên San Serriff Bank (ji 1ê Gulana 2019an) ve girêdayî ne.

Nîqaşên din ên li ser kontrolên ji Knuth

• Meriv çawa kontrolek ji Knuth bistîne

  Pêşniyarên gelemperî ji bo dîtina xeletiyên di pirtûkên Knuth de. Bi piranî ew xeletiyên teknîkî ne, yên ku min tune ne. Li wir pêşniyarek heye ku min ciddî girt:

  Çêtir e ku hûn li bendê bimînin heya ku hûn komek xeletî berhev bikin da ku radest bikin. Bi berhevkirina çend xeletiyên rastîn lê ne pir hêja, hûn îhtîmala ku yek ji wan bi rastî wekî xeletiyek an şîret were hesibandin zêde dike. Ger hûn xeletiyan yek bi yek bişînin, dibe ku her yek yek bi yek were red kirin.

  Min nexwest tenê tîpên bêwate bişînim, lê şîret girt û name şand tenê dema ku min xeletiyek dîrokî dît ku têra xwe giran xuya dikir.

• Çekên Aşutosh Mehra

  Ashutosh Mehra sêyemîn veberhênerê herî dewlemend ê San Serriff e ku bi nirxek netîce ya 0x207.f0 li BoSS ye.

• Di koda TeX ya rastîn de hin xeletiyên ne-fonksîyonel kontrol bikin
• Cûda: #1 #2 #3 #4 #5 #6

Source: www.habr.com