دونالد کنوت یک دانشمند کامپیوتر است که آنقدر به صحت کتاب هایش اهمیت می دهد که پیشنهاد می کند یک دلار هگز (2,56$، 0x1,00$) برای هر "خطای" یافت شده، که در آن خطا به عنوان هر چیزی که "از لحاظ فنی، تاریخی، تایپی یا سیاسی نادرست است" تعریف می شود. من واقعاً می خواستم از کنوت یک چک بگیرم، بنابراین تصمیم گرفتم به دنبال خطاهای موجود در اپوس مگنوم او باشم. "هنر برنامه نویسی" (TAOCP). ما موفق شدیم سه مورد را پیدا کنیم. به قول خود وفادار بود، کنات یک چک فرستاد 0x3,00 دلار.
همانطور که می بینید، این یک چک واقعی نیست. کنوت قبلا چک های واقعی ارسال می کرد، اما در سال 2008 متوقف شد . او اکنون "گواهی سپرده شخصی" را به (BoSS). او می گوید که حاضر است در صورت لزوم پول واقعی بفرستد، اما به نظر می رسد که این کار خیلی دردسرساز است.
دو تا اشتباه تایپی و یک اشتباه تاریخی پیدا کردم. من آنها را به ترتیب کاهش بی اهمیتی فهرست می کنم.
اشتباه تایپی شماره 1
اولین اشتباه تایپی در صفحه 392 جلد سوم «مرتب سازی و جستجو» سطر هشتم از پایین آمده است: «بعد از جستجوی ناموفق، گاهی اوقات (گاهی) مطلوب است که رکورد جدیدی در جدول حاوی K; روشی که این کار را انجام می دهد الگوریتم جستجو و درج نام دارد. اشتباه این است که در عوض چند وقت باید باشد گاهی.
البته چنین اشتباهی جای تعجب ندارد. مطمئناً در این مقاله چند اشتباه تایپی وجود دارد (هیچ پاداشی برای یافتن آنها وجود ندارد). چیزی که واقعاً تعجب آور است این است که برای مدت طولانی مورد توجه قرار نگرفت. صفحه 392 در اعماق بخش ریاضی دفن نشده است همان صفحه اول فصل XNUMX "جستجو"! شاید یکی از پرخواننده ترین بخش های کتاب باشد. در تئوری، باید کمترین اشتباه تایپی وجود داشته باشد، اما خیر.
به هر حال، اگر تا به حال به خواندن TAOCP فکر کرده اید، آن را امتحان کنید. بسیاری خواهند گفت که این است دایرکتوری، برای خواندن مستقیم در نظر گرفته نشده است، اما این درست نیست. نویسنده دیدگاه روشن و سبکی متمایز دارد. تنها چیزی که مانع خوانایی می شود، پیچیدگی ریاضیات است. با این حال، یک راهحل ساده وجود دارد: بخوانید تا زمانی که به ریاضیاتی که نمیفهمید برسید، از آن بگذرید و به بخش بعدی که میتوانید متوجه شوید بروید. با این روش خوندن حداقل 80 درصد کتاب رو از دست میدم اما 20 درصد دیگه عالیه!
همچنین گفته می شود که TAOCP غیر مرتبط، قدیمی است یا در غیر این صورت برای "برنامه نویسی واقعی" قابل اجرا نیست. این هم درست نیست. به عنوان مثال، بخش اول بعد از مقدمه به یافتن یک عنصر در یک آرایه مرتب نشده میپردازد. ساده ترین الگوریتم برای همه برنامه نویسان آشناست. اشاره گر را از ابتدای آرایه شروع کنید، سپس به صورت حلقه ای به صورت زیر عمل کنید:
- بررسی کنید که آیا عنصر فعلی مورد نظر است یا خیر. اگر چنین است، آن را برمی گردانیم. در غیر این صورت
- بررسی کنید که آیا نشانگر خارج از مرز آرایه است. اگر چنین است، یک خطا را برگردانید. در غیر این صورت
- بزرگنمایی کنید و ادامه دهید.
حال در نظر بگیرید: این الگوریتم به طور متوسط به چند بررسی کرانه نیاز دارد؟ در بدترین حالت، جایی که آرایه حاوی عنصر نیست، هر عنصر در لیست به یک بررسی نیاز دارد و به طور متوسط چیزی شبیه به 
. یک الگوریتم جستجوی هوشمندتر می تواند تنها با یک بررسی کرانه ها از بین برود. عنصر مورد نظر را به انتهای آرایه متصل کنید، سپس نشانگر را از ابتدای آرایه شروع کنید و به صورت حلقه ای به صورت زیر عمل کنید:
- بررسی کنید که آیا عنصر فعلی مورد نظر است یا خیر. اگر چنین است، اگر اشاره گر در آرایه باشد، یک پاسخ یا اگر اینطور نیست، یک خطا برمی گردانیم. در غیر این صورت
- بزرگنمایی کنید و ادامه دهید.
به هر طریقی، یافتن عنصر تضمین شده است، و زمانی که این اتفاق میافتد، بررسی کرانهها فقط یک بار انجام میشود. این یک ایده عمیق است، اما حتی برای یک برنامه نویس تازه کار به اندازه کافی ساده است. من احتمالاً نمی توانم در مورد ارتباط کار با دیگران صحبت کنم، اما بلافاصله توانستم این حکمت را هم برای کد شخصی و هم برای کد حرفه ای به کار ببرم. کتاب TAOCP پر از چنین جواهراتی است (انصافاً چیزهای عجیب و غریب زیادی در آن وجود دارد، مانند ).
"جستجو، جستجو
خیلی طولانی
جستجو، جستجو
من فقط می خواستم برقصم"
- لوتر وندروس، "جستجو" (1980)
اشتباه تایپی شماره 2
اشتباه تایپی دوم در جلد 4A، الگوریتم های ترکیبی، قسمت 1 است. صفحه 60 یک مشکل مربوط به برنامه ریزی کمدین ها برای اجرا در کازینوهای مختلف را شرح می دهد. چندین کمدین واقعی از جمله لیلی تاملین، ویرد آل یانکویچ و رابین ویلیامز که در زمان انتشار کتاب هنوز زنده بود به عنوان مثال ذکر شده اند. کنوت همیشه اسامی کامل را در فهرست فهرست می کند، بنابراین ویلیامز در صفحه 882 با عنوان "ویلیامز، رابین مک لوریم" فهرست شده است. اما نام میانی او با "n" به پایان می رسد نه "م"، یعنی مک لورین.
مک لورین نام دختر مادرش بود. او نوه دختری آنسلم جوزف مک لورین، سی و چهارمین فرماندار می سی سی پی بود. سلطنت او ظاهراً هیچ چیز خوبی به یاد نمی آورد. از کتاب :
«مهمترین رویداد در دوران دولت مک لورین، اعلان جنگ ایالات متحده علیه اسپانیا در بهار 1898 بود... متأسفانه، جنگ ممکن است برای برخی از مقامات دولتی این فرصت را فراهم کند تا درگیر رشوه خواری شوند. مک لورین به اقدامات مشکوک مختلفی از جمله خویشاوندی و استفاده بیش از حد از قدرت عفو متهم شد. در جریان جنبش اعتدال، منتقدان فرماندار را به شرابخواری متهم کردند که او علناً به آن اعتراف کرد.
اشتباه تاریخی
در نظر بگیرید الگوریتم ضرب سنتی از برنامه درسی مدرسه به چند عدد ضرب تک رقمی نیاز دارد؟ فرض کنید ضرب می کنید 
-عدد رقمی 
بر 
-بیت 
. ابتدا رقم اول را ضرب کنید 
برای هر رقم 
یکی یکی. سپس رقم دوم را ضرب کنید 
برای هر رقم 
یکی یکی و به همین ترتیب تا زمانی که تمام اعداد را مرور کنید 
. بنابراین ضرب سنتی نیاز دارد 
ضرب های اولیه به طور خاص، ضرب دو عدد در 
رتبه های مورد نیاز 
ضرب های تک رقمی
این بد است، اما می توان با استفاده از روشی که توسط ریاضیدان شوروی آناتولی آلکسیویچ کاراتسوبا توسعه یافته است، فرآیند را بهینه کرد. بیایید وانمود کنیم که 
и 
- اعداد اعشاری دو رقمی؛ یعنی اعداد وجود دارد 
, 
, 
, 
به طوری که 
и 
(تعمیم این الگوریتم به اعداد بزرگتر نیاز به دستکاری دارد؛ اگرچه خیلی سخت نیست، برای اینکه در جزئیات اشتباه نکنم، بهتر است به یک مثال ساده بپردازم). سپس 
, 
, 
. ضرب دوجمله ای ها به دست می آید 
. در حال حاضر هنوز داریم 
ضرب تک رقمی: 
, 
, 
, 
. حالا بیایید جمع و تفریق کنیم 
. بعد از چند بازآرایی که به عنوان تمرین برای خواننده می گذارم معلوم می شود 
- فقط سه ضرب تک رقمی! (برخی ضرایب ثابت وجود دارد، اما آنها را فقط می توان با جمع و جابجایی ارقام محاسبه کرد).
مدرک نپرس، اما الگوریتم کاراتسوبا (به صورت بازگشتی از مثال بالا تعمیم داده شده است) روش ضرب سنتی با را بهبود می بخشد 
عملیات قبل 
. لطفاً توجه داشته باشید که این یک بهبود واقعی در الگوریتم است، نه بهینه سازی برای محاسبات ذهنی. در واقع، این الگوریتم برای محاسبات ذهنی مناسب نیست، زیرا به هزینه های سربار زیادی برای عملیات بازگشتی نیاز دارد. علاوه بر این، تا زمانی که اعداد به اندازه کافی بزرگ نشوند، اثر به طور کامل خود را نشان نخواهد داد (خوشبختانه، الگوریتم Karatsuba با روشهای سریعتر جایگزین شده است: در مارس 2019، الگوریتمی منتشر شد که فقط به آن نیاز دارد. ضرب؛ شتاب فقط برای اعداد غیرقابل تصور بزرگ اعمال می شود).
این الگوریتم در صفحه 295 جلد XNUMX، الگوریتم های نیمه عددی توضیح داده شده است. در آنجا کنوت می نویسد: «عجیب است که این ایده فقط در سال کشف شد 1962 سال، زمانی که مقاله ای در مورد الگوریتم کاراتسوبا منتشر شد. ولی! در سال 1995، کاراتسوبا مقاله ای با عنوان "پیچیدگی محاسباتی" منتشر کرد که چندین چیز را می گوید: 1) در حدود سال 1956، کولموگروف پیشنهاد کرد که ضرب را نمی توان در کمتر از 
مراحل؛ 2) در 1960 سال کاراتسوبا در سمیناری شرکت کرد که در آن کولموگروف فرضیه n² خود را ارائه کرد. 3) «دقیقا در یک هفته»، کاراتسوبا الگوریتم «تقسیم کن و حکومت کن» را توسعه داد. 4) در سال 1962 کلموگروف مقاله ای نوشت و منتشر کرد از طرف کاراتسوبا با توضیح الگوریتم من فقط پس از انتشار مجدد این مقاله متوجه شدم.
بنابراین خطا این است که به جای 1962 باید مشخص شود 1960 سال همین.
تحلیل
یافتن خطاها به مهارت خاصی نیاز نداشت.
- اولین خطا تا حد امکان پیش پا افتاده بود و در مکانی نسبتاً قابل مشاهده بود (ابتدای فصل). هر احمقی می توانست آن را پیدا کند. تازه معلوم شد اون احمقم
- یافتن اشتباه تایپی دوم به شانس و پشتکار نیاز داشت، اما نه مهارت. نمایه «ویلیامز» در صفحه ماقبل آخر جلد، بخش نسبتاً برجسته کتاب است. فقط داشتم فهرست را ورق می زدم (آنقدرها هم که به نظر می رسد رقت انگیز نیست، زیرا تخم مرغ های عید پاک در فهرست های کنوت پنهان شده است. به عنوان مثال، ورودی هایی به زبان عربی و عبری وجود دارد که هر دو به صفحه 66 اشاره می کنند. اما در آن صفحه اشاره ای نشده است. هر دو زبان؛ در عوض به "زبان هایی که از راست به چپ خوانده می شوند" اشاره دارد). و نام دوم توجهم را جلب کرد. از آنجایی که من معمولا ویکیپدیا را مطالعه میکردم، رابین ویلیامز را بررسی کردم و متوجه اختلافی شدم.
- کاش می توانستم بگویم برای یافتن یک خطای تاریخی تحقیق جدی انجام دادم، اما واقعاً فقط نگاه کردم . همان سطرهای اول می گوید: «الگوریتم Karatsuba یک الگوریتم ضرب سریع است. در سال 1960 توسط آناتولی کاراتسوبا کشف و در سال 1962 منتشر شد. پس از آن تنها چیزی که باقی مانده بود اضافه کردن دو و دو بود.
در آینده میخواهم باگ مهمتری پیدا کنم، مخصوصاً در کد Knuth. من همچنین می خواهم یک اشکال در جلد اول الگوریتم های بنیادی پیدا کنم. شاید آن را پیدا می کردم، اما بنا به دلایلی کتابخانه محلی فقط جلدهای 2، 3 و 4A را دارد.
حقایق مالی:
- در کل، سهم من در TAOCP فقط شامل سه کاراکتر است: یک اضافه s، جایگزینی m بر n и 2 بر 0. با قیمت 2,56 دلار، این نمادهای بسیار سودآور هستند. اگر چنین پولی به شما پرداخت می شد، یک مقاله 1000 کلمه ای (به طور متوسط چهار کاراکتر) برای شما XNUMX دلار درآمد داشت.
- با سه دلار هگزادسیمال، من به همراه 29 شهروند دیگر در رتبه 69 در فهرست ثروتمندترین سپرده گذاران بانک سان سریف (از اول می 1) قرار گرفتیم.
بحث های دیگر در مورد چک از Knuth
توصیه های کلی برای یافتن خطا در کتاب های کنوت. بیشتر آنها مربوط به خطاهای فنی هستند که من ندارم. یک پیشنهاد وجود دارد که من آن را جدی گرفتم:
بهتر است صبر کنید تا مجموعه ای از خطاها را برای ارسال جمع آوری کنید. با ترکیب چندین خطای واقعی اما نه چندان ارزشمند، احتمال اینکه یکی از آنها واقعاً به عنوان یک اشتباه یا توصیه در نظر گرفته شود را افزایش می دهید. اگر خطاها را یکی یکی ارسال کنید، ممکن است هر کدام به صورت جداگانه رد شوند.
من نمی خواستم فقط اشتباهات تایپی مزخرف بفرستم، اما توصیه را قبول کردم و نامه را فقط زمانی فرستادم که یک اشتباه تاریخی پیدا کردم که به اندازه کافی جدی به نظر می رسید.
آشوتوش مهرا سومین سرمایه گذار ثروتمند در San Serriff با دارایی خالص 0x207.f0 دلار در BoSS است.
- متفرقه:
منبع: www.habr.com
