டொனால்ட் நத் ஒரு கணினி விஞ்ஞானி, அவர் பரிந்துரைக்கும் புத்தகங்களின் துல்லியத்தைப் பற்றி அதிகம் அக்கறை காட்டுகிறார் ஒரு ஹெக்ஸ் டாலர் ($2,56, 0x$1,00) "தொழில்நுட்பம், வரலாற்று, அச்சுக்கலை அல்லது அரசியல் ரீதியாக தவறானது" என ஏதேனும் "பிழை" கண்டறியப்படும். நான் நூத்திடமிருந்து ஒரு காசோலையைப் பெற விரும்பினேன், அதனால் அவருடைய பெரிய படைப்பில் உள்ள பிழைகளைத் தேட முடிவு செய்தேன். "தி ஆர்ட் ஆஃப் புரோகிராமிங்" (TAOCP). நாங்கள் மூவரைக் கண்டுபிடிக்க முடிந்தது. அவரது வார்த்தையின்படி, நட் ஒரு காசோலையை அனுப்பினார் 0x$3,00.

நீங்கள் பார்க்க முடியும் என, இது ஒரு உண்மையான காசோலை அல்ல. Knuth உண்மையான காசோலைகளை அனுப்புவது வழக்கம், ஆனால் 2008 இல் நிறுத்தப்பட்டது பரவலான மோசடி. அவர் இப்போது "தனிப்பட்ட வைப்புச் சான்றிதழ்களை" அனுப்புகிறார் சான் செரிஃப் வங்கி (BoSS). தேவைப்பட்டால் உண்மையான பணத்தை அனுப்பத் தயாராக இருப்பதாக அவர் கூறுகிறார், ஆனால் இது மிகவும் தொந்தரவாகத் தெரிகிறது.

இரண்டு எழுத்துப் பிழைகளையும் ஒரு வரலாற்றுப் பிழையையும் கண்டேன். அற்பத்தன்மையைக் குறைக்கும் வரிசையில் அவற்றைப் பட்டியலிடுகிறேன்.

எழுத்துப்பிழை #1

முதல் எழுத்துப்பிழை "வரிசைப்படுத்துதல் மற்றும் தேடுதல்" இன் மூன்றாவது தொகுதியின் பக்கம் 392 இல் உள்ளது, கீழே இருந்து எட்டாவது வரி: "ஒரு தோல்வியுற்ற தேடலுக்குப் பிறகு, சில நேரங்களில் (சில நேரங்களில்) உள்ள அட்டவணையில் ஒரு புதிய பதிவை உள்ளிடுவது விரும்பத்தக்கது. K; இதைச் செய்யும் முறை தேடல் மற்றும் செருகல் வழிமுறை என்று அழைக்கப்படுகிறது. மாறாக அதுதான் தவறு சிறிது இருக்க வேண்டும் சில நேரங்களில்.

நிச்சயமாக, அத்தகைய தவறு ஆச்சரியமல்ல. இந்தக் கட்டுரையில் மட்டும் சில எழுத்துப் பிழைகள் இருக்க வேண்டும் (அவற்றைக் கண்டுபிடிப்பதற்கு வெகுமதிகள் இல்லை). உண்மையில் ஆச்சரியம் என்னவெனில், இத்தனை நாள் கவனிக்கப்படாமல் போனதுதான். பக்கம் 392 கணிதப் பிரிவில் ஆழமாகப் புதைக்கப்படவில்லை, அது முதல் பக்கம் அத்தியாயம் 6 "தேடல்"! புத்தகத்தில் அதிகம் வாசிக்கப்பட்ட பகுதிகளில் ஒன்றாக இருக்கலாம். கோட்பாட்டில், மிகக் குறைவான எழுத்துப் பிழைகள் இருக்க வேண்டும், ஆனால் இல்லை.

