دونالد كنوث هو عالم الكمبيوتر الذي يهتم كثيرا بصحة كتبه لدرجة أنه يقدم دولارًا سداسيًا واحدًا (2.56 دولارًا ، 0x دولار أمريكي 1.00) لأي "خطأ" يتم العثور عليه ، حيث يعتبر كل شيء "تقنيًا وتاريخيًا وطباعيًا" خطأ. " أو خطأ سياسيا ". أردت حقًا الحصول على شيك من كنوت ، لذلك قررت البحث عن أخطاء في عمله الرائع "فن البرمجة" (TAOCP). تمكنت من العثور على ثلاثة. طبقًا للكلمة ، أرسل Knut شيكًا بقيمة 0x 3.00 دولارات أمريكية .



كما ترون ، هذا ليس فحص حقيقي. كنوت تستخدم لإرسال الشيكات الحقيقية ، لكنها توقفت في عام 2008 بسبب الاحتيال المتفشي . الآن يرسل "شهادات إيداع شخصية" في بنك سان سيريف (BoSS). يقول إنه مستعد لإرسال أموال حقيقية إذا لزم الأمر ، لكن يبدو أنها مزعجة للغاية.

لقد وجدت اثنين من الأخطاء المطبعية والخطأ التاريخي واحد. سأذكرهم بترتيب تنازلي أقل.

خطأ مطبعي رقم 1

الخطأ المطبعي الأول موجود في الصفحة 392 من المجلد الثالث "الفرز والبحث" ، السطر الثامن من الأسفل: "بعد إجراء بحث غير ناجح ، أحيانًا (في وقت ما) يُنصح بإدخال سجل جديد في الجدول الذي يحتوي على K ؛ وتسمى الطريقة التي تفعل هذا البحث وإدراج خوارزمية. الخطأ هو أنه بدلا من وقت ما يجب أن يكون في بعض الأحيان .

بالطبع ، هذا الخطأ ليس مفاجئًا. فقط في هذه المقالة هناك بالتأكيد بعض الأخطاء المطبعية (لا توجد مكافآت للعثور عليها). ما يثير الدهشة حقا هو أنه لم يلاحظ لفترة طويلة. الصفحة 392 غير مدفونة بعمق في قسم الرياضيات ، فهذه هي الصفحة الأولى من الفصل السادس من "البحث"! ربما واحدة من أكثر أقسام قراءة الكتاب. من الناحية النظرية ، يجب أن يكون هناك أقل الأخطاء المطبعية ، ولكن لا.

بالمناسبة ، إذا فكرت في قراءة TAOCP ، فجربه. سيقول الكثيرون أن هذا دليل غير مخصص للقراءة المباشرة ، لكن هذا غير صحيح. المؤلف لديه وجهة نظر واضحة وأسلوب غريب. الشيء الوحيد الذي يمنع القراءة هو تعقيد الرياضيات. ومع ذلك ، هناك حل بسيط: اقرأ حتى تصل إلى الرياضيات التي لا تفهمها ، وتخطاها وافتح القسم التالي الذي يمكنك فهمه. أقرأ بهذه الطريقة ، افتقد 80٪ على الأقل من الكتاب ، لكن نسبة الـ 20٪ المتبقية رائعة!

يقولون أيضًا أن TAOCP غير ذي صلة أو قديم أو غير قابل للتطبيق على "برمجة حقيقية". هذا أيضا غير صحيح. على سبيل المثال ، في القسم الأول بعد المقدمة ، يعتبر البحث عن عنصر في صفيف غير مصنفة. أبسط الخوارزمية مألوفة لدى جميع المبرمجين. قم بتشغيل المؤشر في بداية الصفيف ، ثم قم بما يلي في حلقة:

1. تحقق ما إذا كان العنصر الحالي هو المطلوب. إذا كان الأمر كذلك ، قم بإعادته ؛ وإلا
   
2. تحقق مما إذا كان المؤشر خارج الصفيف. إذا كان الأمر كذلك ، فأرجع خطأ ؛ وإلا
   
3. زيادة المؤشر والمتابعة.

