Donald Knut yog ib tug kws tshawb fawb hauv computer uas mob siab heev txog qhov tseeb ntawm nws cov phau ntawv uas nws qhia ib hex dollar ($ 2,56, 0x $ 1,00) rau ib qho "yuam kev" pom, qhov twg qhov kev ua yuam kev raug txhais tias yog txhua yam uas yog "technically, keeb kwm, typgraphically, los yog nom tswv tsis raug." Kuv yeej xav tau ib daim tshev los ntawm Knuth, yog li kuv txiav txim siab mus nrhiav qhov yuam kev hauv nws qhov magnum opus "Lub Art ntawm Programming" (TAOCP). Peb tswj kom nrhiav tau peb. Muaj tseeb rau nws cov lus, Knut xa daim tshev rau 0 x 3,00.
Raws li koj tau pom, qhov no tsis yog ib qho kev kuaj tiag tiag. Knuth siv xa cov tshev tiag, tab sis nres hauv 2008 vim . Tam sim no nws xa tawm "tus kheej daim ntawv pov thawj ntawm kev tso nyiaj" mus rau (BoSS). Nws hais tias nws txaus siab xa nyiaj tiag tiag yog tias tsim nyog, tab sis nws zoo li nws nyuaj heev.
Kuv pom ob qhov typos thiab ib qho yuam kev keeb kwm. Kuv yuav teev lawv nyob rau hauv kev txiav txim ntawm kev txo qis trivial.
Typo #1
Thawj typo yog nyob rau nplooj 392 ntawm qhov thib peb ntim ntawm "Sorting and Search", thib yim kab los ntawm hauv qab: "Tom qab kev tshawb nrhiav tsis tiav, qee zaum (qee zaum) nws yog ntshaw kom nkag mus rau cov ntaub ntawv tshiab rau hauv lub rooj uas muaj K; txoj kev uas ua qhov no yog hu ua kev tshawb nrhiav thiab ntxig algorithm. Qhov yuam kev yog qhov hloov qee zaum yuav tsum tej zaum.
Tau kawg, qhov yuam kev no tsis yog qhov xav tsis thoob. Muaj ob peb typos hauv tsab xov xwm no ib leeg (tsis muaj khoom plig rau kev nrhiav lawv). Dab tsi yog qhov xav tsis thoob yog tias nws mus tsis tau pom dua rau ntev. Page 392 tsis yog faus tob rau hauv seem lej, nws yog thawj nplooj ntawv Tshooj 6 "Nrhiav"! Tej zaum yog ib feem ntawm cov ntawv nyeem ntau tshaj plaws. Hauv txoj kev xav, yuav tsum muaj qhov tsawg tshaj plaws typos, tab sis tsis yog.
Los ntawm txoj kev, yog tias koj tau xav txog kev nyeem TAOCP, sim ua nws. Ntau tus yuav hais tias qhov no yog phau ntawv, tsis yog npaj rau kev nyeem ncaj qha, tab sis qhov no tsis muaj tseeb. Tus sau muaj qhov pom tseeb ntawm qhov pom thiab qhov txawv txav. Tib yam uas cuam tshuam kev nyeem ntawv yog qhov nyuaj ntawm lej. Txawm li cas los xij, muaj ib txoj hauv kev yooj yim: nyeem kom txog thaum koj tuaj rau lej koj tsis nkag siab, hla nws, thiab mus rau ntu tom ntej koj tuaj yeem nkag siab. Nyeem li no, kuv nco tsawg kawg yog 80% ntawm phau ntawv, tab sis lwm 20% yog qhov zoo!
Nws tseem hais tias TAOCP tsis cuam tshuam, yog outdated los yog lwm yam tsis muaj feem xyuam rau "tiag tiag programming". Qhov no kuj tsis muaj tseeb. Piv txwv li, thawj ntu tom qab qhov kev taw qhia saib ntawm kev nrhiav ib qho hauv ib qho array tsis txheeb. Qhov yooj yim tshaj plaws algorithm yog paub rau txhua tus programmers. Pib lub pointer thaum pib ntawm lub array, tom qab ntawd ua cov hauv qab no hauv lub voj voog:
- Xyuas seb lub caij tam sim no yog qhov xav tau. Yog tias muaj, peb xa rov qab; txwv tsis pub
- Xyuas seb tus pointer nyob sab nraud ntawm array ciam teb. Yog tias muaj, rov qab qhov yuam kev; txwv tsis pub
- Zoom hauv thiab txuas ntxiv.
Tam sim no xav txog: pes tsawg daim ntawv txheeb xyuas qhov no algorithm xav tau, qhov nruab nrab? Qhov phem tshaj plaws, qhov twg cov array tsis muaj cov khoom, txhua lub ntsiab lus hauv daim ntawv yuav xav tau ib daim tshev, thiab qhov nruab nrab nws yuav yog ib yam dab tsi zoo li. . Ib qho kev tshawb nrhiav algorithm ntse dua tuaj yeem tawm mus nrog tsuas yog ib qho kev kuaj xyuas. Txuas cov khoom xav tau mus rau qhov kawg ntawm array, tom qab ntawd pib lub pointer ntawm qhov pib ntawm array thiab ua cov hauv qab no hauv lub voj voog:
- Xyuas seb lub caij tam sim no yog qhov xav tau. Yog tias muaj, peb rov qab teb yog tias tus pointer nyob hauv cov array, lossis qhov yuam kev yog tias nws tsis yog. Lwm yam
- Zoom hauv thiab txuas ntxiv.
Ib txoj hauv kev los yog lwm qhov, lub ntsiab lus tau lees tias yuav pom, thiab kev kuaj xyuas ciam teb tsuas yog ua ib zaug thaum qhov no tshwm sim. Qhov no yog ib lub tswv yim sib sib zog nqus, tab sis nws yooj yim txaus txawm rau ib tug novice programmer. Tej zaum kuv tsis tuaj yeem hais txog qhov cuam tshuam ntawm kev ua haujlwm rau lwm tus, tab sis tam sim ntawd kuv muaj peev xwm siv tau qhov kev txawj ntse no rau tus kheej thiab kev tshaj lij. Phau ntawv TAOCP yog tag nrho ntawm cov pob zeb zoo li no (kom ncaj ncees, kuj tseem muaj ntau yam coj txawv txawv hauv qhov ntawd, xws li ).
"Nrhiav, nrhiav
Yog li ntev
Nrhiav, nrhiav
Kuv tsuas xav seev cev xwb"
- Luther Vandross, "Kev Tshawb Fawb" (1980)
Typo #2
Qhov thib ob typo yog nyob rau hauv Volume 4A, Combinatorial Algorithms, Part 1. Nplooj 60 piav qhia txog ib qho teeb meem uas muaj kev teem caij neeg tuaj ua yeeb yam ntawm ntau lub twv txiaj yuam pov. Ntau tus neeg ua yeeb yam hauv lub neej tiag tiag raug suav hais tias yog piv txwv, suav nrog Lily Tomlin, Weird Al Yankovic, thiab Robin Williams, uas tseem muaj sia nyob thaum phau ntawv luam tawm. Knuth ib txwm sau cov npe tag nrho hauv qhov ntsuas, yog li Williams tau teev nyob rau nplooj 882 li "Williams, Robin McLorim." Tab sis nws lub npe nruab nrab xaus nrog "n" thiab tsis yog "m", uas yog, McLaurin.
McLaurin yog nws niam lub npe menyuam yaus. Nws yog tus ntxhais xeeb ntxwv ntawm Anselm Joseph McLaurin, 34th Governor ntawm Mississippi. Nws kav, thaj, tsis nco qab txog ib yam dab tsi zoo. Los ntawm phau ntawv :
"Qhov xwm txheej tseem ceeb tshaj plaws thaum lub sijhawm McLaurin tswj hwm yog Tebchaws Meskas tau tshaj tawm kev ua tsov rog rau Spain thaum lub caij nplooj ntoo hlav xyoo 1898... Hmoov tsis zoo, kev ua tsov rog yuav tau muab qee tus thawj coj hauv tsoomfwv muaj sijhawm los koom nrog kev xiab nyiaj. McLaurin tau raug liam tias muaj ntau yam kev xav tsis thoob, suav nrog kev tsis sib haum xeeb thiab kev siv ntau dhau ntawm lub hwj chim zam txim. Thaum lub sijhawm npau taws, cov neeg thuam thuam tus tswv xeev tias yog neeg qaug cawv, uas nws tau lees paub rau pej xeem. "
Keeb kwm yuam kev
Xav txog cov txheej txheem multiplication algorithm los ntawm tsev kawm ntawv cov ntaub ntawv kawm. Nws yuav tsum muaj pes tsawg tus lej sib npaug? Xav tias koj muab ntau ntxiv - tus lej rau -ib . Ua ntej muab tus lej thawj rau txhua tus lej ib ntawm ib. Ces muab tus lej thib ob rau txhua tus lej ib qho los ntawm ib qho thiab lwm yam kom txog thaum koj mus dhau txhua tus lej . Yog li ntawd ib txwm muab faib yuav tsum primitive multiplications. Tshwj xeeb, muab ob tus lej los ntawm qeb yuav tsum tau ib-digit multiplications.
Qhov no yog qhov phem, tab sis nws muaj peev xwm ua kom zoo dua cov txheej txheem siv ib txoj kev tsim los ntawm Soviet mathematician Anatoly Alekseevich Karatsuba. Wb ua txuj tias ΠΈ - ob tug lej lej; uas yog, muaj cov lej , , , zoo li ntawd ΠΈ (generalizing no algorithm rau cov zauv loj yuav tsum tau ib co manipulation; txawm hais tias nws tsis yog nyuaj heev, thiaj li tsis ua yuam kev nyob rau hauv cov ntsiab lus, kuv yuav zoo dua lo rau ib tug yooj yim piv txwv). Ces , , . Multiplying binomials muab . Tam sim no peb tseem muaj ib-digit multiplication: , , , . Tam sim no cia peb ntxiv thiab rho tawm . Tom qab ob peb qhov kev hloov kho tshiab, uas kuv yuav tawm ua ib qho kev tawm dag zog rau tus nyeem ntawv, nws hloov tawm - Tsuas yog peb tus lej sib npaug! (Muaj qee qhov coefficients tas li, tab sis lawv tsuas yog suav tau los ntawm kev ntxiv thiab hloov cov lej).
Tsis txhob thov kom muaj pov thawj, tab sis Karatuba algorithm (recursively generalized los ntawm cov piv txwv saum toj no) txhim kho nyob rau hauv ib txwm multiplication txoj kev nrog kev ua haujlwm ua ntej . Thov nco ntsoov tias qhov no yog qhov kev txhim kho tiag tiag rau cov algorithm, tsis yog kev ua kom zoo rau kev xav txog kev xav. Tseeb, lub algorithm tsis haum rau kev puas siab puas ntsws arithmetic, vim hais tias nws yuav tsum tau nyiaj siv ua haujlwm loj rau kev ua haujlwm rov qab. Tsis tas li ntawd, cov nyhuv yuav tsis tshwm sim tag nrho nws tus kheej kom txog rau thaum cov lej loj txaus (hmoov zoo, Karatsuba's algorithm tau hloov los ntawm cov txheej txheem nrawm dua: thaum Lub Peb Hlis 2019, ib qho algorithm tau luam tawm uas tsuas yog xav tau. kev sib npaug; acceleration tsuas yog siv rau unimaginably loj tus lej).
Cov algorithm no tau piav qhia nyob rau nplooj 295 ntawm Volume XNUMX, Semi-Numerical Algorithms. Muaj Knuth sau tias: βNws xav paub tias lub tswv yim no tsuas yog nrhiav pom hauv 1962 xyoo, "thaum ib tsab xov xwm piav txog Karatsuba's algorithm tau luam tawm. Tab sis! Nyob rau hauv 1995, Karatsuba luam tawm ib daim ntawv ntawm "Computational Complexity," uas hais ob peb yam: 1) Nyob ib ncig ntawm 1956, Kolmogorov tau hais tias kev sib faib ua tsis tau tsawg dua. cov kauj ruam; 2) ib 1960 xyoo Karatsuba tau mus koom lub rooj sib tham uas Kolmogorov nthuav qhia nws qhov kev xav nΒ². 3) "Nyob rau hauv ib lub lis piam," Karatsuba tsim lub "sib faib thiab conquer" algorithm; 4) nyob rau hauv 1962, Kolmogorov sau thiab luam tawm ib tsab xov xwm sawv cev ntawm Karatsuba nrog kev piav qhia ntawm algorithm. "Kuv tsuas paub txog tsab xov xwm no tom qab nws tau tshaj tawm dua."
Yog li qhov yuam kev yog qhov tsis yog 1962 yuav tsum tau teev tseg 1960 xyoo. Yog tag nrho.
ΠΠ½Π°Π»ΠΈΠ·
Nrhiav qhov yuam kev tsis tas yuav tsum muaj kev txawj tshwj xeeb.
- Thawj qhov yuam kev yog qhov tsis tseem ceeb npaum li qhov ua tau thiab nyob rau hauv qhov chaw pom zoo (thaum pib ntawm tshooj). Txhua tus neeg ruam yuav pom nws; Kuv nyuam qhuav tig los ua tus neeg ruam ntawd.
- Nrhiav qhov thib ob typo xav tau koob hmoov thiab mob siab rau, tab sis tsis txawj. Qhov ntsuas rau "Williams" yog nyob rau ntawm nplooj ntawv kawg ntawm lub ntim, ib qho tseem ceeb ntawm phau ntawv. Kuv tsuas yog flipping los ntawm qhov Performance index (nws tsis zoo li nws suab, vim hais tias muaj Easter qe muab zais rau hauv Knuth's indexes. Piv txwv li, muaj kev nkag hauv Arabic thiab Hebrew, ob qho tib si taw rau nplooj 66. Tab sis nplooj ntawv ntawd tsis hais. ob hom lus; es tsis txhob hais txog "cov lus uas tau nyeem los ntawm sab xis mus rau sab laug"). Thiab lub npe thib ob ua rau kuv xav txog. Txij li thaum kuv feem ntau nyeem Wikipedia, kuv tau tshawb xyuas Robin Williams thiab pom qhov tsis sib xws.
- Kuv xav tias kuv tuaj yeem hais tias kuv tau tshawb fawb loj los nrhiav qhov yuam kev keeb kwm, tab sis tiag tiag kuv tsuas yog saib . Thawj cov kab hais tias: "Karatsuba algorithm yog kev sib txuas ceev ceev. Tshawb nrhiav los ntawm Anatoly Karatsuba hauv 1960 thiab luam tawm xyoo 1962. Tom qab ntawd tag nrho cov uas tshuav yog ntxiv ob thiab ob.
Nyob rau hauv lub neej yav tom ntej kuv xav nrhiav ib tug kab mob tseem ceeb, tshwj xeeb tshaj yog nyob rau hauv Knuth tus code. Kuv kuj xav pom cov kab laum hauv thawj ntim ntawm Fundamental Algorithms. Tej zaum kuv yuav pom nws, tab sis rau qee qhov laj thawj lub tsev qiv ntawv hauv zos tsuas muaj cov ntim 2, 3 thiab 4A.
Cov ntsiab lus nyiaj txiag:
- Nyob rau hauv tag nrho, kuv cov nyiaj pab rau TAOCP tsuas muaj peb lub cim: ib qho ntxiv s, hloov m rau n ΠΈ 2 rau 0. Ntawm $2,56, cov no yog cov cim zoo nkauj zoo nkauj; Yog tias koj tau them cov nyiaj ntawd, ib tsab xov xwm ntawm 1000 lo lus (qhov nruab nrab ntawm plaub tus cim) yuav tau txais koj kaum tus loj.
- Nrog peb tus lej hexadecimal, kuv, nrog rau 29 lwm tus pej xeem, raug khi rau 69th qhov chaw ntawm cov npe ntawm cov neeg tso nyiaj nplua nuj tshaj plaws ntawm San Serriff Bank (raws li lub Tsib Hlis 1, 2019).
Lwm qhov kev sib tham txog kev txheeb xyuas los ntawm Knuth
-
Cov lus qhia dav dav rau kev nrhiav qhov yuam kev hauv Knuth cov phau ntawv. Feem ntau lawv txhawj xeeb txog kev ua yuam kev, uas kuv tsis muaj. Muaj ib lub tswv yim nyob ntawd uas kuv tau ua tiag tiag:
Nws yog qhov zoo tshaj los tos kom txog thaum koj tau sau cov txheej txheem yuam kev los xa. Los ntawm kev sib txuas ob peb qhov tseeb tab sis tsis muaj txiaj ntsig zoo heev, koj ua rau muaj kev pheej hmoo tias ib tus ntawm lawv yuav raug suav tias yog qhov yuam kev lossis cov lus qhia. Yog tias koj xa qhov yuam kev ib zaug ib zaug, txhua tus neeg tuaj yeem raug tsis lees paub.
Kuv tsis xav xa cov lus tsis zoo xwb, tab sis coj cov lus qhia thiab xa tsab ntawv tsuas yog thaum kuv pom qhov yuam kev keeb kwm uas zoo li hnyav txaus.
-
Ashutosh Mehra yog tus neeg nplua nuj thib peb hauv San Serriff nrog cov txiaj ntsig zoo ntawm 0x $ 207.f0 hauv BoSS.
- Lwm Yam:
Tau qhov twg los: www.hab.com