ዶናልድ ክኑት ስለ መጽሐፎቹ ትክክለኛነት በጣም የሚያስብ የኮምፒዩተር ሳይንቲስት ነው አንድ ሄክስ ዶላር ($2,56፣ 0x$1,00) ለማንኛውም "ስህተት" ለተገኘ፣ ስህተቱ እንደ ማንኛውም ነገር "በቴክኒክ፣ በታሪክ፣ በፅሑፍ ወይም በፖለቲካዊ ትክክል ያልሆነ" ተብሎ ይገለጻል። ከKnuth ቼክ ለማግኘት በጣም እፈልግ ነበር፣ ስለዚህ በእሱ ማግኒየም ኦፕስ ውስጥ ስህተቶችን ለመፈለግ ወሰንኩ። "የፕሮግራሚንግ ጥበብ" (TAOCP) ሶስት ለማግኘት ችለናል። በቃሉ መሰረት፣ ክኑት ቼክ ላከ 0x$3,00.

እንደሚመለከቱት, ይህ ትክክለኛ ቼክ አይደለም. ክኑዝ እውነተኛ ቼኮችን ይልክ ነበር፣ ነገር ግን በ 2008 ምክንያት ቆሟል የተንሰራፋ ማጭበርበር. አሁን ወደ "የግል የተያዙ የምስክር ወረቀቶች" ይልካል የሳን ሰርሪፍ ባንክ (ቦኤስኤስ) አስፈላጊ ከሆነ እውነተኛ ገንዘብ ለመላክ ፈቃደኛ እንደሆነ ተናግሯል ነገር ግን በጣም ብዙ ችግር ያለበት ይመስላል።

ሁለት የትየባ እና አንድ ታሪካዊ ስህተት አግኝቻለሁ። ተራነትን በሚቀንስ ቅደም ተከተል እዘረዝራቸዋለሁ።

ዓይነት #1

የመጀመሪያው ትየባ በገጽ 392 በሦስተኛው ቅጽ "መደርደር እና ፍለጋ" ላይ ነው፣ ስምንተኛው መስመር ከሥሩ፡ "ያልተሳካ ፍለጋ አንዳንድ ጊዜ (አንዳንዴ) በሠንጠረዡ ውስጥ አዲስ መዝገብ ማስገባት ይፈለጋል። K; ይህን የሚያደርገው ዘዴ ፍለጋ እና አስገባ አልጎሪዝም ይባላል. ስህተቱ በምትኩ ነው። አንዳንድ ጊዜ መሆን አለበት አንዳንድ ጊዜ.

እርግጥ ነው, እንዲህ ዓይነቱ ስህተት አያስገርምም. በዚህ ጽሑፍ ውስጥ ብቻ ጥቂት የፊደል ስህተቶች መኖራቸው አይቀርም (እነሱን ለማግኘት ምንም ሽልማቶች የሉም)። በጣም የሚያስደንቀው ግን ለረጅም ጊዜ ሳይስተዋል መቆየቱ ነው። ገጽ 392 በሂሳብ ክፍል ውስጥ በጥልቅ አልተቀበረም። በጣም የመጀመሪያ ገጽ ምዕራፍ XNUMX "ፈልግ"! በጣም ከተነበቡ የመጽሐፉ ክፍሎች አንዱ ሊሆን ይችላል። በንድፈ ሀሳብ፣ በጣም ጥቂቶቹ የትየባዎች ሊኖሩ ይገባል፣ ግን አይሆንም።

በነገራችን ላይ፣ TAOCP ን ለማንበብ አስበህበት ከሆነ፣ ሞክር። ብዙዎች ይህ ነው ይላሉ ማውጫ, በቀጥታ ለማንበብ የታሰበ አይደለም, ግን ይህ እውነት አይደለም. ደራሲው ግልጽ የሆነ አመለካከት እና የተለየ ዘይቤ አለው. ተነባቢነትን የሚያደናቅፈው ብቸኛው ነገር የሂሳብ ውስብስብነት ነው። ነገር ግን፣ ቀላል መፍትሄ አለ፡ ወደ ሂሳብ እስክትመጣ ድረስ አንብብ፣ አልገባህም ይዝለል፣ እና ወደሚረዳህ ወደሚቀጥለው ክፍል ሂድ። በዚህ መንገድ ሳነብ ከመጽሐፉ ቢያንስ 80% ይናፍቀኛል፣ ሌላው 20% ግን በጣም ጥሩ ነው!

