ڊونالڊ ڪنٿ هڪ ڪمپيوٽر سائنسدان آهي جيڪو پنهنجي ڪتابن جي درستگي بابت ايترو خيال رکندو آهي جيڪو هو مشورو ڏئي ٿو هڪ هيڪس ڊالر ($2,56, 0x$1,00) ڪنهن به "غلطي" لاءِ مليل آهي، جتي هڪ نقص ڪنهن به شيءِ جي طور تي بيان ڪيو ويو آهي جيڪو "ٽيڪنيڪل، تاريخي، ٽائپوگرافي، يا سياسي طور تي غلط آهي." مان واقعي Knuth کان هڪ چيڪ حاصل ڪرڻ چاهيان ٿو، تنهنڪري مون هن جي عظيم نظم ۾ غلطيون ڳولڻ جو فيصلو ڪيو "پروگرامنگ جو فن" (TAOCP). اسان ٽن کي ڳولڻ ۾ ڪامياب ٿي ويا. هن جي لفظ جي سچائي، نٽ لاء هڪ چيڪ موڪليو 0x$3,00.

جئين توهان ڏسي سگهو ٿا، اهو هڪ حقيقي چيڪ ناهي. Knuth حقيقي چيڪ موڪليندو هو، پر 2008 ۾ بند ٿيڻ سبب زبردست فراڊ. ھو ھاڻي موڪلي ٿو ”ذات جي ذاتي سرٽيفڪيٽ“ ڏانھن بئنڪ آف سين سريف (BoSS). هو چوي ٿو ته هو حقيقي پئسا موڪلڻ لاءِ تيار آهي جيڪڏهن گهربل هجي، پر اهو لڳي ٿو ته اهو تمام گهڻو پريشان آهي.

مون کي ٻه ٽائپس ۽ هڪ تاريخي غلطي ملي. مان انھن کي گھٽائڻ جي ترتيب ۾ لسٽ ڪندس.

ٽائيپ نمبر 1

پهرين ٽائپو صفحي 392 جي ٽئين جلد جي صفحي XNUMX تي آهي “ترتيب ۽ ڳولا”، اٺين لائين هيٺان کان: “ناڪام ڳولا کان پوءِ، ڪڏهن ڪڏهن (ڪڏهن) اهو ضروري هوندو آهي ته هڪ نئون رڪارڊ داخل ڪيو وڃي جنهن ۾ K؛ اهو طريقو جيڪو اهو ڪري ٿو ان کي سڏيو ويندو آهي ڳولا ۽ داخل ڪرڻ الگورتھم. ان جي بدران غلطي اها آهي ڪڏهن ٿيڻ گھرجي ڪڏهن ڪڏهن.

يقينن، اهڙي غلطي تعجب جي ڳالهه ناهي. صرف هن مضمون ۾ ڪجهه ٽائپس هجڻ جا پابند آهن (انهن کي ڳولڻ لاء ڪو انعام نه). ڇا واقعي حيرت انگيز آهي ته اهو ايتري عرصي تائين اڻڄاتل ٿي ويو. صفحو 392 رياضي واري حصي ۾ دفن ٿيل نه آهي، اهو آهي بلڪل پهريون صفحو باب XNUMX ”تلاش“! ممڪن آهي ته ڪتاب جي سڀ کان وڌيڪ پڙهيل حصن مان هڪ. نظريي ۾، اتي تمام گھٽ ٽائپس ھئڻ گھرجي، پر نه.

رستي ۾، جيڪڏهن توهان ڪڏهن به TAOCP پڙهڻ بابت سوچيو آهي، ان کي ڪوشش ڏيو. ڪيترائي چوندا ته هي آهي ڊاريڪٽري, سڌو پڙهڻ جو ارادو نه آهي، پر اهو سچ ناهي. ليکڪ جو هڪ واضح نقطه نظر ۽ هڪ مخصوص انداز آهي. صرف هڪ شيء جيڪا پڙهڻ جي صلاحيت ۾ رڪاوٽ آهي رياضي جي پيچيدگي آهي. تنهن هوندي، اتي هڪ سادو حل آهي: پڙهو جيستائين توهان رياضي ۾ نه اچو، توهان سمجهي نٿا سگهو، ان کي ڇڏي ڏيو، ۽ ايندڙ حصي ڏانهن وڃو جيڪو توهان سمجهي سگهو ٿا. هن طريقي سان پڙهڻ سان، مون کي گهٽ ۾ گهٽ 80٪ ڪتاب ياد اچي ٿو، پر ٻيو 20٪ عظيم آهي!