لنأخذ الآن في الاعتبار: كم عدد عمليات التحقق من الحدود التي تتطلبها هذه الخوارزمية ، في المتوسط؟ في أسوأ الحالات ، عندما لا تحتوي المصفوفة على عنصر ، يكون من الضروري إجراء فحص واحد لكل عنصر في القائمة ، وسيكون في المتوسط ​​شيئًا مثل $$$N / 2$ . يمكن لخوارزمية البحث الأكثر ذكاءً القيام بفحص حد واحد فقط. قم بتوصيل العنصر المطلوب بنهاية الصفيف ، ثم قم بتشغيل المؤشر في بداية الصفيف واتبع الخطوات التالية في حلقة:

1. تحقق ما إذا كان العنصر الحالي هو المطلوب. إذا كان الأمر كذلك ، فإننا نرجع الإجابة إذا كان المؤشر داخل الصفيف ، أو خطأ إذا لم يكن كذلك. وإلا
   
2. زيادة المؤشر والمتابعة.

بطريقة أو بأخرى ، يتم ضمان العثور على العنصر ، ويتم إجراء فحص الحدود مرة واحدة فقط ، عندما يحدث هذا. هذه فكرة عميقة ، لكنها بسيطة بما يكفي حتى بالنسبة للمبرمجين المبتدئين. ربما لا أستطيع التحدث عن أهمية العمل بالنسبة للآخرين ، لكنني تمكنت على الفور من تطبيق هذه الحكمة في كل من الشفرة الشخصية والمهنية. كتاب TAOCP مليء بهذه اللآلئ (في الإنصاف ، هناك العديد من الأشياء الغريبة ، مثل فرز الفقاعات ).

"البحث ، البحث
طويل جدا
البحث ، البحث
أردت فقط أن أرقص ".
- لوثر واندروس ، بحث (1980)

خطأ مطبعي رقم 2

الخطأ المطبعي الثاني موجود في المجلد 4A ، الخوارزميات التوافقية ، الجزء 1. في الصفحة 60 ، نصف مهمة التخطيط لأداء الكوميديين في الكازينوهات المختلفة. يُستشهد ببعض الممثلين الكوميديين الحقيقيين كمثال ، بما في ذلك ليلي توملين ، وسترينج آل يانكوفيتش ، وروبن ويليامز ، الذي كان لا يزال على قيد الحياة عندما صدر الكتاب. يعطي Whip دائمًا أسماء كاملة في الفهرس ، لذلك يشار إلى Williams في الصفحة 882 باسم "Williams ، Robin McLorim." لكن اسمه الأوسط ينتهي بـ "n" ، وليس بـ "m" ، أي McLoreen.

ماكلورين هو اسم والدته قبل الزواج. كانت حفيدة أنسيلم جوزيف مكلورين حفيدة ميسيسيبي الرابعة والثلاثين. حكمه ، على ما يبدو ، لم يتذكره أي شيء جيد. من كتاب ميسيسيبي: التاريخ :

"أهم حدث خلال إدارة ماكلورين كان إعلان الولايات المتحدة حرب إسبانيا في ربيع عام 1898 ... لسوء الحظ ، ربما مكنت الحرب بعض المسؤولين الحكوميين من ممارسة الرشوة. واتهم مكلورين بممارسات مشبوهة مختلفة ، بما في ذلك المحسوبية والاستخدام المفرط لقوى العفو. في عصر الرزانة ، اتهم النقاد محافظ السكر ، وهو ما اعترف به علنا ​​".

خطأ تاريخي

النظر في خوارزمية الضرب التقليدية من المناهج الدراسية. كم يتطلب عمليات الضرب ذات البت الواحد؟ افترض أنك تتضاعف $$$م دولا$ عدد بت $$$x$ في $$$ن$ بت $$$ذ$ . أولاً ، اضرب الرقم الأول $$$x$ لكل رقم $$$ذ$ يتناوبون. ثم ضرب الرقم الثاني $$$x$ لكل رقم $$$ذ$ يتناوبون وهلم جرا حتى تذهب من خلال جميع الأرقام $$$x$ . وبالتالي ، يتطلب الضرب التقليدية $$$مليون دولا$ مضاعفات بدائية. على وجه الخصوص ، ضرب عددين من قبل $$$ن$ التصريفات تتطلب $$$n ^ 2$ مضاعفات بت واحد.