TAOCP ஐப் படிப்பது பற்றி நீங்கள் எப்போதாவது நினைத்திருந்தால், முயற்சித்துப் பாருங்கள். இது என்று பலர் கூறுவார்கள் அடைவு, நேரடியாக வாசிப்பதற்காக அல்ல, ஆனால் இது உண்மையல்ல. ஆசிரியருக்கு தெளிவான பார்வையும் தனித்துவமான நடையும் உள்ளது. படிக்கத் தடையாக இருப்பது கணிதத்தின் சிக்கலானது மட்டுமே. இருப்பினும், ஒரு எளிய தீர்வு உள்ளது: உங்களுக்குப் புரியாத கணிதம் வரும் வரை படித்து, அதைத் தவிர்த்துவிட்டு, அடுத்த பகுதிக்குச் செல்லவும். இந்த வழியில் படிக்கும் போது, ​​புத்தகத்தின் 80% ஐ மிஸ் பண்ணுகிறேன், ஆனால் மற்ற 20% நன்றாக இருக்கிறது!

TAOCP என்றும் கூறப்படுகிறது பொருத்தமற்ற, காலாவதியானது அல்லது "உண்மையான நிரலாக்கத்திற்கு" பொருந்தாது. இதுவும் உண்மையல்ல. எடுத்துக்காட்டாக, அறிமுகத்திற்குப் பிறகு முதல் பகுதி வரிசைப்படுத்தப்படாத வரிசையில் ஒரு உறுப்பைக் கண்டறிகிறது. எளிமையான அல்காரிதம் அனைத்து புரோகிராமர்களுக்கும் தெரிந்ததே. வரிசையின் தொடக்கத்தில் சுட்டிக்காட்டியைத் தொடங்கவும், பின் ஒரு சுழற்சியில் பின்வருவனவற்றைச் செய்யவும்:

1. தற்போதைய உறுப்பு விரும்பியதா என்பதைச் சரிபார்க்கவும். அப்படியானால், அதைத் திருப்பித் தருகிறோம்; இல்லையெனில்
2. வரிசை எல்லைக்கு வெளியே சுட்டிக்காட்டி உள்ளதா எனச் சரிபார்க்கவும். அப்படியானால், ஒரு பிழையைத் திருப்பி விடுங்கள்; இல்லையெனில்
3. பெரிதாக்கி தொடரவும்.

இப்போது கவனியுங்கள்: இந்த வழிமுறைக்கு சராசரியாக எத்தனை வரம்புகள் சரிபார்ப்புகள் தேவை? மோசமான நிலையில், அணிவரிசையில் ஒரு உறுப்பு இல்லை என்றால், பட்டியலில் உள்ள ஒவ்வொரு உறுப்புக்கும் ஒரு காசோலை தேவைப்படும், சராசரியாக அது இப்படி இருக்கும் . ஒரு புத்திசாலித்தனமான தேடல் அல்காரிதம் ஒரு வரம்பு சரிபார்ப்புடன் தப்பித்துவிடும். வரிசையின் முடிவில் விரும்பிய உறுப்பை இணைக்கவும், பின்னர் வரிசையின் தொடக்கத்தில் சுட்டிக்காட்டியைத் தொடங்கி, பின்வருவனவற்றை ஒரு சுழற்சியில் செய்யவும்:

1. தற்போதைய உறுப்பு விரும்பியதா என சரிபார்க்கவும். அப்படியானால், சுட்டி அணிவரிசைக்குள் இருந்தால் பதிலையோ அல்லது அது இல்லையெனில் பிழையையோ வழங்குவோம். இல்லையெனில்
2. பெரிதாக்கி தொடரவும்.

ஒரு வழி அல்லது வேறு, உறுப்பு கண்டுபிடிக்கப்படும் என்று உத்தரவாதம் அளிக்கப்படுகிறது, மேலும் இது நிகழும்போது ஒரு முறை மட்டுமே வரம்புகள் சரிபார்ப்பு செய்யப்படுகிறது. இது ஒரு ஆழமான யோசனை, ஆனால் இது ஒரு புதிய புரோகிராமருக்கு கூட போதுமானது. மற்றவர்களுக்கு வேலையின் பொருத்தத்தைப் பற்றி என்னால் பேச முடியாது, ஆனால் இந்த ஞானத்தை தனிப்பட்ட மற்றும் தொழில்முறை குறியீடு இரண்டிற்கும் உடனடியாகப் பயன்படுத்த முடிந்தது. TAOCP புத்தகம் அத்தகைய கற்களால் நிரம்பியுள்ளது (நியாயமாகச் சொல்வதானால், அதில் நிறைய விசித்திரமான விஷயங்கள் உள்ளன. குமிழி வகை).

