Дональд Кнут ол ұсынатын кітаптарының дәлдігіне қатты мән беретін компьютер ғалымы бір алтылық доллар ($2,56, 0x$1,00) табылған кез келген "қате" үшін, мұнда қате "техникалық, тарихи, типографиялық немесе саяси тұрғыдан дұрыс емес" кез келген нәрсе ретінде анықталады. Мен Кнуттан чек алғым келді, сондықтан мен оның негізгі шығармасынан қателерді іздеуді шештім «Бағдарламалау өнері» (TAOCP). Біз үшеуін таба алдық. Өз сөзінде тұрған Кнут чек жіберді 0x$3,00.

Көріп отырғаныңыздай, бұл нақты тексеру емес. Knuth бұрын нақты чектерді жіберетін, бірақ 2008 жылы тоқтатты кең таралған алаяқтық. Ол қазір «жеке депозиттік сертификаттарды» жібереді Сан-Серриф банкі (Бастық). Қажет болса, нақты ақшаны жіберуге дайын екенін айтады, бірақ бұл тым көп қиындық тудыратын сияқты.

Мен екі қате және бір тарихи қате таптым. Мен оларды тривиальдылықты азайту ретімен тізімдеймін.

№1 типография

Бірінші теру қатесі «Сұрыптау және іздеудің» үшінші томының 392-бетінде, төменгі жағынан сегізінші жол: «Сәтсіз іздеуден кейін кейде (кейде) кестеге жаңа жазба енгізген жөн. K; мұны жасайтын әдіс іздеу және кірістіру алгоритмі деп аталады. Оның орнына қателік мынада кейде болу керек кейде.

Әрине, мұндай қателік таң қалдырмайды. Тек осы мақалада бірнеше қате болуы мүмкін (оларды тапқаныңыз үшін сыйақы жоқ). Бір қызығы, оның ұзақ уақыт бойы байқалмай өткені. 392-бет математика бөлімінде терең көмілген жоқ, солай ең бірінші бет 6-тарау «Іздеу»! Кітаптың ең көп оқылатын бөлімдерінің бірі болуы мүмкін. Теорияда ең аз қателер болуы керек, бірақ жоқ.

Айтпақшы, егер сіз TAOCP оқуды ойлаған болсаңыз, оны көріңіз. Көбісі осылай дейді анықтамалық, тікелей оқуға арналмаған, бірақ бұл дұрыс емес. Автордың нақты көзқарасы, өзіндік стилі бар. Оқуға кедергі келтіретін жалғыз нәрсе - математиканың күрделілігі. Дегенмен, қарапайым шешім бар: сіз түсінбейтін математикаға келгенше оқыңыз, оны өткізіп жіберіңіз және түсінуге болатын келесі бөлімге өтіңіз. Осылай оқи отырып, мен кітаптың кем дегенде 80% сағындым, бірақ қалған 20% керемет!

Сондай-ақ TAOCP деп айтылады қатысы жоқ, ескірген немесе «нақты бағдарламалауға» басқаша түрде қолданылмайды. Бұл да дұрыс емес. Мысалы, кіріспеден кейінгі бірінші бөлім сұрыпталмаған массивтегі элементті табуды қарастырады. Ең қарапайым алгоритм барлық бағдарламашыларға таныс. Көрсеткішті массивтің басынан бастаңыз, содан кейін циклде келесі әрекеттерді орындаңыз:

1. Ағымдағы элемент қажетті элемент екенін тексеріңіз. Егер солай болса, біз оны қайтарамыз; әйтпесе
2. Көрсеткіш жиым шекарасынан тыс екенін тексеріңіз. Олай болса, қатені қайтарыңыз; әйтпесе
3. Үлкейтіп, жалғастырыңыз.

Енді қарастырыңыз: бұл алгоритм орта есеппен қанша шекті тексеруді қажет етеді? Ең нашар жағдайда, массивте элемент жоқ болса, тізімдегі әрбір элемент бір тексеруді қажет етеді және орта есеппен ол келесідей болады. . Ақылды іздеу алгоритмі тек бір шектеуді тексеруден құтыла алады. Қажетті элементті массивтің соңына бекітіңіз, содан кейін көрсеткішті массивтің басынан бастап, циклде келесі әрекеттерді орындаңыз:

1. Ағымдағы элемент қажетті элемент екенін тексеріңіз. Олай болса, көрсеткіш массив ішінде болса, жауап қайтарамыз немесе ол болмаса, қатені қайтарамыз. Әйтпесе
2. Үлкейтіп, жалғастырыңыз.