هذا سيء ، لكن يمكنك تحسين العملية باستخدام الطريقة التي طورها عالم الرياضيات السوفيتي أناتولي أليكسييفيتش كاراتسوبا. افترض ذلك $$$x$ و $$$ذ$ - الأرقام العشرية المكونة من رقمين ؛ أي أن هناك أرقام $$$دولا$ . $$$ب$ . $$$ج$ . $$$د$ مثل هذا $$$x = (ab) _ {10}$ و $$$y = (cd) _ {10}$ (تعميم هذه الخوارزمية على أعداد كبيرة يتطلب بعض المعالجات ؛ على الرغم من أن هذا ليس صعبًا جدًا ، لكن حتى لا أكون مخطئًا في التفاصيل ، من الأفضل أن أكون مثالًا بسيطًا). ثم $$$x = 10a + b$ . $$$y = 10c + d$ . $$$xy = (10a + b) (10c + d)$ . الضرب ذو الحدين يعطي $$$xy = 100ac + 10ad + 10bc + bd$ . في الوقت الحالي ، ما زلنا $$$n ^ 2 = 4$ ضرب بت واحد: $$$ac$ . $$$ad$ . $$$قبل الميلا$ . $$$دولا$ . الآن إضافة وطرح $$ . بعد قليل من التباديل ، والذي سأتركه كتمرين للقارئ ، اتضح $$$xy = 110ac + 11bd + 10 (a - b) (d - c)$ - فقط ثلاثة مضاعفات من رقم واحد! (هناك بعض المعاملات الثابتة ، ولكن لا يمكن حسابها إلا عن طريق إضافة الأرقام وتحويلها).

لا تسأل عن إثبات ، ولكن خوارزمية Karatsuba (المعمم بشكل متكرر من المثال أعلاه) تعمل على تحسين الطريقة التقليدية للضرب مع $$$O (n ^ 2)$ عمليات من قبل $$$O (n ^ {(lg 3)})$ . يرجى ملاحظة أن هذا يمثل تحسينًا حقيقيًا في الخوارزمية ، وليس تحسينًا للحسابات الذهنية. في الواقع ، الخوارزمية ليست مناسبة للحساب في الاعتبار ، لأنها تتطلب مقدارًا كبيرًا من النفقات العامة للعمليات العودية. بالإضافة إلى ذلك ، لن يكون التأثير واضحًا تمامًا حتى تصبح الأرقام كبيرة بما يكفي (لحسن الحظ ، بدلاً من خوارزمية Karatsuba ، جاءت الطرق الأسرع: في مارس 2019 ، تم نشر خوارزمية تتطلب فقط مضاعفات n log n ؛ تسري تسري فقط على كبيرة لا يمكن تصورها أرقام).

هذه الخوارزمية موصوفة في الصفحة 295 من المجلد الثاني ، الخوارزميات المشتقة. هناك كتب نوث: "من الغريب أن هذه الفكرة لم تُكتشف إلا في عام 1962 " عندما نُشر مقال يصف خوارزمية كاراتسوبا. ولكن! في عام 1995 ، نشر كاراتسوبا مقالًا بعنوان "تعقيد الحوسبة" ، يقول عدة أشياء: 1) حوالي عام 1956 ، اقترح كولموغوروف أنه لا يمكن إجراء الضرب في أقل من $$$O (n ^ 2)$ الخطوات. 2) في عام 1960 ، حضر Karatsuba حلقة دراسية حيث قدم Kolmogorov فرضيته n². 3) "في غضون أسبوع بالضبط" ، وضعت Karatsuba خوارزمية "فرق تسد" ؛ 4) في عام 1962 ، كتب Kolmogorov ونشر مقالة نيابة عن Karatsuba مع وصف الخوارزمية. "اكتشفت هذا المقال فقط بعد إعادة طباعته."

وبالتالي ، فإن الخطأ هو أنه ينبغي الإشارة إلى عام 1960 بدلاً من عام 1962 . هذا كل شيء.

تحليل