በተጨማሪም TAOCP ነው ተብሏል። አግባብነት የሌለው፣ ጊዜው ያለፈበት ነው ወይም በሌላ መልኩ ለ"እውነተኛ ፕሮግራሚንግ" ተፈጻሚ አይሆንም። ይህ ደግሞ እውነት አይደለም. ለምሳሌ፣ ከመግቢያው በኋላ ያለው የመጀመሪያው ክፍል ባልተደረደረ ድርድር ውስጥ ያለ ኤለመንት መፈለግን ይመለከታል። በጣም ቀላሉ አልጎሪዝም ለሁሉም ፕሮግራም አውጪዎች የታወቀ ነው። ጠቋሚውን በአደራደሩ መጀመሪያ ላይ ይጀምሩ፣ ከዚያ የሚከተለውን በአንድ ዙር ያድርጉ።

1. የአሁኑ ንጥረ ነገር የሚፈለገው መሆኑን ያረጋግጡ. ከሆነ, እንመልሰዋለን; አለበለዚያ
2. ጠቋሚው ከድርድር ወሰን ውጭ መሆኑን ያረጋግጡ። ከሆነ ስህተትን ይመልሱ; አለበለዚያ
3. አሳንስ እና ቀጥል

አሁን አስቡበት፡ ይህ ስልተ ቀመር በአማካይ ስንት የድንበር ፍተሻ ያስፈልገዋል? በጣም በከፋ ሁኔታ ፣ ድርድር አንድ አካል በሌለውበት ፣ በዝርዝሩ ውስጥ ያለው እያንዳንዱ አካል አንድ ቼክ ይፈልጋል ፣ እና በአማካይ አንድ ነገር ይሆናል . ይበልጥ ብልጥ የሆነ የፍለጋ ስልተ-ቀመር በአንድ የወሰን ፍተሻ ብቻ ሊጠፋ ይችላል። የተፈለገውን ኤለመንት ከድርድሩ መጨረሻ ጋር ያያይዙት፣ ከዚያ ጠቋሚውን በድርድር መጀመሪያ ላይ ይጀምሩ እና የሚከተለውን በ loop ያድርጉ።

1. የአሁኑ ንጥረ ነገር የሚፈለገው መሆኑን ያረጋግጡ. ከሆነ፣ ጠቋሚው በድርድር ውስጥ ከሆነ፣ ካልሆነም ስህተት ከሆነ ምላሽ እንመልሳለን። አለበለዚያ
2. አሳንስ እና ቀጥል

አንድ መንገድ ወይም ሌላ, ኤለመንቱ መገኘቱ የተረጋገጠ ነው, እና የድንበር ፍተሻ የሚከናወነው ይህ በሚሆንበት ጊዜ አንድ ጊዜ ብቻ ነው. ይህ ጥልቅ ሀሳብ ነው፣ ግን ለጀማሪ ፕሮግራመር እንኳን በቂ ቀላል ነው። ምናልባት ስለ ሥራው አስፈላጊነት ለሌሎች መናገር አልችልም ፣ ግን ወዲያውኑ ይህንን ጥበብ በግል እና በሙያዊ ኮድ ላይ ተግባራዊ ለማድረግ ቻልኩ። የTAOCP መጽሐፍ በእንደዚህ ዓይነት እንቁዎች የተሞላ ነው (ፍትሃዊ ለመሆን ፣ እዚያ ውስጥ ብዙ እንግዳ ነገሮችም አሉ ፣ ለምሳሌ የአረፋ መደርደር).

" ፈልግ ፣ ፈልግ
በጣም ረጅም
ይፈልጉ ፣ ይፈልጉ
መደነስ ፈልጌ ነበር"
- ሉተር ቫንድሮስ ፣ ፍለጋው (1980)

ዓይነት #2

ሁለተኛው ትየባ በጥራዝ 4A፣ Combinatorial Algorithms ክፍል 1 ላይ ነው።ገጽ 60 ኮሜዲያን በተለያዩ ካሲኖዎች ላይ እንዲሰሩ መርሐግብር ማስያዝ ላይ ያለውን ችግር ይገልጻል። ሊሊ ቶምሊን፣ ዊርድ አል ያንኮቪች እና ሮቢን ዊልያምስ መፅሃፉ ሲታተም በህይወት የነበረዉን ጨምሮ በርካታ የእውነተኛ ህይወት ኮሜዲያኖች ለአብነት ተጠቅሰዋል። ክኑት ሁል ጊዜ ሙሉ ስሞችን በመረጃ ጠቋሚው ውስጥ ይዘረዝራል፣ ስለዚህ ዊሊያምስ በገጽ 882 ላይ “ዊሊያምስ፣ ሮቢን ማክሎሪም” ተብሎ ተዘርዝሯል። ነገር ግን የእሱ መካከለኛ ስም በ "n" ያበቃል እና "m" አይደለም, ማለትም, McLaurin.

ማክላውሪን የእናቱ የመጀመሪያ ስም ነበር። እሷ የአንሰልም ጆሴፍ ማክላሪን የልጅ ልጅ ነበረች፣ 34ኛው የሚሲሲፒ ገዥ። የንግስና ንግስናው ምንም አይነት መልካም ነገር አልታሰበም ይመስላል። ከመጽሐፍ "ሚሲሲፒ: ታሪክ":

