Доналд Кнут як олими компютер аст, ки дар бораи дурустии китобҳои худ, ки пешниҳод мекунад, хеле ғамхорӣ мекунад як шонздаҳ доллар ($2,56, 0x$1,00) барои ҳама гуна "хато"-и ёфтшуда, ки дар он хатогӣ ҳамчун ҳама чизест, ки "аз ҷиҳати техникӣ, таърихӣ, чопӣ ва ё сиёсӣ нодуруст" муайян карда мешавад. Ман дар ҳақиқат мехостам, ки аз Кнут чек гирам, бинобар ин ман қарор додам, ки дар асари бузурги ӯ хатогиҳоро ҷустуҷӯ кунам "Санъати барномасозӣ" (TAOCP). Мо тавонистем се нафарро пайдо кунем. Кнут ба кавли худ вафо кард, ба он чек фиристод 0х $3,00.

Тавре ки шумо мебинед, ин санҷиши воқеӣ нест. Knuth истифода мефиристад чек воқеӣ, Аммо қатъ дар 2008 бо сабаби қаллобии шадид. Ӯ ҳоло ба "сертификати амонатии шахсӣ" мефиристад Бонки Сан Серриф (БоСС). Ӯ мегӯяд, ки дар сурати зарурат омода аст пули ҳақиқиро бифиристад, аммо ба назар чунин мерасад, ки ин як мушкили зиёд аст.

Ман ду хатои хаттӣ ва як хатои таърихӣ пайдо кардам. Ман онҳоро бо тартиби кам кардани ночизӣ номбар мекунам.

Хатои №1

Хатогии аввал дар сањифаи 392 љилди сеюми «Мураттаб ва љустуљў», сатри њаштум аз поён: «Баъд аз љустуљўи бемуваффақият баъзан (баъзан) матлуб аст, ки дар ҷадвал сабти нав ворид карда шавад. K; усуле, ки ин корро мекунад, алгоритми ҷустуҷӯ ва воридкунӣ номида мешавад. Хатогӣ дар он аст, ки ба ҷои он баъзан бояд баъзан.

Албатта, чунин хатой тааҷҷубовар нест. Танҳо дар ин мақола ҳатман якчанд хатогиҳои чопӣ мавҷуданд (барои дарёфти онҳо мукофотпулӣ нест). Чизе, ки воқеан тааҷҷубовар аст, он аст, ки муддати тӯлонӣ нодида гирифта шуд. Саҳифаи 392 дар бахши математика амиқ дафн нашудааст, он аст саҳифаи аввал Боби 6 "Ҷустуҷӯ"! Эҳтимол яке аз бахшҳои аз ҳама хондани китоб. Дар назария, бояд камтарин хатогиҳо вуҷуд дошта бошанд, аммо не.

Дар омади гап, агар шумо ягон бор дар бораи хондани TAOCP фикр карда бошед, онро санҷед. Бисёриҳо мегӯянд, ки ин аст директория, барои мутолиаи мустақим пешбинӣ нашудааст, аммо ин дуруст нест. Муаллиф нуктаи назари равшан ва услуби хос дорад. Ягона чизе, ки ба хондан халал мерасонад, мураккабии математика аст. Бо вуҷуди ин, як роҳи ҳалли оддӣ вуҷуд дорад: то он даме, ки шумо ба математика нафаҳмед, хонед, онро гузаред ва ба бахши ояндае, ки шумо фаҳмед, гузаред. Бо ин роҳ, ман камаш 80% китобро аз даст медиҳам, аммо 20% боқимонда хеле хуб аст!

Инчунин гуфта мешавад, ки TAOCP номарбуте, кӯҳна шудааст ё ба таври дигар ба "барномасозии воқеӣ" мувофиқ нест. Ин ҳам дуруст нест. Масалан, бахши аввал пас аз муқаддима ба дарёфти элемент дар массиви ҷудонашуда назар мекунад. Соддатарин алгоритм барои ҳама барномасозон шинос аст. Нишондиҳандаро дар ибтидои массив оғоз кунед ва пас дар як давр амалҳои зеринро иҷро кунед:

1. Тафтиш кунед, ки оё унсури ҷорӣ як чизи дилхоҳ аст. Агар ин тавр бошад, мо онро бармегардонем; дар акси ҳол
2. Санҷед, ки нишондиҳанда берун аз сарҳади массив аст. Агар ин тавр бошад, хаторо баргардонед; дар акси ҳол
3. Масштаб кунед ва идома диҳед.