اهو پڻ چيو ويندو آهي ته TAOCP غير لاڳاپيل، پراڻو آهي يا ٻي صورت ۾ "حقيقي پروگرامنگ" تي لاڳو ناهي. اهو پڻ سچ ناهي. مثال طور، تعارف کان پوء پهريون سيڪشن هڪ غير ترتيب ڏنل صف ۾ هڪ عنصر ڳولڻ تي نظر اچي ٿو. آسان الورورٿم سڀني پروگرامرن کي واقف آهي. صف جي شروعات ۾ پوائنٽر کي شروع ڪريو، پوء ھيٺ ڏنل لوپ ۾ ڪريو:

1. چيڪ ڪريو ته موجوده عنصر گهربل آهي. جيڪڏهن ائين آهي، اسان ان کي واپس آڻينداسين؛ ٻي صورت ۾
2. چيڪ ڪريو ته پوائنٽر صف جي حد کان ٻاهر آهي. جيڪڏهن ائين آهي، هڪ غلطي واپس ڪريو؛ ٻي صورت ۾
3. وڏو ڪريو ۽ جاري رکو.

ھاڻي غور ڪريو: ھن الورورٿم کي ڪيتري حد تائين چيڪ ڪرڻ جي ضرورت آھي، سراسري طور تي؟ بدترين صورت ۾، جتي صف ۾ هڪ عنصر شامل نه آهي، فهرست ۾ هر عنصر هڪ چيڪ جي ضرورت هوندي، ۽ سراسري طور تي اهو ڪجهه هوندو. . هڪ هوشيار ڳولا الگورتھم صرف هڪ حد جي چيڪ سان پري ٿي سگهي ٿو. مطلوب عنصر کي صف جي آخر ۾ ڳنڍيو، پوء پوائنٽر کي صف جي شروعات ۾ شروع ڪريو ۽ ھيٺيون لوپ ۾ ڪريو:

1. چيڪ ڪريو ته موجوده عنصر گهربل آهي. جيڪڏهن ائين آهي، اسان هڪ جواب ڏينداسين جيڪڏهن پوائنٽر صف جي اندر آهي، يا هڪ غلطي جيڪڏهن اهو ناهي. ٻي صورت ۾
2. وڏو ڪريو ۽ جاري رکو.

هڪ طريقو يا ٻيو، عنصر مليل هجڻ جي ضمانت ڏني وئي آهي، ۽ حدن جي چڪاس صرف هڪ ڀيرو ڪئي ويندي آهي جڏهن اهو ٿئي ٿو. اھو ھڪڙو گہرا خيال آھي، پر اھو ڪافي سادو آھي جيتوڻيڪ ھڪڙو نوان پروگرامر لاءِ. مان شايد ٻين سان ڪم جي لاڳاپي تي ڳالهائي نٿو سگهان، پر مان فوري طور تي هن حڪمت کي ذاتي ۽ پيشه ورانه ڪوڊ تي لاڳو ڪرڻ جي قابل ٿي ويو آهيان. TAOCP ڪتاب اهڙن جواهرات سان ڀريل آهي (منصفانه هجڻ لاءِ، اتي به ڪيتريون ئي عجيب شيون آهن، جهڙوڪ بلبل جي ترتيب).

”ڳولڻ، ڳولهڻ
گهڻو ڊگهو
ڳولا ، تلاش
مان صرف ناچ ڪرڻ چاهيان ٿو"
- لوٿر وينڊروس، "دي سرچ" (1980)

ٽائيپ نمبر 2