Қалай болғанда да, элементті табуға кепілдік беріледі және шекараларды тексеру бұл орын алған кезде бір рет орындалады. Бұл терең идея, бірақ бұл тіпті жаңадан бастаған бағдарламашы үшін де қарапайым. Мен жұмыстың басқаларға қатыстылығы туралы айта алмайтын шығармын, бірақ мен бұл даналықты жеке және кәсіби кодқа бірден қолдана алдым. TAOCP кітабы осындай асыл тастарға толы (әділдік үшін, онда көптеген оғаш нәрселер бар, мысалы көпіршікті сұрыптау).

«Іздеу, іздеу
Көріскенше
Іздеу, іздеу
Мен жай ғана билегім келді"
— Лютер Вандросс, «Іздеу» (1980)

№2 типография

Екінші қате 4А том, Комбинаторлық алгоритмдер, 1-бөлімде. 60-бет әр түрлі казиноларда ойнау үшін комедияларды жоспарлауға қатысты мәселені сипаттайды. Мысал ретінде бірнеше шынайы комедиялар келтірілген, соның ішінде кітап шыққан кезде әлі тірі болған Лили Томлин, Weird Al Yankovich және Робин Уильямс. Кнут индексте әрқашан толық есімдерді келтіреді, сондықтан Уильямс 882-бетте «Уильямс, Робин МакЛорим» деп көрсетілген. Бірақ оның әкесінің аты «m» емес, «n» әрпімен аяқталады, яғни Маклаурин.

Маклаурин оның анасының қыз есімі болды. Ол Миссисипидің 34-губернаторы Ансельм Джозеф Маклауриннің шөбересі болды. Оның билігі, шамасы, жақсы ештеңемен есте қалмады. Кітаптан «Миссисипи: тарих»:

«Маклорин әкімшілігі кезіндегі ең маңызды оқиға 1898 жылдың көктемінде Америка Құрама Штаттарының Испанияға соғыс жариялауы болды... Өкінішке орай, соғыс кейбір мемлекеттік шенеуніктерге парақорлықпен айналысу мүмкіндігін берген болуы мүмкін. Маклауринге непотизм және кешірім жасау өкілеттіктерін шамадан тыс пайдалануды қоса алғанда, әртүрлі күмәнді тәжірибелер үшін айып тағылды. Сабырлылық қозғалысы кезінде сыншылар губернаторды маскүнем деп айыптады, ол мұны көпшілік алдында мойындады».

Тарихи қателік

Қарастырыңыз дәстүрлі көбейту алгоритмі мектеп бағдарламасынан. Ол үшін қанша бір таңбалы көбейту керек? Сіз көбейдіңіз делік - таңбалы сан туралы -бит . Алдымен бірінші санды көбейтіңіз әрбір сан үшін кезекпен. Содан кейін екінші санды көбейтіңіз әрбір сан үшін барлық сандарды өткенше бір-бірден және т.б . Осылайша дәстүрлі көбейту қажет қарапайым көбейту. Атап айтқанда, екі санды көбейту дәрежелер қажет бір таңбалы көбейту.

Бұл жаман, бірақ кеңес математигі Анатолий Алексеевич Карацуба әзірлеген әдісті пайдаланып процесті оңтайландыруға болады. Солай етейік и  - екі таңбалы ондық сандар; яғни сандар бар , , , солай и (бұл алгоритмді үлкенірек сандарға жалпылау кейбір айла-шарғыларды қажет етеді; бұл өте қиын болмаса да, бөлшектерде қателіктер жібермеу үшін мен қарапайым мысалға сүйенемін). Содан кейін , , . Биномдарды көбейту береді . Қазіргі уақытта бізде әлі бар бір таңбалы көбейту: , , , . Енді қос және азайтайық . Оқырманға жаттығу ретінде қалдыратын бірнеше рет реттеуден кейін бұл шығады  - тек үш бір таңбалы көбейту! (Кейбір тұрақты коэффициенттер бар, бірақ оларды сандарды қосу және ауыстыру арқылы ғана есептеуге болады).

Дәлел сұрамаңыз, бірақ Карацуба алгоритмі (жоғарыдағы мысалдан рекурсивті жалпыланған) көмегімен дәстүрлі көбейту әдісін жақсартады алдындағы операциялар . Бұл ойша есептеулерді оңтайландыру емес, алгоритмді нақты жақсарту екенін ескеріңіз. Шынында да, алгоритм ментальді арифметика үшін жарамсыз, өйткені ол рекурсивті операциялар үшін үлкен үстеме шығындарды талап етеді. Сонымен қатар, нәтиже сандар жеткілікті үлкен болғанша өзін толық көрсетпейді (бақытымызға орай, Карацуба алгоритмі бұдан да жылдам әдістермен ауыстырылды: 2019 жылдың наурызында тек талап ететін алгоритм жарияланды. n журналы n көбейту; жеделдету елестету мүмкін емес үлкен сандарға ғана қолданылады).