"தேடு, தேடு
மிகவும் தூரம்
தேடு, தேடு
நான் நடனமாட விரும்பினேன்"
- லூதர் வான்ட்ரோஸ், "தேடல்" (1980)

எழுத்துப்பிழை #2

இரண்டாவது எழுத்துப்பிழை தொகுதி 4A, ஒருங்கிணைந்த அல்காரிதம்ஸ், பகுதி 1 இல் உள்ளது. பக்கம் 60 பல்வேறு கேசினோக்களில் நகைச்சுவை நடிகர்கள் நிகழ்ச்சிகளை நடத்த திட்டமிடுவதில் உள்ள சிக்கலை விவரிக்கிறது. புத்தகம் வெளியிடப்பட்டபோது உயிருடன் இருந்த லில்லி டாம்லின், வியர்ட் அல் யான்கோவிக் மற்றும் ராபின் வில்லியம்ஸ் உட்பட பல நிஜ வாழ்க்கை நகைச்சுவை நடிகர்கள் உதாரணங்களாகக் குறிப்பிடப்பட்டுள்ளனர். Knuth எப்போதும் குறியீட்டில் முழுப் பெயர்களையும் பட்டியலிடுகிறது, எனவே வில்லியம்ஸ் பக்கம் 882 இல் "வில்லியம்ஸ், ராபின் மெக்லோரிம்" என்று பட்டியலிடப்பட்டுள்ளார். ஆனால் அவரது நடுத்தர பெயர் "n" உடன் முடிவடைகிறது மற்றும் "m" அல்ல, அதாவது McLaurin.

மெக்லாரின் என்பது அவரது தாயின் இயற்பெயர். அவர் மிசிசிப்பியின் 34வது ஆளுநரான அன்செல்ம் ஜோசப் மெக்லாரினின் கொள்ளுப் பேத்தி ஆவார். அவரது ஆட்சி, வெளிப்படையாக, நல்ல எதையும் நினைவில் கொள்ளவில்லை. புத்தகத்தில் இருந்து "மிசிசிப்பி: வரலாறு":

"மெக்லாரின் நிர்வாகத்தின் போது மிக முக்கியமான நிகழ்வு 1898 வசந்த காலத்தில் ஸ்பெயின் மீது அமெரிக்கா போர் பிரகடனம் செய்தது... துரதிர்ஷ்டவசமாக, போர் சில அரசாங்க அதிகாரிகளுக்கு லஞ்சத்தில் ஈடுபடுவதற்கான வாய்ப்பை வழங்கியிருக்கலாம். மெக்லாரின் பல்வேறு சந்தேகத்திற்குரிய நடைமுறைகளில் குற்றம் சாட்டப்பட்டார், இதில் நேபாட்டிசம் மற்றும் மன்னிப்பு அதிகாரங்களின் அதிகப்படியான பயன்பாடு ஆகியவை அடங்கும். நிதான இயக்கத்தின் போது, ​​விமர்சகர்கள் கவர்னர் ஒரு குடிகாரன் என்று குற்றம் சாட்டினார்கள், அதை அவர் பகிரங்கமாக ஒப்புக்கொண்டார்.

வரலாற்றுத் தவறு

கவனியுங்கள் பாரம்பரிய பெருக்கல் அல்காரிதம் பள்ளி பாடத்திட்டத்தில் இருந்து. இதற்கு எத்தனை ஒற்றை இலக்க பெருக்கல்கள் தேவை? நீங்கள் பெருக்குகிறீர்கள் என்று வைத்துக்கொள்வோம் - இலக்க எண் மீது - பிட் . முதலில் முதல் இலக்கத்தை பெருக்கவும் ஒவ்வொரு இலக்கத்திற்கும் ஒவ்வொன்றாக. பின்னர் இரண்டாவது இலக்கத்தை பெருக்கவும் ஒவ்வொரு இலக்கத்திற்கும் நீங்கள் எல்லா எண்களையும் கடந்து செல்லும் வரை ஒவ்வொன்றாக மற்றும் பல . எனவே பாரம்பரிய பெருக்கல் தேவைப்படுகிறது பழமையான பெருக்கல்கள். குறிப்பாக, இரண்டு எண்களை பெருக்குவது தரவரிசைகள் தேவை ஒற்றை இலக்க பெருக்கல்.