ٻيو ٽائپو جلد 4A ۾ آهي، گڏيل الگورٿمس، حصو 1. صفحو 60 هڪ مسئلو بيان ڪري ٿو جنهن ۾ مختلف جوسينو تي ڪم ڪرڻ لاءِ ڪامريڊن کي شيڊيول ڪرڻ شامل آهي. ڪيترائي حقيقي زندگي جي مزاح نگارن کي مثال طور حوالو ڏنو ويو آهي، جن ۾ للي ٽاملن، ويئرڊ ال يانڪووڪ، ۽ رابن وليمس، جيڪي اڃا تائين زنده هئا جڏهن ڪتاب شايع ڪيو ويو هو. Knuth هميشه انڊيڪس ۾ مڪمل نالا لسٽ ڪري ٿو، تنهنڪري وليمس صفحي 882 تي "وليمز، رابن ميڪلورم" جي طور تي درج ڪيو ويو آهي. پر هن جو وچين نالو ”ن“ سان ختم ٿئي ٿو ۽ ”م“ نه، يعني ميڪلورين.

ميڪلورين سندس ماءُ جو پهريون نالو هو. هوءَ مسيسپي جي 34 هين گورنر انسلم جوزف ميڪلورين جي وڏي نياڻي هئي. سندس راڄ، ظاهري طور، ڪنهن به سٺي لاءِ ياد نه ڪيو ويو. ڪتاب مان "مسسيپي: تاريخ":

”ميلاورين انتظاميه جي دور ۾ سڀ کان اهم واقعو 1898ع جي بهار ۾ اسپين خلاف آمريڪا جو اعلان جنگ هو... بدقسمتيءَ سان، جنگ شايد ڪجهه سرڪاري عملدارن کي رشوت خوري ۾ مشغول ٿيڻ جو موقعو فراهم ڪيو هجي. McLaurin تي مختلف قابل اعتراض عملن جو الزام لڳايو ويو، جن ۾ اقربا پروري ۽ معافي جي طاقت جو گهڻو استعمال شامل آهي. مزاج جي تحريڪ دوران، نقادن گورنر تي شرابي هجڻ جو الزام لڳايو، جنهن جو هن عوامي طور تي اعتراف ڪيو.

تاريخي غلطي

غور ڪيو روايتي ضرب الخوارزمي اسڪول جي نصاب مان. ان لاءِ ڪيترا واحد عدد ضرب جي ضرورت آهي؟ فرض ڪريو ته ضرب ڪريو - عددي نمبر تي -بٽ . پھريون پھريون نمبر ضرب ڪريو هر عدد لاءِ هڪ هڪ ڪري. پوءِ ٻئي نمبر کي ضرب ڪريو هر عدد لاءِ هڪ هڪ ڪري پوءِ تيستائين جيستائين توهان سڀني نمبرن ذريعي نه وڃو . اهڙيء طرح روايتي ضرب جي ضرورت آهي ابتدائي ضربون. خاص طور تي، ٻن انگن کي ضرب ڪندي درجا گهربل واحد عددي ضرب.

اهو خراب آهي، پر اهو ممڪن آهي ته پروسيس کي بهتر ڪرڻ لاء هڪ طريقو استعمال ڪندي جيڪو سوويت رياضي دان اناتولي الڪسيويچ ڪراتسوبا طرفان تيار ڪيو ويو آهي. اچو ته اهو فرض ڪريون и  - ٻه عددي ڊيسيمل نمبر؛ يعني انگ آهن , , , اهڙي طرح и (هن الورورٿم کي عام ڪرڻ لاءِ وڏي انگن اکرن جي ضرورت آهي؛ جيتوڻيڪ اهو تمام ڏکيو نه آهي، تفصيلن ۾ غلطيون نه ڪرڻ لاءِ، مان هڪ سادي مثال تي ڀلو ويندس). پوءِ , , . binomials کي ضرب ڏئي ٿو . هن وقت اسان وٽ اڃا تائين آهي واحد عددي ضرب: , , , . ھاڻي اچو ته شامل ڪريو ۽ گھٽائي سگھون . ٿورن ترتيبن کان پوءِ، جيڪو مان پڙهندڙ لاءِ هڪ مشق جي طور تي ڇڏيندس، اهو نڪتو  - صرف ٽي واحد عددي ضرب! (ڪجهه مستقل ڪوئففينٽس آهن، پر اهي صرف انگن کي شامل ڪرڻ ۽ ڦيرائڻ سان حساب ڪري سگهجن ٿا).