البحث عن الأخطاء لا يتطلب الكثير من المهارة.

1. كان الخطأ الأول شائعًا قدر الإمكان ، وكان في مكان بارز نسبيًا (بداية الفصل). أي أحمق سيجدها ؛ لقد تحولت للتو إلى هذا الغبي.
   
2. العثور على الخطأ المطبعي الثاني يتطلب الحظ والعناية ، ولكن ليس المهارة. يوجد فهرس "Williams" في الصفحة ما قبل الأخيرة من المجلد ، وهو جزء بارز إلى حد ما من الكتاب. كنت أقفز من خلال الفهرس (ليس مثيرًا للشفقة كما يبدو لأن بيض عيد الفصح مخبأ في فهارس Knuth. على سبيل المثال ، هناك إدخالات باللغتين العربية والعبرية ، وكلاهما يشير إلى الصفحة 66. لكن هذه الصفحة لا تذكر إما اللغات ؛ بدلاً من ذلك ، يشير إلى "اللغات التي تتم قراءتها من اليمين إلى اليسار"). وجذبت انتباهي بالاسم الأوسط. منذ أن قرأت عادةً ويكيبيديا ، راجعت روبن ويليامز ولاحظت وجود تباين.
   
3. أود أن أقول أنني أجريت دراسة جادة للعثور على خطأ تاريخي ، لكنني في الواقع ألقيت نظرة فقط على صفحة ويكيبيديا حول خوارزمية Karatsuba . تقول الأسطر الأولى: "خوارزمية Karatsuba هي خوارزمية للضرب السريع. اكتشفها أناتولي كاراتسوبا في عام 1960 ونشرت في عام 1962. " بعد ذلك ، بقي فقط أضعاف مرتين.

في المستقبل ، أرغب في العثور على خطأ أكثر أهمية ، خاصة في كود Knuth. أود أيضًا العثور على خطأ في المجلد الأول ، الخوارزميات الأساسية. ربما كنت قد وجدت ذلك ، ولكن لسبب ما هناك فقط مجلدات 2 و 3 و 4A في المكتبة المحلية.

حقائق مالية:

• في المجموع ، تتكون مساهمي في TAOCP من ثلاثة أحرف فقط: واحد يضيف s ، ويستبدل m بـ n و 2 بـ 0 . بسعر 2.56 دولار ، هذه هي الرموز المربحة جدا. إذا كنت قد دفعت هذا النوع من المال ، فستجلب لك مقالة مؤلفة من 1000 كلمة (في المتوسط ​​، أربعة أحرف لكل منها) عشر قطع.
  
• مع ثلاثة دولارات سداسية عشرية ، أشترك مع 29 مواطناً آخر في المرتبة 69 في قائمة أغنى المودعين في بنك سان سيريف (اعتبارًا من 1 مايو 2019).

مناقشات أخرى من الشيكات كنوت

• كيفية الحصول على شيك من كنوت
  
  إرشادات عامة للعثور على الأخطاء في كتب Knut. معظمها أخطاء فنية ليست لدي. هناك اقتراح واحد أخذته بجدية:
  
  

  من الأفضل الانتظار حتى تجمع مجموعة من الأخطاء لإرسالها. من خلال الجمع بين العديد من الأخطاء الحقيقية ، ولكنها ليست ذات قيمة كبيرة ، ستزيد من احتمالية اعتبار أحدها خطأ أو نصيحة. إذا قمت بإرسال أخطاء واحدة في كل مرة ، فقد يتم رفض كل على حدة.

  
  لم أكن أرغب في إرسال أخطاء مطبعية هزلية ، لكنني أطعت النصيحة وأرسلت خطابًا فقط عندما وجدت خطأً تاريخيًا بدا أنه خطير بدرجة كافية
  
• الشيكات اشوتوش ميهرا
  
  يعد Ashutosh Mehra ثالث أغنى مساهم في San Serriff بثروة هائلة تبلغ 0x $ 207 ، و f0 في BoSS.
  
• تحقق من وجود بعض الأخطاء غير الوظيفية في رمز TeX الحقيقي
  
• متنوعة: # 1 # 2 # 3 # 4 # 5 # 6