Акнун фикр кунед: ин алгоритм ба ҳисоби миёна чанд санҷишро талаб мекунад? Дар бадтарин ҳолат, ки дар он массив элемент мавҷуд набошад, ҳар як элементи рӯйхат як чекро талаб мекунад ва ба ҳисоби миёна он чизе монанди он хоҳад буд. . Алгоритми ҷустуҷӯи оқилона метавонад танҳо бо як чеки маҳдуд халос шавад. Элементи дилхоҳро ба охири массив замима кунед, пас нишондиҳандаро дар аввали массив оғоз кунед ва дар як давра амалҳои зеринро иҷро кунед:

1. Санҷед, ки оё унсури ҷории дилхоҳ аст. Агар ин тавр бошад, мо ҷавобро бармегардонем, агар нишоннамо дар дохили массив бошад, ё хатогӣ, агар он набошад. Дар акси ҳол
2. Масштаб кунед ва идома диҳед.

Бо ин ё он роҳ, пайдо шудани элемент кафолат дода мешавад ва санҷиши ҳудудҳо танҳо як маротиба ҳангоми рух додани ин сурат анҷом дода мешавад. Ин як идеяи амиқ аст, аммо он ҳатто барои як барномасози навкор кофӣ оддӣ аст. Эҳтимол ман дар бораи аҳамияти кор ба дигарон ҳарф зада наметавонам, аммо ман дарҳол тавонистам ин ҳикматро ҳам ба кодекси шахсӣ ва ҳам касбӣ татбиқ кунам. Китоби TAOCP пур аз чунин ганҷҳост (бо одилона, дар он ҷо чизҳои аҷиб низ зиёданд, масалан навъи ҳубобӣ).

"Ҷустуҷӯ, ҷустуҷӯ
Хайр
Ҷустуҷӯ, ҷустуҷӯ
Ман танҳо мехостам рақс кунам"
- Лютер Вандросс, "Ҷустуҷӯ" (1980)

Хатои №2

Хатогии дуюм дар Ҷилди 4А, Алгоритмҳои комбинатсияи, Қисми 1. Саҳифаи 60 мушкилотеро, ки ба нақша гирифтани ҳаҷвнигорон барои иҷроиш дар казиноҳои гуногун ҷалб мекунад, тасвир мекунад. Якчанд ҳаҷвнигорони воқеии ҳаёт ба унвони мисол оварда шудаанд, аз ҷумла Лили Томлин, Вайрд Ал Янкович ва Робин Вилямс, ки ҳангоми нашри китоб ҳанӯз зинда буданд. Кнут ҳамеша номҳои пурраро дар индекс номбар мекунад, бинобар ин Вилямс дар саҳифаи 882 ҳамчун "Уилямс, Робин МакЛорим" номбар шудааст. Аммо номи миёнааш бо "n" тамом мешавад, на "м", яъне МакЛорин.

Маклаурин номи духтари модараш буд. Вай набераи Анселм Ҷозеф Маклаурин, губернатори 34-уми Миссисипи буд. Подшоҳии ӯ, аз афташ, бо ягон чизи хуб ёдовар нашуд. Аз китоб "Миссисипи: Таърих":

«Мухимтарин вокеа дар давраи маъмурияти Мак-Лорин дар бахори соли 1898 ба мукобили Испания чанг эълон кардани Штатхои Муттахида буд... Мутаассифона, чанг шояд ба баъзе ходимони давлатй имконият дод, ки ба порахурй машгул шаванд. Маклауринро ба амалҳои мухталифи шубҳанок, аз ҷумла хешутаборбозӣ ва истифодаи аз ҳад зиёди ваколатҳои афв айбдор карданд. Дар ҷараёни ҳаракати таҳаммулпазирӣ мунаққидон ҳокимро ба майзада будан муттаҳам карданд, ки ӯ инро дар пеши назари мардум эътироф кард».

Хатогии таърихӣ