ثبوت نه پڇو، پر Karatsuba الگورتھم (مٿي ڏنل مثال مان بار بار عام ڪيو ويو) روايتي ضرب جي طريقي سان بهتر ٿي آپريشن کان اڳ . مهرباني ڪري نوٽ ڪريو ته هي الورورٿم ۾ حقيقي سڌارو آهي، ذهني حسابن لاءِ اصلاح ناهي. درحقيقت، الورورٿم ذهني رياضي لاء مناسب نه آهي، ڇاڪاڻ ته ان کي ٻيهر ورهاڱي واري عملن لاء وڏي مٿي جي قيمت جي ضرورت آهي. ان کان علاوه، اهو اثر مڪمل طور تي ظاهر نه ٿيندو جيستائين انگ اکر ڪافي وڏا نه ٿي وڃن (خوش قسمتي سان، ڪارتسوبا جي الگورتھم کي اڃا به تيز طريقن سان تبديل ڪيو ويو آهي: مارچ 2019 ۾، هڪ الگورتھم شايع ڪيو ويو جيڪو صرف ضرورت آهي. ن لاگ ن ضرب تيز رفتار صرف ناقابل تصور وڏي تعداد تي لاڳو ٿئي ٿو).

هي الگورتھم جلد 295 جي صفحي XNUMX تي بيان ڪيو ويو آھي، نيم عددي الگورٿم. اتي Knuth لکي ٿو ته: ”اها دلچسپ ڳالهه آهي ته اهو خيال فقط سنڌ ۾ دريافت ٿيو هو 1962 سال، "جڏهن هڪ مضمون شايع ڪيو ويو جيڪو ڪراتسوبا جي الگورتھم کي بيان ڪري ٿو. پر! 1995 ۾، ڪراتسوبا هڪ مقالو "ڪمپيوٽيشنل پيچيدگي" شايع ڪيو، جنهن ۾ ڪيتريون ئي شيون آهن: 1) 1956 جي ڀرسان، ڪولموگوروف تجويز ڪيو ته ضرب کان گهٽ ۾ گهٽ نه ٿي سگهي. قدم؛ 2) ۾ 1960 سال ڪاراتسوبا سيمينار ۾ شرڪت ڪئي جتي ڪولموگوروف پنهنجو مفروضو پيش ڪيو n². 3) "بلڪل هڪ هفتي ۾،" ڪراتسوبا ترقي ڪئي "تقسيم ۽ فتح" الگورتھم؛ 4) 1962 ع ۾ Kolmogorov لکيو ۽ هڪ مضمون شايع ڪيو ڪارتسوبا جي طرفان الگورتھم جي وضاحت سان. "مون کي صرف هن آرٽيڪل بابت معلوم ٿيو جڏهن اهو ٻيهر شايع ڪيو ويو."

تنهنڪري غلطي اها آهي ته بدران 1962 بيان ڪيو وڃي 1960 سال. اهو ئي سڀ ڪجهه آهي.

تجزيو

غلطيون ڳولڻ لاء خاص مهارت جي ضرورت نه هئي.

1. پهرين غلطي ممڪن طور تي معمولي هئي ۽ نسبتا ڏسڻ واري جاء تي هئي (باب جي شروعات). ڪنهن بيوقوف کي اهو مليو هوندو. مان صرف اهو بيوقوف ٿي ويو آهيان.
2. ٻيو ٽائپو ڳولڻ لاء قسمت ۽ محنت جي ضرورت آهي، پر مهارت نه. "وليمس" لاءِ انڊيڪس حجم جي آخري صفحي تي آهي، ڪتاب جو ڪافي نمايان حصو. مان صرف انڊيڪس کي ڦيرائي رهيو هئس (اها ايترو ڏکوئيندڙ نه آهي جيترو اهو لڳي ٿو، ڇاڪاڻ ته ڪوٿ جي انڊيڪس ۾ ايسٽر ايگز لڪيل آهن. مثال طور، عربي ۽ عبراني ۾ داخل ٿيل آهن، ٻئي صفحي 66 ڏانهن اشارو ڪن ٿا. پر اهو صفحو ذڪر نٿو ڪري. يا ته ٻوليون؛ ان جي بدران "ٻوليون جيڪي پڙهيل آهن ساڄي کان کاٻي ڏانهن"). ۽ ٻيو نالو منهنجو ڌيان ڇڪايو. جيئن ته مان عام طور تي وڪيپيڊيا پڙهندو آهيان، مون رابن وليمز کي چيڪ ڪيو ۽ هڪ تفاوت محسوس ڪيو.
3. مان چاهيان ٿو ته مان چوان ها ته مون هڪ تاريخي غلطي ڳولڻ لاء سنجيده تحقيق ڪئي، پر حقيقت ۾ مون صرف ڏٺو وڪيپيڊيا صفحو ڪاراتسوبا جي الگورتھم بابت. بلڪل پهرين لائينون چون ٿا: "ڪراتسوبا الگورتھم ھڪڙو تيز ضرب الورورٿم آھي. 1960 ۾ اناتولي ڪراتسوبا پاران دريافت ڪيو ويو ۽ 1962 ۾ شايع ٿيو. ان کان پوءِ باقي بچيل هو ٻه ۽ ٻه شامل ڪرڻ.

