دونالد كنوث هو عالم كمبيوتر يهتم كثيرًا بدقة كتبه التي يقترحها دولار سداسي واحد ($2,56, 0x$1,00) لأي "خطأ" يتم العثور عليه، حيث يتم تعريف الخطأ على أنه أي شيء "غير صحيح من الناحية الفنية أو التاريخية أو المطبعية أو السياسية." أردت حقًا الحصول على شيك من "كنوث"، لذلك قررت البحث عن الأخطاء في أعماله الرائعة "فن البرمجة" (تاوكب). تمكنا من العثور على ثلاثة. وفيًا لكلمته، أرسل كنوت شيكًا بمبلغ 0x$3,00.
كما ترون، هذا ليس الاختيار الحقيقي. اعتاد كنوث على إرسال شيكات حقيقية، لكنه توقف في عام 2008 بسبب . وهو الآن يرسل "شهادات إيداع شخصية" إلى (رئيس). ويقول إنه على استعداد لإرسال أموال حقيقية إذا لزم الأمر، ولكن يبدو أن الأمر يمثل الكثير من المتاعب.
لقد وجدت خطأين مطبعيين وخطأ تاريخيًا واحدًا. سأدرجها بالترتيب لتقليل التافهة.
الخطأ المطبعي رقم 1
الخطأ المطبعي الأول موجود في الصفحة 392 من المجلد الثالث “الفرز والبحث”، السطر الثامن من الأسفل: “بعد بحث غير ناجح، أحيانًا (أحيانًا) من المستحسن إدخال سجل جديد في الجدول الذي يحتوي على K; الطريقة التي تقوم بذلك تسمى خوارزمية البحث والإدراج. الخطأ هو أنه بدلا من ذلك بعض الاحيان يجب أن يكون أحيانا.
وبطبيعة الحال، مثل هذا الخطأ ليس مفاجئا. لا بد أن تكون هناك بعض الأخطاء المطبعية في هذه المقالة وحدها (لا توجد مكافآت للعثور عليها). ما يثير الدهشة حقًا هو أنه لم يلاحظه أحد لفترة طويلة. الصفحة 392 ليست مدفونة في قسم الرياضيات، إنها كذلك الصفحة الأولى الفصل السادس "البحث"! ربما يكون أحد الأقسام الأكثر قراءة في الكتاب. من الناحية النظرية، ينبغي أن يكون هناك أقل عدد من الأخطاء المطبعية، ولكن لا.
بالمناسبة، إذا فكرت يومًا في قراءة TAOCP، فجرّب ذلك. سيقول الكثيرون أن هذا هو دليل، غير مخصص للقراءة المباشرة، ولكن هذا غير صحيح. يتمتع الكاتب بوجهة نظر واضحة وأسلوب مميز. الشيء الوحيد الذي يعيق سهولة القراءة هو تعقيد الرياضيات. ومع ذلك، هناك حل بسيط: اقرأ حتى تصل إلى الرياضيات التي لا تفهمها، وتخطيها، وانتقل إلى القسم التالي الذي يمكنك فهمه. عند القراءة بهذه الطريقة، أفتقد ما لا يقل عن 80% من الكتاب، لكن الـ 20% الأخرى رائعة!
ويقال أيضًا أن TAOCP عَرَضِيّ، قديم أو غير قابل للتطبيق على "البرمجة الحقيقية". وهذا أيضا غير صحيح. على سبيل المثال، القسم الأول بعد المقدمة يبحث في العثور على عنصر في مصفوفة غير مصنفة. أبسط خوارزمية مألوفة لجميع المبرمجين. ابدأ تشغيل المؤشر في بداية المصفوفة، ثم قم بما يلي في حلقة:
- تحقق مما إذا كان العنصر الحالي هو العنصر المطلوب. إذا كان الأمر كذلك، فإننا نعيده؛ خلاف ذلك
- تحقق مما إذا كان المؤشر خارج حدود الصفيف. إذا كان الأمر كذلك، قم بإرجاع خطأ؛ خلاف ذلك
- التكبير والمتابعة.
فكر الآن: كم عدد عمليات التحقق من الحدود التي تتطلبها هذه الخوارزمية في المتوسط؟ في أسوأ الحالات، حيث لا تحتوي المصفوفة على عنصر، سيتطلب كل عنصر في القائمة فحصًا واحدًا، وفي المتوسط سيكون شيئًا مثل 
. يمكن لخوارزمية بحث أكثر ذكاءً أن تفلت من خلال التحقق من الحدود مرة واحدة فقط. قم بإرفاق العنصر المطلوب بنهاية المصفوفة، ثم قم بتشغيل المؤشر في بداية المصفوفة وقم بما يلي في حلقة:
- تحقق مما إذا كان العنصر الحالي هو العنصر المطلوب. إذا كان الأمر كذلك، فإننا نعيد استجابة إذا كان المؤشر داخل المصفوفة، أو خطأ إذا لم يكن كذلك. خلاف ذلك
- التكبير والمتابعة.
بطريقة أو بأخرى، يتم ضمان العثور على العنصر، ويتم إجراء فحص الحدود مرة واحدة فقط عندما يحدث ذلك. هذه فكرة عميقة، لكنها بسيطة بما فيه الكفاية حتى بالنسبة للمبرمج المبتدئ. ربما لا أستطيع التحدث عن أهمية العمل للآخرين، لكنني تمكنت على الفور من تطبيق هذه الحكمة على كل من الكود الشخصي والمهني. كتاب TAOCP مليء بهذه الأحجار الكريمة (لكي نكون منصفين، هناك أيضًا الكثير من الأشياء الغريبة هناك، مثل ).
"بحث بحث
سنشتاق إليك
بحث بحث
أردت فقط أن أرقص"
- لوثر فاندروس، "البحث" (1980)
الخطأ المطبعي رقم 2
الخطأ المطبعي الثاني موجود في المجلد 4A، الخوارزميات التوافقية، الجزء 1. تصف الصفحة 60 مشكلة تتعلق بجدولة الكوميديين لتقديم عروضهم في كازينوهات مختلفة. تم الاستشهاد بالعديد من الكوميديين الواقعيين كأمثلة، بما في ذلك ليلي توملين، ويرد آل يانكوفيتش، وروبن ويليامز، الذي كان لا يزال على قيد الحياة عندما نُشر الكتاب. يسرد Knuth دائمًا الأسماء الكاملة في الفهرس، لذلك يتم إدراج Williams في الصفحة 882 باسم "Williams, Robin McLorim." لكن اسمه الأوسط ينتهي بحرف "ن" وليس "م"، أي ماكلورين.
كان ماكلورين هو الاسم الأول لوالدته. كانت حفيدة أنسيلم جوزيف ماكلورين، الحاكم الرابع والثلاثين لولاية ميسيسيبي. يبدو أن عهده لم يُذكر بأي شيء جيد. من الكتاب :
"كان الحدث الأكثر أهمية خلال إدارة ماكلورين هو إعلان الولايات المتحدة الحرب على إسبانيا في ربيع عام 1898... ولسوء الحظ، ربما أتاحت الحرب الفرصة لبعض المسؤولين الحكوميين للانخراط في الرشوة. اتُهم ماكلورين بممارسات مختلفة مشكوك فيها، بما في ذلك المحسوبية والاستخدام المفرط لسلطات العفو. خلال حركة الاعتدال، اتهم النقاد الحاكم بأنه سكير، وهو ما اعترف به علنًا.
خطأ تاريخي
نظر خوارزمية الضرب التقليدية من المنهج المدرسي . كم عدد الضربات المكونة من رقم واحد التي يتطلبها الأمر؟ لنفترض أنك تتضاعف 
-رقم الرقم 
في 
-قليل 
. أولا اضرب الرقم الأول 
لكل رقم 
واحدا تلو الآخر. ثم اضرب الرقم الثاني 
لكل رقم 
واحدًا تلو الآخر، وهكذا حتى تنتهي من جميع الأرقام 
. وبالتالي يتطلب الضرب التقليدي 
الضرب البدائي على وجه الخصوص، ضرب رقمين 
الرتب المطلوبة 
الضرب برقم واحد.
وهذا أمر سيئ، ولكن من الممكن تحسين العملية باستخدام طريقة طورها عالم الرياضيات السوفييتي أناتولي ألكسيفيتش كاراتسوبا. دعونا نتظاهر بذلك 
и 
- أرقام عشرية مكونة من رقمين؛ أي أن هناك أرقامًا 
, 
, 
, 
مثل ذلك 
и 
(يتطلب تعميم هذه الخوارزمية على أعداد أكبر بعض التلاعب؛ على الرغم من أنها ليست صعبة للغاية، حتى لا أرتكب أخطاء في التفاصيل، فمن الأفضل أن ألتزم بمثال بسيط). ثم 
, 
, 
. ضرب ذوات الحدين يعطي 
. في هذه اللحظة لا يزال لدينا 
الضرب برقم واحد: 
, 
, 
, 
. الآن دعونا نضيف ونطرح 
. بعد بعض عمليات إعادة الترتيب، والتي سأتركها كتمرين للقارئ، يتبين ذلك 
- ثلاثة مضاعفات مكونة من رقم واحد فقط! (توجد بعض المعاملات الثابتة، لكن لا يمكن حسابها إلا عن طريق جمع الأرقام وإزاحتها).
لا تطلب الدليل ولكن خوارزمية كاراتسوبا (يتم تعميمه بشكل متكرر من المثال أعلاه) يحسن طريقة الضرب التقليدية باستخدام 
العمليات من قبل 
. يرجى ملاحظة أن هذا يعد تحسينًا حقيقيًا للخوارزمية، وليس تحسينًا للحسابات الذهنية. في الواقع، الخوارزمية ليست مناسبة للحساب الذهني، لأنها تتطلب تكاليف عامة كبيرة للعمليات العودية. بالإضافة إلى ذلك، لن يظهر التأثير بالكامل حتى تصبح الأرقام كبيرة بما يكفي (لحسن الحظ، تم استبدال خوارزمية كاراتسوبا بطرق أسرع: في مارس 2019، تم نشر خوارزمية تتطلب فقط الضرب. ينطبق التسارع فقط على الأعداد الكبيرة التي لا يمكن تصورها).
تم وصف هذه الخوارزمية في الصفحة 295 من المجلد الثاني، الخوارزميات شبه الرقمية. هناك يكتب كنوث: «من الغريب أن هذه الفكرة لم تُكتشف إلا في 1962 العام"، عندما تم نشر مقال يصف خوارزمية كاراتسوبا. لكن! في عام 1995، نشر كاراتسوبا ورقة بحثية بعنوان "التعقيد الحسابي"، والتي تقول عدة أشياء: 1) حوالي عام 1956، اقترح كولموجوروف أن الضرب لا يمكن أن يتم في أقل من 
خطوات؛ 2 بوصة 1960 في العام التالي حضر كاراتسوبا الندوة التي قدم فيها كولموجوروف فرضيته n². 3) "في أسبوع واحد بالضبط"، طور كاراتسوبا خوارزمية "فرق تسد"؛ 4) في عام 1962 كتب كولموغوروف ونشر مقالاً نيابة عن كاراتسوبا مع وصف الخوارزمية. "لم أعرف عن هذا المقال إلا بعد إعادة نشره."
وبالتالي فإن الخطأ هو أنه بدلا من 1962 يجب تحديدها 1960 سنة. هذا كل شئ.
تحليل
العثور على الأخطاء لا يتطلب مهارة خاصة.
- الخطأ الأول كان تافهاً قدر الإمكان وكان في مكان ظاهر نسبياً (بداية الفصل). أي أحمق كان سيجدها؛ لقد تبين أنني ذلك الأحمق.
- يتطلب العثور على الخطأ المطبعي الثاني الحظ والاجتهاد، ولكن ليس المهارة. يوجد فهرس "وليامز" في الصفحة قبل الأخيرة من المجلد، وهو جزء بارز إلى حد ما من الكتاب. كنت أقلب للتو في الفهرس (ليس الأمر مثيرًا للشفقة كما يبدو، لأن هناك بيض عيد الفصح مخبأ في فهارس كنوث. على سبيل المثال، هناك إدخالات باللغتين العربية والعبرية، وكلاهما يشير إلى الصفحة 66. لكن تلك الصفحة لا تذكر أي من اللغتين؛ وبدلاً من ذلك يشير إلى "اللغات التي تُقرأ من اليمين إلى اليسار"). والاسم الثاني لفت انتباهي. وبما أنني عادة أقرأ ويكيبيديا، فقد قمت بمراجعة روبن ويليامز ولاحظت وجود تناقض.
- أتمنى أن أقول إنني أجريت بحثًا جادًا للعثور على خطأ تاريخي، لكنني في الحقيقة بحثت للتو . تقول الأسطر الأولى: "خوارزمية كاراتسوبا هي خوارزمية ضرب سريعة. اكتشفه أناتولي كاراتسوبا في عام 1960 ونشر في عام 1962. بعد ذلك، كل ما تبقى هو إضافة اثنين واثنين.
في المستقبل، أود العثور على خطأ أكثر أهمية، خاصة في كود Knuth. أود أيضًا العثور على خطأ في المجلد الأول من الخوارزميات الأساسية. ربما كنت سأعثر عليه، ولكن لسبب ما تحتوي المكتبة المحلية على المجلدات 2 و3 و4A فقط.
الحقائق المالية:
- في المجمل، تتكون مساهمتي في TAOCP من ثلاثة أحرف فقط: إضافة واحدة s، إستبدال m في n и 2 في 0. بسعر 2,56 دولارًا، تعد هذه بعض الرموز المربحة جدًا؛ إذا تم دفع هذا القدر من المال لك، فإن مقالًا مكونًا من 1000 كلمة (متوسط أربعة أحرف) سيكسبك عشرة آلاف دولار.
- مع وجود ثلاثة دولارات سداسية عشرية، أحتل أنا و29 مواطنًا آخر المركز 69 في قائمة أغنى المودعين في بنك سان سيريف (اعتبارًا من 1 مايو 2019).
مناقشات أخرى حول الشيكات من كنوث
توصيات عامة للعثور على الأخطاء في كتب كنوث. في الغالب يتعلق الأمر بالأخطاء الفنية، التي لا أملكها. هناك اقتراح واحد أخذته على محمل الجد:
من الأفضل الانتظار حتى تقوم بجمع مجموعة من الأخطاء لإرسالها. من خلال الجمع بين العديد من الأخطاء الحقيقية ولكن ليست ذات قيمة كبيرة، فإنك تزيد من احتمالية اعتبار أحدها خطأً أو نصيحة. إذا قمت بإرسال الأخطاء واحدًا تلو الآخر، فقد يتم رفض كل خطأ على حدة.
لم أكن أرغب في إرسال أخطاء مطبعية لا معنى لها فحسب، بل أخذت النصيحة وأرسلت الرسالة فقط عندما وجدت خطأً تاريخيًا بدا خطيرًا بدرجة كافية.
أشوتوش ميهرا هو ثالث أغنى مستثمر في سان سيريف بثروة صافية هائلة تبلغ 0x207.f0 دولار في BoSS.
- منوعات:
المصدر: www.habr.com