Тасаввур кунед алгоритми анъанавии зарб аз барномаи таълимии мактаб. Барои он чанд зарбкунии якрақама лозим аст? Фарз мекунем, ки шумо афзоиш медиҳед - рақами рақамӣ ба -бита . Аввал рақами аввалро зарб кунед барои ҳар як рақам як ба як. Сипас рақами дуюмро зарб кунед барои ҳар як рақам як ба як ва ғайра то он даме, ки шумо аз тамоми рақамҳо гузаред . Ҳамин тариқ, зарбкунии анъанавӣ талаб мекунад зарбҳои ибтидоӣ. Махсусан, зарб кардани ду адад ба рутбаҳо талаб карда мешавад зарбкунии якрақама.

Ин бад аст, вале процессро бо усули кор карда баромадаи математики советй Анатолий Алексеевич Карацуба оптимизация кардан мумкин аст. Биёед чунин вонамуд кунем и  - ададњои дурақамаи даҳӣ; яъне ракамхо мавчуданд , , , чунон ки и (умум кардани ин алгоритм ба ададҳои калон каме коркардро талаб мекунад; гарчанде ки ин чандон душвор нест, барои он ки дар тафсилот хато накунам, ман беҳтараш ба як мисоли одди мемонам). Баъд , , . Зарбкунии биномҳо медиҳад . Дар айни замон мо то ҳол дорем зарбкунии якрақама: , , , . Акнун биёед илова ва кам кунем . Пас аз чанде аз навсозӣ, ки ман ҳамчун машқ барои хонанда мегузорам, маълум мешавад  - танҳо се зарб як рақам! (Баъзе коэффитсиентҳои доимӣ мавҷуданд, аммо онҳоро танҳо бо роҳи илова ва иваз кардани рақамҳо ҳисоб кардан мумкин аст).

Далел напурс, аммо Алгоритми Карацуба (аз мисоли боло рекурсивӣ умумӣ) оид ба усули зарб анъанавии бо беҳтар амалиёти пеш . Лутфан таваҷҷӯҳ намоед, ки ин такмилдиҳии воқеии алгоритм аст, на оптимизатсия барои ҳисобҳои ақлӣ. Дарвоқеъ, алгоритм барои арифметикаи равонӣ мувофиқ нест, зеро он барои амалиёти рекурсивӣ хароҷоти зиёди изофӣ талаб мекунад. Илова бар ин, то он даме, ки рақамҳо ба қадри кофӣ калон нашаванд, эффект пурра зоҳир намешавад (хушбахтона, алгоритми Карацуба бо усулҳои боз ҳам тезтар иваз карда шуд: дар моҳи марти соли 2019 алгоритме нашр шуд, ки танҳо n log n зарб; шитоб танҳо ба ададҳои тасаввурнашавандаи калон дахл дорад).

Ин алгоритм дар саҳифаи 295 ҷилди XNUMX, Алгоритмҳои нимрақамӣ тасвир шудааст. Дар он ҷо Кнут менависад: «Аҷиб аст, ки ин идея танҳо дар 1962 сол», вақте ки мақолае, ки алгоритми Карацубаро тавсиф мекунад, нашр шуд. Аммо! Дар соли 1995, Карацуба мақолаеро дар бораи "Мушкилии ҳисоббарорӣ" нашр кард, ки дар он чанд чиз гуфта мешавад: 1) Тақрибан дар соли 1956, Колмогоров пешниҳод кард, ки зарбкунӣ дар муддати камтар аз қадамҳо; 2) дар 1960 сол Карацуба дар семинар иштирок кард, ки дар он Колмогоров гипотезаи n²-ро пешниҳод кард. 3) «Расаб дар як ҳафта» Карацуба алгоритми «тақсим кун ва ғалаба кун»-ро таҳия намуд; 4) соли 1962 Колмогоров макола навишта, чоп карда буд аз номи Карацуба бо тавсифи алгоритм. "Ман дар бораи ин мақола танҳо пас аз нашри он фаҳмидам."

Пас, хато дар он аст, ки ба ҷои 1962 бояд муайян карда шавад 1960 сол. Ҳамааш ҳамин.

Таҳлил

Ҷустуҷӯи хатоҳо маҳорати махсусро талаб намекард.