“በማክላውሪን አስተዳደር ወቅት በጣም አስፈላጊው ክስተት ዩናይትድ ስቴትስ በ1898 የጸደይ ወቅት በስፔን ላይ ጦርነት ማወጇ ነው... እንደ አለመታደል ሆኖ ጦርነቱ አንዳንድ የመንግስት ባለስልጣናት ጉቦ እንዲሰሩ እድል ሳይሰጥ አልቀረም። ማክላሪን በተለያዩ አጠራጣሪ ልማዶች ተከሷል፣ በዝምድና እና ከልክ ያለፈ የይቅርታ ስልጣኖችን መጠቀምን ጨምሮ። በንዴት እንቅስቃሴ ወቅት፣ ተቺዎች ገዥውን ሰካራም ነው ብለው ከሰሱት፣ እሱም በይፋ አምኗል።

ታሪካዊ ስህተት

እስቲ አስብ ባህላዊ ማባዛት አልጎሪዝም ከትምህርት ቤት ሥርዓተ-ትምህርት. ስንት ነጠላ አሃዝ ማባዛት ያስፈልገዋል? ተባዙ እንበል - አሃዝ ቁጥር ላይ - ቢት . መጀመሪያ የመጀመሪያውን አሃዝ ማባዛት። ለእያንዳንዱ አሃዝ አንድ በ አንድ. ከዚያ ሁለተኛውን አሃዝ ማባዛት። ለእያንዳንዱ አሃዝ ሁሉንም ቁጥሮች እስኪያልፍ ድረስ አንድ በአንድ እና ወዘተ . ስለዚህ ባህላዊ ማባዛት ይጠይቃል ጥንታዊ ብዜቶች. በተለይም ሁለት ቁጥሮችን በ ደረጃዎች ያስፈልጋል ነጠላ-አሃዝ ብዜቶች.

ይህ መጥፎ ነው, ነገር ግን በሶቪየት የሂሳብ ሊቅ አናቶሊ አሌክሼቪች ካራትሱባ የተሰራውን ዘዴ በመጠቀም ሂደቱን ማመቻቸት ይቻላል. እንደዚያ እናስመስለው и  - ባለ ሁለት አሃዝ አስርዮሽ ቁጥሮች; ቁጥሮች አሉ ማለት ነው። , , , ለምሳሌ и (ይህንን ስልተ ቀመር ወደ ትላልቅ ቁጥሮች ማጠቃለል የተወሰነ ማጭበርበርን ይጠይቃል፤ ምንም እንኳን በጣም ከባድ ባይሆንም በዝርዝሮቹ ላይ ስህተት ላለመሥራት እኔ በቀላል ምሳሌ ላይ እከተላለሁ።) ከዚያም , , . ሁለትዮሽ ማባዛት ይሰጣል . በአሁኑ ጊዜ አሁንም አለን። ነጠላ-አሃዝ ማባዛት; , , , . አሁን እንጨምር እና እንቀንስ . ለአንባቢ እንደ መልመጃ የምተወው ከጥቂት ማሻሻያዎች በኋላ፣ ተለወጠ  - ባለአንድ አሃዝ ማባዛት ሶስት ብቻ! (አንዳንድ ቋሚ ቅንጅቶች አሉ, ግን እነሱ ሊሰሉ የሚችሉት አሃዞችን በመጨመር እና በመቀየር ብቻ ነው).

ማስረጃ አትጠይቅ ግን Karatsuba ስልተ ቀመር (ከላይ ካለው ምሳሌ በተደጋጋሚ ጠቅለል ያለ) በባህላዊው የማባዛት ዘዴን ያሻሽላል ክወናዎች በፊት . እባክዎን ይህ የአልጎሪዝም ትክክለኛ መሻሻል እንጂ ለአእምሮ ስሌቶች ማመቻቸት እንዳልሆነ ልብ ይበሉ። በእርግጥም ስልተ ቀመር ለአእምሮ ሒሳብ ተስማሚ አይደለም፣ ምክንያቱም ለተደጋጋሚ ስራዎች ትልቅ ወጪ ይጠይቃል። በተጨማሪም ፣ ቁጥሩ በቂ እስኪሆን ድረስ ውጤቱ ሙሉ በሙሉ እራሱን አይገለጽም (እንደ እድል ሆኖ የካራትሱባ ስልተ ቀመር በፈጣን ዘዴዎች ተተክቷል-በማርች 2019 ፣ የሚያስፈልገው ስልተ ቀመር ታትሟል ። n log n ማባዛት; ማጣደፍ የማይታሰብ ትልቅ ቁጥሮች ላይ ብቻ ነው የሚሰራው)።