இது மோசமானது, ஆனால் சோவியத் கணிதவியலாளர் அனடோலி அலெக்ஸீவிச் காரட்சுபா உருவாக்கிய முறையைப் பயன்படுத்தி செயல்முறையை மேம்படுத்துவது சாத்தியமாகும். என்று பாசாங்கு செய்யலாம் и  - இரண்டு இலக்க தசம எண்கள்; அதாவது எண்கள் உள்ளன , , , அதுபோல் и (இந்த அல்காரிதத்தை பெரிய எண்களுக்குப் பொதுமைப்படுத்த சில கையாளுதல்கள் தேவை; இது மிகவும் கடினம் அல்ல என்றாலும், விவரங்களில் தவறு செய்யாமல் இருக்க, நான் ஒரு எளிய எடுத்துக்காட்டுடன் ஒட்டிக்கொள்வேன்). பிறகு , , . இருசொற்களைப் பெருக்கினால் கிடைக்கும் . தற்போது எங்களிடம் உள்ளது ஒற்றை இலக்க பெருக்கல்: , , , . இப்போது கூட்டி கழிப்போம் . சில மறுசீரமைப்புகளுக்குப் பிறகு, வாசகருக்கு ஒரு பயிற்சியாக நான் விட்டுவிடுவேன், அது மாறிவிடும்  - மூன்று ஒற்றை இலக்க பெருக்கல்கள் மட்டுமே! (சில நிலையான குணகங்கள் உள்ளன, ஆனால் அவை இலக்கங்களைச் சேர்ப்பதன் மூலமும் மாற்றுவதன் மூலமும் மட்டுமே கணக்கிட முடியும்).

ஆதாரம் கேட்காதே, ஆனால் கரட்சுபா அல்காரிதம் (மேலே உள்ள எடுத்துக்காட்டில் இருந்து மீண்டும் மீண்டும் பொதுவானது) பாரம்பரிய பெருக்கல் முறையை மேம்படுத்துகிறது முன் செயல்பாடுகள் . இது அல்காரிதத்தின் உண்மையான முன்னேற்றம், மனக் கணக்கீடுகளுக்கான மேம்படுத்தல் அல்ல என்பதை நினைவில் கொள்ளவும். உண்மையில், அல்காரிதம் மன எண்கணிதத்திற்கு ஏற்றது அல்ல, ஏனெனில் இதற்கு சுழல்நிலை செயல்பாடுகளுக்கு அதிக செலவுகள் தேவைப்படுகின்றன. கூடுதலாக, எண்கள் போதுமான அளவு பெரிதாகும் வரை விளைவு முழுமையாக வெளிப்படாது (அதிர்ஷ்டவசமாக, கரட்சுபாவின் வழிமுறை இன்னும் வேகமான முறைகளால் மாற்றப்பட்டுள்ளது: மார்ச் 2019 இல், ஒரு வழிமுறை வெளியிடப்பட்டது, அது மட்டுமே தேவைப்படும் n பதிவு n பெருக்கல்கள்; முடுக்கம் கற்பனைக்கு எட்டாத பெரிய எண்களுக்கு மட்டுமே பொருந்தும்).