1. Хатогии аввал ба қадри имкон ночиз буд ва дар ҷои нисбатан намоён (ибтидои боб) буд. Ҳар як аблаҳ онро пайдо мекард; Ман танҳо он аблаҳ шудам.
2. Дарёфт кардани хатои дуюм бахт ва ғайратро талаб мекард, аммо маҳорат не. Индекси "Уилямс" дар саҳифаи охирини ҷилд ҷойгир аст, ки қисми хеле намоёни китоб аст. Ман танҳо индексро варақ зада будам (ин он қадар ғамгин нест, зеро дар индексҳои Кнут тухмҳои Пасха пинҳон шудаанд. Масалан, сабтҳо ба арабӣ ва ибрӣ мавҷуданд, ки ҳарду ба саҳифаи 66 ишора мекунанд. Аммо он саҳифа зикр нашудааст. ё забонҳо; ба ҷои он ба "забонҳое, ки аз рост ба чап хонда мешаванд") ишора мекунад. Ва номи дуюм диққати маро ба худ ҷалб кард. Азбаски ман одатан Википедияро мехонам, ман Робин Вилямсро тафтиш кардам ва ихтилоферо мушоҳида кардам.
3. Мехостам бигӯям, ки ман барои дарёфти хатои таърихӣ таҳқиқоти ҷиддӣ кардам, аммо дар ҳақиқат ман танҳо нигоҳ кардам Саҳифаи Википедиа дар бораи алгоритми Карацуба. Дар худи сатрхои аввал чунин гуфта мешавад: «Алгоритми Карацуба як алгоритми зарбкунии зуд аст. Анатолий Карацуба онро соли 1960 кашф карда, соли 1962 нашр кардааст». Пас аз ин ҳама чизи илова кардани ду ва ду боқӣ монд.

Дар оянда ман мехоҳам як хатои муҳимтаре пайдо кунам, махсусан дар коди Кнут. Ман инчунин мехостам хатоеро дар ҷилди якуми Алгоритмҳои бунёдӣ пайдо кунам. Шояд ман онро меёфтам, аммо бо кадом сабабе китобхонаи маҳаллӣ танҳо ҷилдҳои 2, 3 ва 4А дорад.

Фактҳои молиявӣ:

• Дар маҷмӯъ, саҳми ман дар TAOCP танҳо аз се аломат иборат аст: як илова s, иваз кардан m ба n и 2 ба 0. Бо нархи 2,56 доллар, инҳо баъзе рамзҳои хеле сердаромаданд; Агар ба шумо ин гуна пул пардохт карда шавад, мақолаи иборат аз 1000 калима (ба ҳисоби миёна чор аломат) ба шумо даҳ гранд мебуд.
• Бо се доллари шонздаҳӣ, ман дар қатори 29 шаҳрванди дигар дар рӯйхати сарватмандтарин амонатгузорони Сан Серриф Бонки (то 69 майи соли 1) дар зинаи 2019-ум қарор дорам.

Дигар муҳокимаҳо дар бораи чекҳо аз Knuth

• Чӣ тавр чекро аз Knuth гирифтан мумкин аст

  Тавсияҳои умумӣ барои дарёфти хатогиҳо дар китобҳои Кнут. Онҳо асосан ба хатогиҳои техникӣ дахл доранд, ки ман онро надорам. Як пешниҳоде ҳаст, ки ман онро ҷиддӣ қабул кардам:

  Беҳтар аст, ки интизор шавед, ки шумо маҷмӯи хатогиҳоро барои пешниҳод ҷамъоварӣ кунед. Бо якҷоя кардани якчанд хатогиҳои воқеӣ, вале на он қадар арзишманд, шумо эҳтимолияти онро зиёд мекунед, ки яке аз онҳо воқеан ҳамчун хато ё маслиҳат ҳисобида мешавад. Агар шумо хатогиҳоро дар як вақт пешниҳод кунед, ҳар яки онҳо метавонанд рад карда шаванд.

  Ман намехостам танҳо хатогиҳои бемаънӣ фиристам, аммо маслиҳатро гирифта, номаро танҳо вақте пайдо кардам, ки хатои таърихие, ки ба қадри кофӣ ҷиддӣ ба назар мерасид, фиристодам.

• Чекхои Ашутош Мехра

  Ашутош Мехра сеюмин сарватмандтарин сармоягузор дар Сан Серриф бо дороии бузурги 0x$207.f0 дар BoSS мебошад.

• Баъзе хатогиҳои ғайрифаъолро дар рамзи воқеии TeX тафтиш кунед
• Дигар: #1 #2 #3 #4 #5 #6

Манбаъ: will.com