Бұл алгоритм Жартылай сандық алгоритмдер 295-томының XNUMX-бетінде сипатталған. Онда Кнут былай деп жазады: «Бұл идеяның тек жылы ашылғаны қызық 1962 жылы» деген мақалада Карацубаның алгоритмін сипаттайтын мақала жарияланған. Бірақ! 1995 жылы Карацуба «Есептеу күрделілігі» туралы мақаласын жариялады, онда бірнеше нәрсе айтылады: 1) Шамамен 1956 жылы Колмогоров көбейтуді кемінде орындауға болмайтынын ұсынды. қадамдар; 2) жылы 1960 жылы Карацуба семинарға қатысып, Колмогоров өзінің n² гипотезасын ұсынды. 3) «Дәл бір аптада» Карацуба «бөліп ал және жең» алгоритмін әзірледі; 4) 1962 жылы Колмогоров мақала жазып, жариялады Карацуба атынан алгоритмнің сипаттамасымен. «Мен бұл мақаланы қайта жарияланғаннан кейін ғана білдім».

Сондықтан қате оның орнына 1962 көрсетілуі керек 1960 жыл. Осымен болды.

Талдау

Қателерді табу арнайы шеберлікті қажет етпеді.

1. Бірінші қате мүмкіндігінше тривиальды болды және салыстырмалы түрде көрінетін жерде болды (тараудың басы). Кез келген ақымақ оны тауып алар еді; Мен сол ақымақ болып шықтым.
2. Екінші қатені табу сәттілік пен еңбекқорлықты қажет етті, бірақ шеберлік емес. «Уильямс» индексі томның соңғы бетінде, кітаптың өте көрнекті бөлігінде. Мен жай ғана индексті парақтап отырдым (бұл соншалықты аянышты емес, өйткені Кнуттың индекстерінде Пасха жұмыртқалары жасырылған. Мысалы, араб және иврит тілдеріндегі жазбалар бар, екеуі де 66-бетті көрсетеді. Бірақ бұл бетте айтылмаған. кез келген тіл; оның орнына ол «оңнан солға қарай оқылатын тілдерді» білдіреді). Ал екінші есім менің назарымды аударды. Мен әдетте Википедияны оқитындықтан, Робин Уильямсты тексеріп, сәйкессіздікті байқадым.
3. Тарихи қатені табу үшін байыпты зерттеулер жасадым деп айтқым келеді, бірақ мен жай ғана қарап шықтым Карацуба алгоритмі туралы Wikipedia беті. Алғашқы жолдарда былай делінген: «Каратсуба алгоритмі – жылдам көбейту алгоритмі. 1960 жылы Анатолий Карацуба тауып, 1962 жылы жарық көрді». Осыдан кейін екі мен екіні қосу ғана қалды.

Болашақта мен маңызды қатені тапқым келеді, әсіресе Knuth кодында. Мен сондай-ақ Негізгі алгоритмдердің бірінші томында қате тапқым келеді. Мүмкін мен оны тапқан болар едім, бірақ қандай да бір себептермен жергілікті кітапханада тек 2, 3 және 4А томдары бар.

Қаржылық фактілер:

• Жалпы алғанда, менің TAOCP-ге қосқан үлесім тек үш таңбадан тұрады: бір қосымша s, ауыстыру m туралы n и 2 туралы 0. Бағасы 2,56 доллар, бұл өте пайдалы белгілер; Егер сізге осындай ақша төленетін болса, 1000 сөзден тұратын мақала (орта есеппен төрт таңба) сізге он ган табатын еді.
• Үш он алтылық доллармен мен басқа 29 азаматпен бірге San Serriff банкінің ең бай салымшылары тізімінде (69 жылдың 1 мамырындағы жағдай бойынша) 2019-шы орынды иемдендім.

Knuth чектері туралы басқа талқылаулар

• Кнуттан чекті қалай алуға болады

  Кнуттың кітаптарындағы қателерді табу бойынша жалпы ұсыныстар. Көбінесе олар менде жоқ техникалық қателерге қатысты. Мен байыпты қабылдаған бір ұсыныс бар:

  Жіберу үшін қателер жинағын жинағанша күткен дұрыс. Бірнеше нақты, бірақ өте құнды емес қателерді біріктіру арқылы сіз олардың біреуінің қате немесе кеңес ретінде қарастырылу ықтималдығын арттырасыз. Қателерді бір-бірден жіберсеңіз, әрқайсысы жеке қабылданбауы мүмкін.

  Мен жай ғана мағынасыз әріптерді жібергім келмеді, бірақ кеңесті қабылдап, тарихи қатені байқаған кезде ғана жібердім.

• Ашутош Мехраның чектері

  Ашутош Мехра BoSS-те 0x$207.f0 таза құнымен Сан-Серрифтің үшінші ең бай инвесторы.

• Нақты TeX кодындағы кейбір жұмыс істемейтін қателерді тексеріңіз
• Әртүрлі: #1 #2 #3 #4 #5 #6

Ақпарат көзі: www.habr.com