Доналд Кнутх је информатичар који толико брине о тачности својих књига које предлаже један хексадецимални долар (2,56 УСД, 0к1,00 УСД) за било коју пронађену „грешку“, где се грешка дефинише као било шта што је „технички, историјски, типографски или политички нетачно“. Заиста сам желео да добијем чек од Кнута, па сам одлучио да потражим грешке у његовом магнум опусу "Уметност програмирања" (ТАОЦП). Успели смо да пронађемо три. Веран својој речи, Кнут је послао чек за 0к$3,00.
Као што видите, ово није права провера. Кнутх је слао праве чекове, али је престао 2008. због . Сада шаље "личне потврде о депозиту". (БоСС). Каже да је спреман да пошаље прави новац ако је потребно, али изгледа да је то превелика мука.
Нашао сам две грешке у куцању и једну историјску грешку. Навешћу их по опадајућој тривијалности.
Грешка у куцању #1
Прва штампарска грешка је на страни 392 трећег тома „Сортирање и претрага“, осми ред одоздо: „После неуспешне претраге, понекад (понекад) је пожељно унети нови запис у табелу која садржи K; метода која то ради назива се алгоритам претраге и уметања. Грешка је што уместо тога неко време требало би да буде понекад.
Наравно, таква грешка није изненађујућа. Само у овом чланку ће сигурно бити неколико грешака у куцању (нема награда за њихово проналажење). Оно што је заиста изненађујуће је да је тако дуго прошло незапажено. Страница 392 није закопана дубоко у секцији математике, јесте прва страница Поглавље 6 "Тражи"! Вероватно један од најчитанијих делова књиге. У теорији би требало да буде најмање грешака у куцању, али не.
Успут, ако сте икада размишљали о читању ТАОЦП-а, покушајте. Многи ће рећи да је то директоријум, није намењен директном читању, али то није тачно. Аутор има јасну тачку гледишта и карактеристичан стил. Једина ствар која отежава читљивост је сложеност математике. Међутим, постоји једноставно решење: читајте док не дођете до математике коју не разумете, прескочите је и пређите на следећи одељак који разумете. Читајући на овај начин, недостаје ми најмање 80% књиге, али осталих 20% је одлично!
Такође се каже да ТАОЦП небитно, је застарео или на други начин није применљив на „стварно програмирање“. Ово такође није тачно. На пример, први одељак након увода разматра проналажење елемента у несортираном низу. Најједноставнији алгоритам познат је свим програмерима. Покрените показивач на почетку низа, а затим урадите следеће у петљи:
- Проверите да ли је тренутни елемент жељени. Ако је тако, враћамо га; иначе
- Проверите да ли је показивач изван границе низа. Ако јесте, вратите грешку; иначе
- Увећајте и наставите.
Сада размислите: колико провера граница у просеку захтева овај алгоритам? У најгорем случају, када низ не садржи елемент, сваки елемент на листи ће захтевати једну проверу, а у просеку ће бити нешто попут 
. Паметнији алгоритам претраживања могао би да се извуче са само једном провером граница. Причврстите жељени елемент на крај низа, затим покрените показивач на почетку низа и урадите следеће у петљи:
- Проверите да ли је тренутни елемент жељени. Ако је тако, враћамо одговор ако је показивач унутар низа, или грешку ако није. Иначе
- Увећајте и наставите.
На овај или онај начин, гарантовано је да ће елемент бити пронађен, а провера граница се врши само једном када се то догоди. Ово је дубока идеја, али је довољно једноставна чак и за програмера почетника. Вероватно не могу да говорим о релевантности рада за друге, али сам одмах успео да применим ову мудрост и на лични и на професионални кодекс. Књига ТАОЦП је пуна таквих драгуља (праведно речено, ту има и доста чудних ствари, као нпр. ).
„Тражи, тражи
Тако дуго
Тражи, тражи
Само сам хтео да играм"
— Лутер Вандрос, „Потрага“ (1980)
Грешка у куцању #2
Друга грешка у куцању је у том 4А, Комбинаторни алгоритми, део 1. Страна 60 описује проблем који укључује заказивање комичара за наступе у различитим коцкарницама. Неколико комичара из стварног живота наводе се као примери, укључујући Лили Томлин, Чудног Ал Јанковића и Робина Вилијамса, који је још био жив када је књига објављена. Кнутх увек наводи пуна имена у индексу, тако да је Вилијамс наведен на страни 882 као „Вилијамс, Робин Меклорим“. Али његово средње име се завршава са "н", а не са "м", односно МцЛаурин.
Меклаурин је било девојачко презиме његове мајке. Била је праунука Анселма Џозефа Меклорина, 34. гувернера Мисисипија. Његова владавина, очигледно, није остала упамћена ни по чему добром. Из књиге :
„Најважнији догађај током Меклоринове администрације била је објава рата Сједињених Држава Шпанији у пролеће 1898... Нажалост, рат је можда пружио неким владиним званичницима прилику да се упусте у подмићивање. Меклорин је оптужен за различите упитне праксе, укључујући непотизам и прекомерну употребу овлашћења за помиловање. Током покрета умерености, критичари су оптужили гувернера да је пијаница, што је он јавно признао.
Историјска грешка
Размотрити традиционални алгоритам множења из школског програма. Колико једноцифреног множења је потребно? Претпоставимо да се множите 
-дигитални број 
на 
-мало 
. Прво помножите прву цифру 
за сваку цифру 
један по један. Затим помножите другу цифру 
за сваку цифру 
један по један и тако редом док не прођете кроз све бројеве 
. Стога традиционално множење захтева 
примитивна множења. Конкретно, множење два броја са 
обавезни чинови 
једноцифрена множења.
Ово је лоше, али је могуће оптимизовати процес користећи метод који је развио совјетски математичар Анатолиј Алексејевич Карацуба. Хајде да се претварамо 
и 
- двоцифрени децимални бројеви; односно постоје бројеви 
, 
, 
, 
тако да 
и 
(генерализација овог алгоритма на веће бројеве захтева одређену манипулацију; иако није претешко, да не бих погрешио у детаљима, боље ћу се задржати на једноставном примеру). Онда 
, 
, 
. Множење бинома даје 
. У овом тренутку још увек имамо 
једноцифрено множење: 
, 
, 
, 
. Сада саберимо и одузмемо 
. После неколико престројавања, које ћу оставити као вежбу за читаоца, испада 
- само три једноцифрена множења! (Постоје неки константни коефицијенти, али они се могу израчунати само сабирањем и померањем цифара).
Не тражите доказ, али Каратсуба алгоритам (рекурзивно генерализовано из примера изнад) побољшава традиционални метод множења са 
операције пре 
. Имајте на уму да је ово право побољшање алгоритма, а не оптимизација за менталне прорачуне. Заиста, алгоритам није погодан за менталну аритметику, пошто захтева велике режијске трошкове за рекурзивне операције. Осим тога, ефекат се неће у потпуности манифестовати све док бројеви не постану довољно велики (на срећу, Каратсубин алгоритам је замењен још бржим методама: у марту 2019. објављен је алгоритам који захтева само множења; убрзање важи само за незамисливо велике бројеве).
Овај алгоритам је описан на страни 295 у том XNUMX, Полунумерички алгоритми. Тамо Кнут пише: „Занимљиво је да је ова идеја откривена тек у 1962 године“, када је објављен чланак који описује Карацубин алгоритам. Али! Карацуба је 1995. године објавио рад „Цомпутатионал Цомплекити” који каже неколико ствари: 1) око 1956. Колмогоров је сугерисао да се множење не може обавити за мање од 
степенице; 2) у 1960 године Карацуба је присуствовао семинару где је Колмогоров изнео своју хипотезу н². 3) „За тачно недељу дана“, Карацуба је развио алгоритам „завади па владај“; 4) Колмогоров је 1962. написао и објавио чланак у име Карацубе са описом алгоритма. „Сазнао сам за овај чланак тек након што је поново објављен.”
Дакле, грешка је што уместо 1962 мора бити наведен 1960 године. То је све.
Анализа
Проналажење грешака није захтевало посебну вештину.
- Прва грешка је била што тривијална и била је на релативно видљивом месту (почетак поглавља). Сваки идиот би га нашао; Управо сам испао тај идиот.
- Проналажење друге грешке у куцању захтевало је срећу и марљивост, али не и вештину. Индекс за „Вилијамса” налази се на претпоследњој страни свеске, прилично истакнутом делу књиге. Управо сам прелиставао индекс (није тако патетично као што звучи, јер у Кнутовим индексима постоје ускршња јаја сакривена. На пример, постоје уноси на арапском и хебрејском, оба упућују на страницу 66. Али та страница не помиње било који језици, уместо тога се односи на „језике који се читају с десна на лево“). И друго име ми је привукло пажњу. Пошто обично читам Википедију, проверио сам Робина Вилијамса и приметио неслагање.
- Волео бих да могу да кажем да сам урадио озбиљно истраживање да пронађем историјску грешку, али заиста сам само погледао . Већ у првим редовима се каже: „Алгоритам Каратсуба је алгоритам за брзо множење. Открио га је Анатолиј Карацуба 1960. и објавио 1962. После тога је остало само да саберемо два и два.
У будућности бих желео да пронађем значајнију грешку, посебно у Кнутовом коду. Такође бих желео да пронађем грешку у првом тому Фундаменталних алгоритама. Можда бих га и нашао, али из неког разлога локална библиотека има само томове 2, 3 и 4А.
Финансијске чињенице:
- Укупно, мој допринос ТАОЦП-у се састоји од само три карактера: једног додатка s, замена m на n и 2 на 0. По цени од 2,56 долара, ово су неки прилично уносни симболи; Да сте плаћени толики новац, чланак од 1000 речи (у просеку четири карактера) би вам донео десет хиљада.
- Са три хексадецимална долара, ја сам, са још 29 грађана, изједначен за 69. место на листи најбогатијих штедиша Сан Серифф банке (од 1. маја 2019. године).
Друге дискусије о чековима од Кнутха
Опште препоруке за проналажење грешака у Кнутовим књигама. Углавном се тичу техничких грешака, које ја немам. Постоји један предлог који сам озбиљно схватио:
Најбоље је да сачекате док не прикупите скуп грешака да бисте их послали. Комбиновањем неколико стварних, али не баш вредних грешака, повећавате вероватноћу да ће се једна од њих заиста сматрати грешком или саветом. Ако пошаљете грешке једну по једну, свака појединачно може бити одбијена.
Нисам желео да шаљем само глупе грешке у куцању, већ сам прихватио савет и послао писмо тек када сам пронашао историјску грешку која је деловала довољно озбиљно.
Ашутош Мехра је трећи најбогатији инвеститор у Сан Серифу са огромном нето вредношћу од 0к207.ф0 у БоСС-у.
- Остало:
Извор: ввв.хабр.цом