ይህ አልጎሪዝም በቅጽ 295፣ ከፊል-ቁጥር ስልተ ቀመሮች ገጽ XNUMX ላይ ተገልጿል:: እዛ ክኑዝ እንዲህ ሲሉ ጽፈዋል:- “ይህ ሃሳብ የተገኘው በ ውስጥ ብቻ መሆኑ ጉጉ ነው። 1962 ዓመት” የካራትሱባ ስልተ ቀመርን የሚገልጽ መጣጥፍ ሲወጣ። ግን! እ.ኤ.አ. በ 1995 ካራትሱባ ብዙ ነገሮችን የሚናገረውን "የስሌት ውስብስብነት" የሚል ወረቀት አሳተመ: 1) በ 1956 አካባቢ, ኮልሞጎሮቭ ማባዛት ባነሰ ጊዜ ውስጥ ሊከናወን አይችልም. ደረጃዎች; 2) ውስጥ 1960 ዓመት ካራትሱባ ኮልሞጎሮቭ መላምቱን n² ባቀረበበት ሴሚናር ላይ ተገኝቷል። 3) "በትክክል በአንድ ሳምንት ውስጥ" Karatsuba "መከፋፈል እና ማሸነፍ" ስልተ ቀመር አዘጋጅቷል; 4) በ 1962 ኮልሞጎሮቭ አንድ ጽሑፍ ጻፈ እና አሳተመ በካራትሱባ ስም ከአልጎሪዝም መግለጫ ጋር. "ስለዚህ ጽሑፍ ያወቅኩት እንደገና ከታተመ በኋላ ነው።"

ስለዚህ ስህተቱ በምትኩ ነው። 1962 የሚለው መገለጽ አለበት። 1960 አመት. ይኼው ነው.

ትንታኔ

ስህተቶችን መፈለግ ልዩ ችሎታ አያስፈልገውም.

1. የመጀመሪያው ስህተት በተቻለ መጠን ቀላል እና በአንፃራዊነት በሚታየው ቦታ (የምዕራፉ መጀመሪያ) ላይ ነበር. ማንኛውም ሞኝ ባገኘው ነበር; አሁን ያ ደደብ ሆኜ ተገኘሁ።
2. ሁለተኛውን የትየባ ማግኘት ዕድል እና ትጋት ይጠይቃል፣ነገር ግን ችሎታ አይደለም። የ"ዊልያምስ" መረጃ ጠቋሚ በመጽሐፉ ውስጥ በጣም ታዋቂ በሆነው የጥራዙ ገጽ ላይ ነው። ኢንዴክስን እያገላበጥኩ ነበር (የሚመስለውን ያህል የሚያሳዝን አይደለም፣ ምክንያቱም በክኑት ኢንዴክሶች ውስጥ የተደበቁ የትንሳኤ እንቁላሎች አሉ። ለምሳሌ በአረብኛ እና በዕብራይስጥ ቋንቋዎች የገቡ ናቸው ሁለቱም ወደ ገጽ 66 ያመለክታሉ። ግን ያ ገጽ አልጠቀሰም። የትኛውም ቋንቋዎች፤ ይልቁንም “ከቀኝ ወደ ግራ የሚነበቡ ቋንቋዎችን” ያመለክታል። እና ሁለተኛው ስም ትኩረቴን ሳበው። ብዙ ጊዜ ዊኪፔዲያን ስለማነብ ሮቢን ዊልያምስን ፈትጬዋለሁ ​​እና ልዩነት እንዳለ አስተዋልኩ።
3. ታሪካዊ ስህተትን ለማግኘት ጠንከር ያለ ጥናት አድርጌያለሁ ማለትን እመኛለሁ፣ ግን በእውነት ዝም ብዬ ተመለከትኩ። ስለ Karatsuba ስልተ ቀመር የዊኪፔዲያ ገጽ. የመጀመሪያዎቹ መስመሮች እንዲህ ይላሉ፡- “የካራትሱባ ስልተ ቀመር ፈጣን የማባዛት ስልተ-ቀመር ነው። በ 1960 በአናቶሊ ካራትሱባ የተገኘ እና በ 1962 የታተመ። ከዚያ በኋላ የቀረው ሁለት እና ሁለት መጨመር ብቻ ነበር.

ወደፊት በተለይ በKnuth's ኮድ ውስጥ የበለጠ ጉልህ የሆነ ስህተት ማግኘት እፈልጋለሁ። በመሠረታዊ ስልተ ቀመሮች የመጀመሪያ ጥራዝ ላይም ስህተት ማግኘት እፈልጋለሁ። ምናልባት ባገኘው ነበር፣ ግን በሆነ ምክንያት የአካባቢው ቤተ-መጽሐፍት ጥራዞች 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

ምንጭ: hab.com