இந்த அல்காரிதம் தொகுதி 295, அரை-எண் அல்காரிதம்களின் பக்கம் XNUMX இல் விவரிக்கப்பட்டுள்ளது. அங்கு நூத் எழுதுகிறார்: "இந்த யோசனை கண்டுபிடிக்கப்பட்டது என்பது ஆர்வமாக உள்ளது 1962 ஆண்டு,” காரட்சுபாவின் அல்காரிதத்தை விவரிக்கும் கட்டுரை வெளியிடப்பட்டது. ஆனாலும்! 1995 ஆம் ஆண்டில், கரட்சுபா "கணக்கீட்டு சிக்கலானது" என்ற ஒரு ஆய்வறிக்கையை வெளியிட்டார், அதில் பல விஷயங்களைக் கூறுகிறது: 1) 1956 ஆம் ஆண்டில், கொல்மோகோரோவ் பெருக்கத்தை குறைவாக செய்ய முடியாது என்று பரிந்துரைத்தார். படிகள்; 2) இல் 1960 ஆண்டு காரட்சுபா கருத்தரங்கில் கலந்து கொண்டார், அங்கு கோல்மோகோரோவ் தனது கருதுகோளை n² வழங்கினார். 3) "சரியாக ஒரு வாரத்தில்," காரட்சுபா "பிரிந்து வெற்றி" அல்காரிதத்தை உருவாக்கினார்; 4) 1962 இல் கொல்மோகோரோவ் ஒரு கட்டுரையை எழுதி வெளியிட்டார் கரட்சுபா சார்பில் வழிமுறையின் விளக்கத்துடன். "இந்தக் கட்டுரையை மறுபிரசுரம் செய்த பிறகுதான் நான் அறிந்தேன்."

எனவே பிழை அதற்கு பதிலாக உள்ளது 1962 குறிப்பிடப்பட வேண்டும் 1960 ஆண்டு. அவ்வளவுதான்.

Анализ

பிழைகளைக் கண்டறிவதற்கு சிறப்புத் திறன் தேவையில்லை.

1. முதல் பிழை முடிந்தவரை அற்பமானது மற்றும் ஒப்பீட்டளவில் காணக்கூடிய இடத்தில் இருந்தது (அத்தியாயத்தின் ஆரம்பம்). எந்த முட்டாள் அதை கண்டுபிடித்திருப்பான்; நான் தான் அந்த முட்டாளாக மாறிவிட்டேன்.
2. இரண்டாவது எழுத்துப்பிழையை கண்டுபிடிப்பதற்கு அதிர்ஷ்டமும் விடாமுயற்சியும் தேவை, ஆனால் திறமை இல்லை. "வில்லியம்ஸ்" க்கான குறியீடு தொகுதியின் இறுதிப் பக்கத்தில் உள்ளது, இது புத்தகத்தின் முக்கிய பகுதியாகும். நான் குறியீட்டைப் புரட்டிப் பார்த்துக் கொண்டிருந்தேன் (அது கேட்கும் அளவுக்கு பரிதாபமாக இல்லை, ஏனென்றால் நூத்தின் குறியீடுகளில் ஈஸ்டர் முட்டைகள் மறைந்துள்ளன. உதாரணத்திற்கு, அரபு மற்றும் ஹீப்ருவில் உள்ளீடுகள் உள்ளன, இவை இரண்டும் பக்கம் 66ஐச் சுட்டிக்காட்டுகின்றன. ஆனால் அந்தப் பக்கம் குறிப்பிடப்படவில்லை. மொழிகள்; அதற்கு பதிலாக அது "வலமிருந்து இடமாக வாசிக்கப்படும் மொழிகள்" என்பதைக் குறிக்கிறது). இரண்டாவது பெயர் என் கவனத்தை ஈர்த்தது. நான் வழக்கமாக விக்கிபீடியாவைப் படிப்பதால், ராபின் வில்லியம்ஸைச் சரிபார்த்து, ஒரு முரண்பாட்டைக் கண்டேன்.
3. நான் ஒரு வரலாற்றுப் பிழையைக் கண்டுபிடிக்க தீவிர ஆராய்ச்சி செய்தேன் என்று சொல்ல விரும்புகிறேன், ஆனால் உண்மையில் நான் பார்த்தேன் கரட்சுபாவின் அல்காரிதம் பற்றிய விக்கிபீடியா பக்கம். முதல் வரிகள் கூறுகின்றன: “கரட்சுபா அல்காரிதம் ஒரு வேகமான பெருக்கல் அல்காரிதம். 1960 இல் அனடோலி கரட்சுபாவால் கண்டுபிடிக்கப்பட்டு 1962 இல் வெளியிடப்பட்டது." அதன் பிறகு இரண்டையும் இரண்டையும் கூட்டுவதுதான் மிச்சம்.