مستقبل ۾ مان هڪ وڌيڪ اهم بگ ڳولڻ چاهيان ٿو، خاص طور تي Knuth جي ڪوڊ ۾. مان به هڪ بگ ڳولڻ چاهيان ٿو بنيادي الخوارزمي جي پهرين جلد ۾. ٿي سگهي ٿو مون کي اهو مليو هجي، پر ڪجهه سببن جي ڪري مقامي لائبريري ۾ صرف جلد 2، 3 ۽ 4A آهي.

مالي حقيقتون:

• مجموعي طور تي، TAOCP ۾ منهنجو حصو صرف ٽن اکرن تي مشتمل آهي: هڪ اضافو s، متبادل m تي n и 2 تي 0. $2,56 تي، اھي آھن ڪجھ خوبصورت نفعو نشان؛ جيڪڏهن توهان کي ان قسم جي رقم ادا ڪئي وئي هئي، 1000 لفظن جو هڪ آرٽيڪل (هڪ سراسري چار اکرن جو) توهان کي ڏهه گرانڊ حاصل ڪندو.
• ٽن هيڪس ڊيسيمل ڊالرن سان، مان، 29 ٻين شهرين سان گڏ، سان سريف بئنڪ جي امير ترين ذخيرو ڪندڙن جي لسٽ ۾ 69هين جاءِ تي جڙيل آهيان (1 مئي 2019 تائين).

Knuth کان چيڪن بابت ٻيا بحث

• Knuth کان چيڪ ڪيئن حاصل ڪجي

  Knuth جي ڪتابن ۾ غلطيون ڳولڻ لاء عام سفارشون. گهڻو ڪري اهي ٽيڪنيڪل غلطيون آهن، جيڪي مون وٽ نه آهن. اتي ھڪڙو مشورو آھي جنھن کي مون سنجيدگي سان ورتو آھي:

  اهو بهترين آهي انتظار ڪرڻ جيستائين توهان جمع ڪرڻ لاءِ غلطين جو هڪ سيٽ گڏ ڪيو. ڪيترن ئي حقيقي نه پر تمام قيمتي غلطين کي گڏ ڪرڻ سان، توهان اهو امڪان وڌو ٿا ته انهن مان هڪ کي اصل ۾ غلطي يا صلاح سمجهيو ويندو. جيڪڏهن توهان هڪ وقت ۾ هڪ غلطي جمع ڪريو ٿا، هر هڪ انفرادي طور تي رد ڪري سگهجي ٿو.

  مون نه ٿي چاهيو ته صرف بي معنيٰ ٽائيپون موڪلون، پر صلاح ورتي ۽ خط تڏهن ئي موڪليو جڏهن مون کي ڪا تاريخي غلطي ملي، جيڪا ڪافي سنجيده لڳي.

• آشوتوش مهرا جو چيڪ

  آشوتوش مهرا BoSS ۾ 0x$207.f0 جي وڏي خالص ماليت سان سين سيرف ۾ ٽيون امير ترين سيڙپڪار آهي.

• حقيقي TeX ڪوڊ ۾ ڪجھ غير فنڪشنل بگ لاءِ چيڪ ڪريو
• متفرق: #1 #2 #3 #4 #5 #6

جو ذريعو: www.habr.com