Donald Knuth təklif etdiyi kitablarının düzgünlüyünə çox əhəmiyyət verən bir kompüter alimidir bir hex dollar ($2,56, 0x$1,00) aşkar edilmiş hər hansı "xəta" üçün, burada xətanın "texniki, tarixi, mətbəə və ya siyasi cəhətdən düzgün olmayan" hər hansı bir şey kimi müəyyən edildiyi. Mən həqiqətən Knuthdan çek almaq istəyirdim, ona görə də onun böyük əsərində səhvlər axtarmaq qərarına gəldim "Proqramlaşdırma sənəti" (TAOCP). Biz üçü tapmağı bacardıq. Sözünə sadiq qalan Knut çek göndərdi 0x3,00$.
Gördüyünüz kimi, bu, əsl çek deyil. Knuth əvvəllər real çeklər göndərirdi, lakin 2008-ci ildə dayandı . İndi o, “şəxsi depozit sertifikatları” göndərir (BoSS). O, lazım gələrsə, real pul göndərməyə hazır olduğunu deyir, amma görünür, bu, çox çətinlik yaradır.
İki yazı səhvi və bir tarixi səhv tapdım. Onları mənasızlığı azaltmaq üçün sıralayacağam.
Yazı xətası №1
Birinci hərf səhvi üçüncü cildin 392-ci səhifəsində "Çeşidləmə və axtarış", aşağıdan səkkizinci sətirdir: "Uğursuz axtarışdan sonra bəzən (bəzən) cədvələ yeni bir qeyd daxil etmək məsləhət görülür. K; bunu edən üsul axtarış və daxil etmə alqoritmi adlanır. Səhv bunun əvəzinə bəzən olmalıdır bəzən.
Təbii ki, belə bir səhv təəccüblü deyil. Təkcə bu məqalədə bir neçə yazı səhvi ola bilər (onları tapmaq üçün heç bir mükafat yoxdur). Həqiqətən təəccüblü olan odur ki, bu qədər uzun müddət diqqətdən kənarda qaldı. Səhifə 392 riyaziyyat bölməsində dərinə gömülməyib, elədir ilk səhifə Fəsil XNUMX "Axtarış"! Kitabın bəlkə də ən çox oxunan hissələrindən biridir. Teorik olaraq, ən az yazı səhvləri olmalıdır, amma yox.
Yeri gəlmişkən, əgər siz nə vaxtsa TAOCP oxumaq barədə düşünmüsünüzsə, cəhd edin. Çoxları deyəcək ki, bu belədir kataloq, birbaşa oxumaq üçün nəzərdə tutulmayıb, lakin bu doğru deyil. Müəllifin aydın baxış bucağı və fərqli üslubu var. Oxunma qabiliyyətinə mane olan yeganə şey riyaziyyatın mürəkkəbliyidir. Bununla belə, sadə bir həll yolu var: başa düşmədiyiniz riyaziyyata gələnə qədər oxuyun, keçin və başa düşə biləcəyiniz növbəti hissəyə keçin. Bu şəkildə oxuyanda kitabın ən azı 80%-i üçün darıxıram, amma qalan 20%-i əladır!
O da deyilir ki, TAOCP əhəmiyyətsiz, köhnəlmişdir və ya başqa şəkildə "real proqramlaşdırma" üçün tətbiq edilmir. Bu da doğru deyil. Məsələn, girişdən sonrakı birinci bölmə çeşidlənməmiş massivdə elementin tapılmasına baxır. Ən sadə alqoritm bütün proqramçılara tanışdır. Göstəricini massivin əvvəlində başlayın, sonra döngədə aşağıdakıları edin:
- Cari elementin istədiyiniz olub olmadığını yoxlayın. Əgər belədirsə, biz onu geri qaytarırıq; əks halda
- Göstəricinin massiv sərhədindən kənarda olub olmadığını yoxlayın. Əgər belədirsə, xətanı qaytarın; əks halda
- Yaxınlaşdırın və davam edin.
İndi düşünün: bu alqoritm orta hesabla neçə həddi yoxlama tələb edir? Ən pis halda, massivin elementi olmadığı halda, siyahıdakı hər bir element bir yoxlama tələb edəcək və orta hesabla bu kimi bir şey olacaq. . Daha ağıllı bir axtarış alqoritmi yalnız bir sərhəd yoxlaması ilə xilas ola bilər. İstədiyiniz elementi massivin sonuna əlavə edin, sonra göstəricini massivin əvvəlində başladın və döngədə aşağıdakıları edin:
- Cari elementin istədiyiniz olub olmadığını yoxlayın. Əgər belədirsə, göstərici massiv daxilindədirsə, cavab qaytarırıq, yoxsa xəta qaytarırıq. Əks halda
- Yaxınlaşdırın və davam edin.
Bu və ya digər şəkildə, elementin tapılmasına zəmanət verilir və bu baş verdikdə sərhədlərin yoxlanılması yalnız bir dəfə həyata keçirilir. Bu dərin fikirdir, lakin hətta təcrübəsiz bir proqramçı üçün kifayət qədər sadədir. Yəqin ki, əsərin başqaları üçün aktuallığı barədə danışa bilmərəm, amma bu hikməti həm şəxsi, həm də peşəkar koda dərhal tətbiq edə bildim. TAOCP kitabı belə qiymətli daşlarla doludur (ədalətli olmaq üçün orada çoxlu qəribə şeylər də var, məsələn ).
“Axtar, axtar
Bu qədər uzun
Axtar, axtar
Mən sadəcə rəqs etmək istəyirdim"
- Lüter Vandross, "Axtarış" (1980)
Yazı xətası №2
İkinci yazı xətası Cild 4A, Kombinatoriya alqoritmləri, 1-ci hissədədir. Səhifə 60 komediyaçıların müxtəlif kazinolarda çıxış etməsini planlaşdırmaqla bağlı problemi təsvir edir. Nümunə olaraq bir neçə real həyat komediyaçısı göstərilir, o cümlədən kitab nəşr olunanda hələ sağ olan Lili Tomlin, Qəribə Əl Yankoviç və Robin Uilyams. Knuth həmişə indeksdə tam adları sadalayır, buna görə də Williams 882-ci səhifədə "Williams, Robin McLorim" kimi qeyd olunur. Ancaq onun orta adı "m" deyil, "n" ilə bitir, yəni McLaurin.
McLaurin anasının qızlıq soyadı idi. O, Missisipi ştatının 34-cü qubernatoru Anselm Cozef MakLaurinin nəvəsi idi. Onun hakimiyyəti, görünür, yaxşı heç nə ilə yadda qalmadı. Kitabdan :
“MakLaurin administrasiyası dövründə ən mühüm hadisə ABŞ-ın 1898-ci ilin yazında İspaniyaya müharibə elan etməsi oldu... Təəssüf ki, müharibə bəzi dövlət məmurlarına rüşvətxorluqla məşğul olmaq imkanı yarada bilər. McLaurin müxtəlif şübhəli təcrübələrdə, o cümlədən qohumbazlıqda və əfv səlahiyyətlərindən həddən artıq istifadədə ittiham olunurdu. Təvazökarlıq hərəkatı zamanı tənqidçilər qubernatoru sərxoş olmaqda günahlandırdılar, o, bunu açıq şəkildə etiraf etdi”.
Tarixi səhv
Saymaq ənənəvi vurma alqoritmi məktəb kurikulumundan. Bunun üçün neçə təkrəqəmli vurma lazımdır? Tutaq ki, çoxaldınız -rəqəmli nömrə haqqında -bit . Əvvəlcə birinci rəqəmi çarpın hər bir rəqəm üçün bir bir. Sonra ikinci rəqəmi çoxaldın hər bir rəqəm üçün bütün nömrələri keçənə qədər bir-bir və s . Beləliklə, ənənəvi çarpma tələb edir primitiv vurmalar. Xüsusilə, iki ədədin çarpılması rütbələr tələb olunur təkrəqəmli vurmalar.
Bu pisdir, lakin sovet riyaziyyatçısı Anatoli Alekseeviç Karatsuba tərəfindən hazırlanmış metoddan istifadə edərək prosesi optimallaşdırmaq mümkündür. Belə iddia edək и - ikirəqəmli onluq ədədlər; yəni rəqəmlər var , , , belə и (bu alqoritmin daha böyük rəqəmlər üçün ümumiləşdirilməsi müəyyən manipulyasiya tələb edir; o qədər də çətin olmasa da, təfərrüatlarda səhvə yol verməmək üçün sadə bir nümunəyə sadiq qalacağam). Sonra , , . binomialların çarpılması verir . Hal-hazırda bizdə hələ də var təkrəqəmli vurma: , , , . İndi əlavə və çıxaq . Oxucu üçün bir məşq olaraq buraxacağım bir neçə düzəlişdən sonra belə çıxır - yalnız üç təkrəqəmli vurma! (Bəzi sabit əmsallar var, lakin onlar yalnız rəqəmlərin əlavə edilməsi və yerdəyişməsi ilə hesablana bilər).
Sübut istəməyin, amma Karatsuba alqoritmi (yuxarıdakı nümunədən rekursiv ümumiləşdirilmiş) ilə ənənəvi vurma metodunu təkmilləşdirir əvvəl əməliyyatlar . Nəzərə alın ki, bu, zehni hesablamalar üçün optimallaşdırma deyil, alqoritmin real təkmilləşdirilməsidir. Həqiqətən, alqoritm mental arifmetika üçün uyğun deyil, çünki rekursiv əməliyyatlar üçün böyük məsrəflər tələb edir. Bundan əlavə, rəqəmlər kifayət qədər böyük olana qədər təsir özünü tam şəkildə göstərməyəcək (xoşbəxtlikdən, Karatsuba alqoritmi daha sürətli üsullarla əvəz edilmişdir: 2019-cu ilin mart ayında yalnız tələb olunan bir alqoritm nəşr olundu. çarpma; sürətlənmə yalnız ağlasığmaz dərəcədə böyük ədədlərə aiddir).
Bu alqoritm 295-ci cild, Yarı-rəqəm alqoritmlərinin XNUMX-ci səhifəsində təsvir edilmişdir. Orada Knuth yazır: “Maraqlıdır ki, bu ideya yalnız burada kəşf edilmişdir 1962 il,” Karatsubanın alqoritmini təsvir edən məqalə dərc olundu. Amma! 1995-ci ildə Karatsuba bir neçə şeydən bəhs edən "Hesablama mürəkkəbliyi" məqaləsini nəşr etdi: 1) təxminən 1956-cı ildə Kolmoqorov vurmağın daha az müddətdə edilə bilməyəcəyini təklif etdi. addımlar; 2) içində 1960 il Karatsuba Kolmoqorov n² hipotezini təqdim etdiyi seminarda iştirak etdi. 3) “Düz bir həftə ərzində” Karatsuba “böl və qalib gəl” alqoritmini işləyib hazırladı; 4) 1962-ci ildə Kolmoqorov bir məqalə yazıb nəşr etdi Karatsuba adından alqoritmin təsviri ilə. “Mən bu məqalə haqqında ancaq yenidən dərc olunandan sonra xəbər tutdum.”
Belə ki, səhv əvəzinə 1962 müəyyən edilməlidir 1960 il. Hamısı budur.
Təhlil
Səhvləri tapmaq xüsusi bacarıq tələb etmirdi.
- Birinci səhv mümkün qədər mənasız idi və nisbətən görünən yerdə idi (fəslin əvvəli). İstənilən axmaq onu tapardı; Mən sadəcə o axmaq oldum.
- İkinci yazı səhvini tapmaq şans və çalışqanlıq tələb edirdi, lakin bacarıq yox. "Williams" üçün indeks kitabın kifayət qədər görkəmli hissəsində, cildin sondan əvvəlki səhifəsindədir. Mən sadəcə indeksi vərəqləyirdim (bu, göründüyü qədər acınacaqlı deyil, çünki Knutun indekslərində Pasxa yumurtaları gizlənir. Məsələn, ərəb və ivrit dillərində yazılar var, hər ikisi 66-cı səhifəyə işarə edir. Amma bu səhifədə qeyd olunmur. hər iki dil; bunun əvəzinə "sağdan sola oxunan dillərə" aiddir). Və ikinci ad diqqətimi çəkdi. Mən adətən Vikipediyanı oxuduğum üçün Robin Williamsı yoxladım və uyğunsuzluq hiss etdim.
- Kaş ki, tarixi bir səhv tapmaq üçün ciddi araşdırmalar apardığımı söyləyə biləydim, amma həqiqətən baxdım . İlk sətirlərdə deyilir: “Karatsuba alqoritmi sürətli vurma alqoritmidir. 1960-cı ildə Anatoli Karatsuba tərəfindən kəşf edilmiş və 1962-ci ildə nəşr edilmişdir”. Bundan sonra iki və iki əlavə etmək qaldı.
Gələcəkdə xüsusilə Knuth kodunda daha əhəmiyyətli bir səhv tapmaq istərdim. Mən həmçinin Fundamental Alqoritmlərin birinci cildində səhv tapmaq istərdim. Bəlkə də tapardım, amma nədənsə yerli kitabxanada yalnız 2, 3 və 4A cildləri var.
Maliyyə faktları:
- Ümumilikdə, mənim TAOCP-ə töhfəm yalnız üç simvoldan ibarətdir: bir əlavə s, yerdəyişmə m haqqında n и 2 haqqında 0. 2,56 dollara, bunlar olduqca gəlirli simvollardır; Əgər sizə bu cür pul ödənilsəydi, 1000 sözdən ibarət məqalə (ortalama dörd simvol) sizə on qran qazandırardı.
- Üç onaltılıq dollarla mən, digər 29 vətəndaşla birlikdə San Serriff Bankın ən zəngin əmanətçiləri siyahısında (69 may 1-cu il tarixinə) 2019-cu yerdəyik.
Knuth-dan çeklərlə bağlı digər müzakirələr
-
Knuthun kitablarında səhvləri tapmaq üçün ümumi tövsiyələr. Əsasən texniki səhvlərə aiddir, məndə yoxdur. Orada ciddi qəbul etdiyim bir təklif var:
Təqdim etmək üçün bir sıra səhvlər toplayana qədər gözləmək yaxşıdır. Bir neçə real, lakin çox dəyərli olmayan səhvləri birləşdirərək, onlardan birinin həqiqətən səhv və ya məsləhət kimi qəbul edilməsi ehtimalını artırmış olursunuz. Səhvləri bir-bir təqdim etsəniz, hər biri ayrı-ayrılıqda rədd edilə bilər.
Mən sadəcə cəfəngiyat səhvləri göndərmək istəmədim, ancaq kifayət qədər ciddi görünən tarixi bir səhv tapdığım zaman məsləhət aldım və məktubu göndərdim.
-
Ashutosh Mehra, BoSS-da 0x207.f0 xalis sərvəti ilə San Serrifin üçüncü ən zəngin investorudur.
- Müxtəlif:
Mənbə: www.habr.com