எதிர்காலத்தில் நான் மிகவும் குறிப்பிடத்தக்க பிழையைக் கண்டறிய விரும்புகிறேன், குறிப்பாக நூத்தின் குறியீட்டில். அடிப்படை அல்காரிதம்களின் முதல் தொகுதியிலும் பிழையைக் கண்டறிய விரும்புகிறேன். ஒருவேளை நான் அதைக் கண்டுபிடித்திருக்கலாம், ஆனால் சில காரணங்களால் உள்ளூர் நூலகத்தில் 2, 3 மற்றும் 4A தொகுதிகள் மட்டுமே உள்ளன.

நிதி உண்மைகள்:

• மொத்தத்தில், TAOCPக்கான எனது பங்களிப்பு மூன்று எழுத்துக்களை மட்டுமே கொண்டுள்ளது: ஒரு கூடுதலாக s, மாற்று m மீது n и 2 மீது 0. $2,56 இல், இவை சில அழகான இலாபகரமான சின்னங்கள்; உங்களுக்கு அந்த வகையான பணம் கொடுக்கப்பட்டால், 1000 வார்த்தைகள் (சராசரியாக நான்கு எழுத்துக்கள்) கொண்ட ஒரு கட்டுரை உங்களுக்கு பத்து பெரிய வருமானம் தரும்.
• மூன்று ஹெக்ஸாடெசிமல் டாலர்களுடன், நான் மற்ற 29 குடிமக்களுடன் சேர்ந்து, சான் செரிஃப் வங்கியின் பணக்கார டெபாசிடர்கள் பட்டியலில் (மே 69, 1 நிலவரப்படி) 2019 வது இடத்திற்கு இணைந்துள்ளோம்.

Knuth இன் காசோலைகள் பற்றிய பிற விவாதங்கள்

• Knuth இலிருந்து ஒரு காசோலையை எவ்வாறு பெறுவது

  நூத்தின் புத்தகங்களில் பிழைகளைக் கண்டறிவதற்கான பொதுவான பரிந்துரைகள். பெரும்பாலும் அவர்கள் தொழில்நுட்பப் பிழைகளைப் பற்றி கவலைப்படுகிறார்கள், அது என்னிடம் இல்லை. நான் தீவிரமாக எடுத்துக் கொண்ட ஒரு பரிந்துரை உள்ளது:

  சமர்ப்பிக்க வேண்டிய பிழைகளின் தொகுப்பைச் சேகரிக்கும் வரை காத்திருப்பது நல்லது. பல உண்மையான ஆனால் மிகவும் மதிப்புமிக்க பிழைகளை இணைப்பதன் மூலம், அவற்றில் ஒன்று உண்மையில் தவறு அல்லது ஆலோசனையாக கருதப்படுவதற்கான வாய்ப்பை அதிகரிக்கிறீர்கள். நீங்கள் ஒரு நேரத்தில் பிழைகளைச் சமர்ப்பித்தால், ஒவ்வொன்றும் தனித்தனியாக நிராகரிக்கப்படலாம்.

  நான் முட்டாள்தனமான எழுத்துப் பிழைகளை அனுப்ப விரும்பவில்லை, ஆனால் நான் மிகவும் தீவிரமானதாகத் தோன்றிய ஒரு வரலாற்றுப் பிழையைக் கண்டறிந்தபோதுதான் ஆலோசனையைப் பெற்று கடிதத்தை அனுப்பினேன்.

• அசுதோஷ் மெஹ்ராவின் காசோலைகள்

  அசுதோஷ் மெஹ்ரா, BoSS இல் 0x$207.f0 என்ற நிகர மதிப்புடன் சான் செரிஃபில் மூன்றாவது பணக்கார முதலீட்டாளர் ஆவார்.

• உண்மையான TeX குறியீட்டில் செயல்படாத சில பிழைகளைச் சரிபார்க்கவும்
• இதர: #1 #2 #3 #4 #5 #6

ஆதாரம்: www.habr.com