Donalds Knuts ir datorzinÄtnieks, kuram tik ļoti rÅ«p savu grÄmatu precizitÄte, ko viÅÅ” iesaka viens hex dolÄrs (2,56 ASV dolÄri, 0 x 1,00 ASV dolÄri) par jebkuru atrasto "kļūdu", kur kļūda tiek definÄta kÄ jebkas, kas ir "tehniski, vÄsturiski, tipogrÄfiski vai politiski nepareizs". Es ļoti gribÄju saÅemt Äeku no Knuta, tÄpÄc nolÄmu meklÄt kļūdas viÅa magnum opusÄ "ProgrammÄÅ”anas mÄksla" (TAOCP). Mums izdevÄs atrast trÄ«s. Uzticoties savam vÄrdam, Knuts nosÅ«tÄ«ja Äeku par 0x3,00 ASV dolÄri.
KÄ redzat, Ŕī nav Ä«sta pÄrbaude. Knuts agrÄk sÅ«tÄ«ja Ä«stus Äekus, taÄu 2008. gadÄ pÄrtrauca . Tagad viÅÅ” izsÅ«ta "personÄ«gos noguldÄ«jumu sertifikÄtus". (BoSS). ViÅÅ” saka, ka ir gatavs sÅ«tÄ«t reÄlu naudu, ja nepiecieÅ”ams, taÄu Ŕķiet, ka tas ir pÄrÄk daudz problÄmu.
Atradu divas drukas kļūdas un vienu vÄsturisku kļūdu. Es tos uzskaitÄ«Å”u trivialitÄtes samazinÄÅ”anas secÄ«bÄ.
Drukas kļūda #1
PirmÄ drukas kļūda ir treÅ”Ä sÄjuma āÅ Ä·iroÅ”ana un meklÄÅ”anaā 392. lappusÄ, astotajÄ rindiÅÄ no apakÅ”as: āPÄc neveiksmÄ«gas meklÄÅ”anas reizÄm (reizÄm) vÄlams tabulÄ ievadÄ«t jaunu ierakstu, kurÄ ir K; metodi, kas to dara, sauc par meklÄÅ”anas un ievietoÅ”anas algoritmu. Kļūda ir tÄ, ka tÄ vietÄ kÄdreiz vajadzÄtu bÅ«t dažreiz.
Protams, Å”Äda kļūda nav pÄrsteidzoÅ”a. Å ajÄ rakstÄ vien noteikti ir dažas drukas kļūdas (bez atlÄ«dzÄ«bas par to atraÅ”anu). PatieÅ”Äm pÄrsteidzoÅ”i ir tas, ka tas tik ilgi palika nepamanÄ«ts. 392. lapa nav dziļi aprakta matemÄtikas sadaļÄ, tÄ ir pati pirmÄ lapa 6.nodaļa "MeklÄt"! IespÄjams, viena no visvairÄk lasÄ«tajÄm grÄmatas sadaļÄm. TeorÄtiski drukas kļūdu vajadzÄtu bÅ«t vismazÄk, bet nÄ.
Starp citu, ja esat kÄdreiz domÄjis par TAOCP lasÄ«Å”anu, izmÄÄ£iniet to. Daudzi teiks, ka tÄ ir katalogs, nav paredzÄts tieÅ”ai lasÄ«Å”anai, taÄu tÄ nav taisnÄ«ba. Autoram ir skaidrs skatÄ«jums un savdabÄ«gs stils. VienÄ«gais, kas traucÄ lasÄmÄ«bai, ir matemÄtikas sarežģītÄ«ba. TomÄr ir vienkÄrÅ”s risinÄjums: lasiet, lÄ«dz nonÄkat pie matemÄtikas, ko nesaprotat, izlaidiet to un pÄrejiet uz nÄkamo sadaļu, kuru varat saprast. TÄ lasot, man pietrÅ«kst vismaz 80% grÄmatas, bet pÄrÄjie 20% ir lieliski!
Ir arÄ« teikts, ka TAOCP nav nozÄ«mes, ir novecojis vai citÄdi nav piemÄrojams "Ä«stai programmÄÅ”anai". TÄ arÄ« nav taisnÄ«ba. PiemÄram, pirmajÄ sadaÄ¼Ä pÄc ievada aplÅ«kota elementa atraÅ”ana neŔķirotÄ masÄ«vÄ. VienkÄrÅ”Äkais algoritms ir pazÄ«stams visiem programmÄtÄjiem. SÄciet rÄdÄ«tÄju masÄ«va sÄkumÄ, pÄc tam veiciet tÄlÄk norÄdÄ«tÄs darbÄ«bas.
- PÄrbaudiet, vai paÅ”reizÄjais elements ir vÄlamais. Ja tÄ, mÄs to atgriežam; citÄdi
- PÄrbaudiet, vai rÄdÄ«tÄjs atrodas Ärpus masÄ«va robežas. Ja tÄ, atgrieziet kļūdu; citÄdi
- Tuviniet un turpiniet.
Tagad apsveriet: cik robežpÄrbaudes vidÄji prasa Å”is algoritms? SliktÄkajÄ gadÄ«jumÄ, ja masÄ«vÄ nav elementa, katram saraksta elementam bÅ«s nepiecieÅ”ama viena pÄrbaude, un vidÄji tas bÅ«s kaut kas lÄ«dzÄ«gs . GudrÄks meklÄÅ”anas algoritms varÄtu izvairÄ«ties tikai ar vienu robežu pÄrbaudi. Pievienojiet vajadzÄ«go elementu masÄ«va beigÄm, pÄc tam sÄciet rÄdÄ«tÄju masÄ«va sÄkumÄ un veiciet tÄlÄk norÄdÄ«tÄs darbÄ«bas.
- PÄrbaudiet, vai paÅ”reizÄjais elements ir vÄlamais. Ja tÄ, mÄs atgriežam atbildi, ja rÄdÄ«tÄjs atrodas masÄ«vÄ, vai kļūdu, ja tÄ nav. CitÄdi
- Tuviniet un turpiniet.
TÄ vai citÄdi elements tiek atrasts, un robežu pÄrbaude tiek veikta tikai vienu reizi, kad tas notiek. Å Ä« ir dziļa ideja, taÄu tÄ ir pietiekami vienkÄrÅ”a pat iesÄcÄjam programmÄtÄjam. Laikam nevaru runÄt par darba atbilstÄ«bu citiem, taÄu Å”o gudrÄ«bu uzreiz varÄju pielietot gan personÄ«gajÄ, gan profesionÄlajÄ kodeksÄ. TAOCP grÄmata ir pilna ar Å”Ädiem dÄrgakmeÅiem (taisnÄ«bas labad jÄsaka, ka tur ir arÄ« daudz dÄ«vainu lietu, piemÄram, ).
"MeklÄt, meklÄt
Tik ilgi
MeklÄ, meklÄ
Es tikai gribÄju dejot"
ā Luters Vandross, "MeklÄÅ”ana" (1980)
Drukas kļūda #2
OtrÄ drukas kļūda ir 4.A sÄjumÄ, KombinatoriÄlie algoritmi, 1. daļa. 60. lappusÄ ir aprakstÄ«ta problÄma, kas saistÄ«ta ar komiÄ·u uzstÄÅ”anÄs plÄnoÅ”anu dažÄdos kazino. KÄ piemÄri tiek minÄti vairÄki reÄlÄs dzÄ«ves komiÄ·i, tostarp Lilija Tomlina, DÄ«vainais Als JankoviÄs un Robins Viljamss, kurÅ” grÄmatas iznÄkÅ”anas brÄ«dÄ« vÄl bija dzÄ«vs. Knuts indeksÄ vienmÄr norÄda pilnus vÄrdus, tÄpÄc Viljamss 882. lappusÄ ir norÄdÄ«ts kÄ "Viljamss, Robins Maklorims". Bet viÅa otrais vÄrds beidzas ar ānā, nevis ar āmā, tas ir, McLaurin.
McLaurin bija viÅa mÄtes pirmslaulÄ«bas uzvÄrds. ViÅa bija Misisipi 34. gubernatora Anselma Džozefa Maklarina mazmazmeita. ViÅa valdÄ«Å”anas laiks, acÄ«mredzot, netika atcerÄts ar neko labu. No grÄmatas :
āSvarÄ«gÄkais notikums Maklarina administrÄcijas laikÄ bija Amerikas Savienoto Valstu kara pieteikÅ”ana SpÄnijai 1898. gada pavasarÄ«... DiemžÄl karÅ”, iespÄjams, deva dažÄm valdÄ«bas amatpersonÄm iespÄju iesaistÄ«ties kukuļoÅ”anÄ. Maklorins tika apsÅ«dzÄts dažÄdÄs apÅ”aubÄmÄs praksÄs, tostarp nepotismÄ un pÄrmÄrÄ«gÄ apžÄloÅ”anas pilnvaru izmantoÅ”anÄ. AtturÄ«bas kustÄ«bas laikÄ kritiÄ·i apsÅ«dzÄja gubernatoru par dzÄrÄju, ko viÅÅ” publiski atzina.
VÄsturiska kļūda
ApsvÄrt tradicionÄlais reizinÄÅ”anas algoritms no skolas mÄcÄ«bu programmas. Cik viencipara reizinÄjumus tas prasa? PieÅemsim, ka jÅ«s reizinat -ciparu skaitlis par - mazliet . Vispirms reiziniet pirmo ciparu katram ciparam vienu pÄc otra. PÄc tam reiziniet otro ciparu katram ciparam pa vienam un tÄ tÄlÄk, lÄ«dz iziet cauri visiem numuriem . TÄdÄjÄdi ir nepiecieÅ”ama tradicionÄlÄ reizinÄÅ”ana primitÄ«vie reizinÄjumi. Jo Ä«paÅ”i, reizinot divus skaitļus ar vajadzÄ«gas pakÄpes viencipara reizinÄjumus.
Tas ir slikti, taÄu procesu ir iespÄjams optimizÄt, izmantojot padomju matemÄtiÄ·a Anatolija AleksejeviÄa Karatsubas izstrÄdÄto metodi. Izliksimies tÄ Šø - divciparu decimÄlskaitļi; tas ir, ir skaitļi , , , tÄds, ka Šø (vispÄrinot Å”o algoritmu uz lielÄkiem skaitļiem, ir vajadzÄ«gas dažas manipulÄcijas; lai gan tas nav pÄrÄk grÅ«ti, lai nekļūdÄ«tos detaļÄs, labÄk palikÅ”u pie vienkÄrÅ”a piemÄra). Tad , , . BinomiÄlu reizinot iegÅ«st . Å obrÄ«d mums vÄl ir viencipara reizinÄÅ”ana: , , , . Tagad saskaitÄ«sim un atÅemsim . PÄc dažÄm pÄrkÄrtoÅ”anÄm, kuras atstÄÅ”u lasÄ«tÄjam kÄ vingrinÄjumu, izrÄdÄs - tikai trÄ«s viencipara reizinÄjumi! (Ir daži nemainÄ«gi koeficienti, bet tos var aprÄÄ·inÄt, tikai saskaitot un pÄrbÄ«dot ciparus).
Neprasi pierÄdÄ«jumus, bet Karatsuba algoritms (rekursÄ«vi vispÄrinÄts no iepriekÅ” minÄtÄ piemÄra) uzlabo tradicionÄlo reizinÄÅ”anas metodi ar operÄcijas iepriekÅ” . LÅ«dzu, Åemiet vÄrÄ, ka tas ir reÄls algoritma uzlabojums, nevis optimizÄcija prÄta aprÄÄ·iniem. PatieÅ”Äm, algoritms nav piemÄrots prÄta aritmÄtikai, jo tas prasa lielas pieskaitÄmÄs izmaksas rekursÄ«vÄm darbÄ«bÄm. TurklÄt efekts pilnÄ«bÄ neizpaudÄ«sies, kamÄr skaitļi kļūs pietiekami lieli (par laimi, Karatsubas algoritms ir aizstÄts ar vÄl ÄtrÄkÄm metodÄm: 2019. gada martÄ tika publicÄts algoritms, kas prasa tikai reizinÄjumi; paÄtrinÄjums attiecas tikai uz neiedomÄjami lieliem skaitļiem).
Å is algoritms ir aprakstÄ«ts 295. sÄjuma DaļÄji skaitļu algoritmi XNUMX. lpp. Tur Knuts raksta: āZiÅkÄrÄ«gi, ka Ŕī ideja tika atklÄta tikai gadÄ 1962 gadÄā, kad tika publicÄts raksts, kurÄ aprakstÄ«ts Karatsubas algoritms. Bet! 1995. gadÄ Karatsuba publicÄja rakstu par āComputational Complexityā, kurÄ teikts vairÄkas lietas: 1) Ap 1956. gadu Kolmogorovs ierosinÄja, ka reizinÄÅ”anu nevar veikt Ä«sÄkÄ laikÄ pakÄpieni; 2) iekÅ”Ä 1960 gadÄ Karatsuba apmeklÄja seminÄru, kurÄ Kolmogorovs prezentÄja savu hipotÄzi nĀ². 3) āTieÅ”i vienas nedÄļas laikÄā Karatsuba izstrÄdÄja āskaldi un valdiā algoritmu; 4) 1962. gadÄ Kolmogorovs uzrakstÄ«ja un publicÄja rakstu Karatsuba vÄrdÄ ar algoritma aprakstu. "Es uzzinÄju par Å”o rakstu tikai pÄc tÄ pÄrpublicÄÅ”anas."
TÄtad kļūda ir tÄ, ka tÄ vietÄ 1962 jÄprecizÄ 1960 gadÄ. Tas ir viss.
Analīze
Kļūdu atraŔana neprasīja īpaŔas prasmes.
- PirmÄ kļūda bija maksimÄli triviÄla un atradÄs samÄrÄ labi redzamÄ vietÄ (nodaļas sÄkums). JebkurÅ” idiots to bÅ«tu atradis; Es vienkÄrÅ”i izrÄdÄ«jos tas idiots.
- OtrÄs drukas kļūdas atraÅ”ana prasÄ«ja veiksmi un centÄ«bu, bet ne prasmes. "Viljamsa" rÄdÄ«tÄjs ir sÄjuma priekÅ”pÄdÄjÄ lappusÄ, kas ir diezgan ievÄrojama grÄmatas daļa. Es tikko Ŕķiroju indeksu (tas nav tik nožÄlojami, kÄ izklausÄs, jo Knuta rÄdÄ«tÄjos ir paslÄptas Lieldienu olas. PiemÄram, ir ieraksti arÄbu un ebreju valodÄ, abi norÄda uz 66. lpp. Bet tajÄ lapÄ nav minÄts vai nu valodÄs; tÄ vietÄ tas attiecas uz āvalodÄm, kuras lasa no labÄs uz kreiso pusiā). Un otrais vÄrds piesaistÄ«ja manu uzmanÄ«bu. TÄ kÄ es parasti lasu VikipÄdiju, es pÄrbaudÄ«ju Robinu Viljamsu un pamanÄ«ju neatbilstÄ«bu.
- Es vÄlos, lai varÄtu teikt, ka veicu nopietnu izpÄti, lai atrastu vÄsturisku kļūdu, bet patiesÄ«bÄ es tikai paskatÄ«jos . PaÅ”Äs pirmajÄs rindÄs teikts: āKaratsuba algoritms ir Ätrs reizinÄÅ”anas algoritms. 1960. gadÄ atklÄja Anatolijs Karatsuba un publicÄja 1962. gadÄ. PÄc tam atlika tikai pievienot divus un divus.
NÄkotnÄ es vÄlÄtos atrast kÄdu bÅ«tiskÄku kļūdu, Ä«paÅ”i Knutha kodÄ. Es arÄ« vÄlÄtos atrast kļūdu pirmajÄ Fundamental Algorithms sÄjumÄ. VarbÅ«t es bÅ«tu atradis, bet nez kÄpÄc vietÄjÄ bibliotÄkÄ ir tikai 2., 3. un 4A sÄjums.
FinanŔu fakti:
- KopumÄ mans ieguldÄ«jums TAOCP sastÄv tikai no trim rakstzÄ«mÄm: viens papildinÄjums s, nomaiÅa m par n Šø 2 par 0. Par USD 2,56 Å”ie ir daži diezgan ienesÄ«gi simboli; Ja jums maksÄtu Å”Ädu naudu, par 1000 vÄrdu rakstu (vidÄji Äetras rakstzÄ«mes) jÅ«s nopelnÄ«tu desmit grantus.
- Ar trim heksadecimÄlajiem dolÄriem es kopÄ ar 29 citiem pilsoÅiem ieÅemu 69. vietu San Serriff Bank bagÄtÄko noguldÄ«tÄju sarakstÄ (no 1. gada 2019. maija).
Citas diskusijas par Äekiem no Knuta
-
VispÄrÄ«gi ieteikumi kļūdu atraÅ”anai Knuta grÄmatÄs. PÄrsvarÄ tie attiecas uz tehniskÄm kļūdÄm, kuru man nav. Tur ir viens ieteikums, ko es uztvÄru nopietni:
VislabÄk ir pagaidÄ«t, lÄ«dz esat apkopojis kļūdu kopu, lai iesniegtu. Apvienojot vairÄkas reÄlas, bet ne pÄrÄk vÄrtÄ«gas kļūdas, jÅ«s palielinÄsiet iespÄjamÄ«bu, ka viena no tÄm patieÅ”Äm tiks uzskatÄ«ta par kļūdu vai padomu. Ja kļūdas iesniedzat pa vienai, katra no tÄm var tikt noraidÄ«ta atseviŔķi.
Es negribÄju sÅ«tÄ«t tikai muļķīgas drukas kļūdas, bet ÅÄmu vÄrÄ padomu un nosÅ«tÄ«ju vÄstuli tikai tad, kad atradu vÄsturisku kļūdu, kas Ŕķita pietiekami nopietna.
-
Ashutosh Mehra ir treÅ”ais bagÄtÄkais investors SanserifÄ, kura neto vÄrtÄ«ba BoSS ir 0x207,f0.
- DažÄdi:
Avots: www.habr.com