Дональд Кнут өөрийн санал болгож буй номнуудынхаа үнэн зөвийг маш их анхаардаг компьютерийн эрдэмтэн юм нэг зургаан доллар ($2,56, 0x$1,00) олдсон аливаа "алдаа"-д алдаа нь "техникийн, түүх, хэвлэмэл, улс төрийн хувьд алдаатай" аливаа зүйлийг хэлнэ. Би Кнутаас чек авахыг маш их хүсч байсан тул түүний магнум зохиолын алдааг хайхаар шийдсэн "Програмчлалын урлаг" (TAOCP). Бид гурвыг нь олж чадсан. Хэлсэн үгэндээ үнэнч Кнут чек илгээв 0х $3,00.
Таны харж байгаагаар энэ бол жинхэнэ шалгалт биш юм. Кнут бодит чек илгээдэг байсан ч 2008 онд зогссон . Тэр одоо "хувийн хадгаламжийн гэрчилгээ" илгээдэг (BoSS). Тэрээр шаардлагатай бол бодит мөнгө явуулахад бэлэн гэдгээ хэлсэн ч энэ нь хэтэрхий төвөг учруулсан юм шиг санагдаж байна.
Би хоёр үсгийн алдаа, нэг түүхэн алдаа олсон. Би тэдгээрийг үл тоомсорлохыг багасгах дарааллаар жагсаах болно.
Үсгийн алдаа №1
Эхний үсгийн алдаа нь "Ангилах ба хайх" номын 392-р ботийн XNUMX-р хуудсанд, доод талаас найм дахь мөрөнд: "Амжилтгүй хайсны дараа заримдаа (заримдаа) хүснэгтэд шинэ бичлэг оруулах нь зүйтэй. K; Үүнийг хийх аргыг хайлт ба оруулах алгоритм гэж нэрлэдэг. Үүний оронд алдаа байгаа юм заримдаа байх ёстой заримдаа.
Мэдээжийн хэрэг, ийм алдаа нь гайхмаар зүйл биш юм. Зөвхөн энэ нийтлэлд цөөн хэдэн үсгийн алдаа байх нь гарцаагүй (түүнийг олоход шагналгүй). Гайхалтай нь энэ нь удаан хугацаанд анзаарагдахгүй байсан явдал юм. 392-р хуудас нь математикийн хэсэгт гүн оршуулсангүй, тийм хамгийн эхний хуудас 6-р бүлэг "Хайлт"! Номын хамгийн их уншдаг хэсгүүдийн нэг байж магадгүй. Онолын хувьд хамгийн бага үсгийн алдаа байх ёстой, гэхдээ үгүй.
Дашрамд хэлэхэд, хэрэв та хэзээ нэгэн цагт TAOCP унших талаар бодож байсан бол үзээрэй. Үүнийг олон хүн хэлэх болно лавлах, шууд уншихад зориулагдаагүй, гэхдээ энэ нь үнэн биш юм. Зохиогч нь тодорхой үзэл бодолтой, өвөрмөц хэв маягтай. Уншихад саад болж буй цорын ганц зүйл бол математикийн нарийн төвөгтэй байдал юм. Гэсэн хэдий ч энгийн шийдэл байдаг: та ойлгохгүй байгаа математикийн хичээлдээ орох хүртлээ уншаад алгасаад дараагийн ойлгох хэсэг рүү оч. Ингэж уншихад би номынхоо 80% -ийг санаж байна, харин үлдсэн 20% нь үнэхээр гайхалтай!
Мөн TAOCP гэж ярьдаг хамааралгүй, хуучирсан эсвэл "бодит програмчлалд" хамаарахгүй. Энэ нь бас үнэн биш юм. Жишээлбэл, танилцуулгын дараах эхний хэсэг нь эрэмблэгдээгүй массив дахь элементийг олохыг хардаг. Хамгийн энгийн алгоритм нь бүх програмистуудад танил юм. Заагчийг массивын эхнээс эхлүүлж, дараа нь давталтаар дараахь зүйлийг хий.
- Одоогийн элемент нь хүссэн зүйл мөн эсэхийг шалгана уу. Хэрэв тийм бол бид буцааж өгнө; өөрөөр
- Заагч нь массивын хилийн гадна байгаа эсэхийг шалгана уу. Хэрэв тийм бол алдаа буцаана; өөрөөр
- Томруулж, үргэлжлүүлнэ үү.
Одоо бодоод үз: энэ алгоритм дунджаар хэдэн хязгаарын шалгалт шаарддаг вэ? Хамгийн муу тохиолдолд, массив нь элемент агуулаагүй тохиолдолд жагсаалтын элемент бүр нэг шалгалтыг шаарддаг бөгөөд дунджаар энэ нь дараах байдалтай байх болно. 
. Ухаалаг хайлтын алгоритм нь зөвхөн нэг хязгаарыг шалгахаас зайлсхийх боломжтой. Хүссэн элементээ массивын төгсгөлд хавсаргаж, дараа нь массивын эхэнд заагчийг эхлүүлж, гогцоонд дараахь зүйлийг хийнэ.
- Одоогийн элемент нь хүссэн зүйл мөн эсэхийг шалгана уу. Хэрэв тийм бол заагч массив дотор байвал хариу, байхгүй бол алдаа буцаана. Үгүй бол
- Томруулж, үргэлжлүүлнэ үү.
Ямар нэг байдлаар элемент олдох нь баталгаатай бөгөөд энэ нь тохиолдсон тохиолдолд хил хязгаарыг шалгах нь зөвхөн нэг удаа хийгддэг. Энэ бол гүн гүнзгий санаа боловч шинэхэн програмистад ч хангалттай энгийн зүйл юм. Би уг бүтээлийг бусдад хамаатай гэж хэлж чадахгүй байх, гэхдээ би энэ мэргэн ухааныг хувийн болон мэргэжлийн кодонд шууд хэрэглэж чадсан. TAOCP ном ийм эрдэнийн чулуугаар дүүрэн байдаг (шударга хэлэхэд тэнд бас олон хачирхалтай зүйлс байдаг. ).
"Хайл, хай
Тийм удаан
Хайх, хайх
Би зүгээр л бүжиглэхийг хүссэн"
- Лютер Вандрос, "Хайлт" (1980)
Үсгийн алдаа №2
Хоёрдахь үсгийн алдаа нь 4А боть, Комбинаторийн алгоритмууд, 1-р хэсэг. 60-р хуудсанд хошин урлагийн жүжигчдийг янз бүрийн казинод тоглох хуваарь гаргахтай холбоотой асуудлыг тайлбарласан болно. Ном хэвлэгдэх үед амьд сэрүүн байсан Лили Томлин, Хачирхалтай Аль Янкович, Робин Уильямс зэрэг хэд хэдэн бодит инээдмийн жүжигчдийг жишээ болгон дурджээ. Кнут индекст дандаа бүтэн нэрийг бичдэг тул Уильямсыг 882-р хуудсанд "Уильямс, Робин Маклорим" гэж бичжээ. Гэхдээ түүний дунд нэр нь "m" биш харин "n" гэсэн үсгээр төгсдөг, өөрөөр хэлбэл Маклаурин.
Маклаурин бол ээжийнх нь анхны нэр юм. Тэрээр Миссисипи мужийн 34 дэх амбан захирагч Ансельм Жозеф Маклаурины ач охин байв. Түүний хаанчлал нь ямар ч сайн зүйлээр дурсаагүй бололтой. Номоос :
“Маклаурины засаг захиргааны үеийн хамгийн чухал үйл явдал бол 1898 оны хавар АНУ Испанид дайн зарласан явдал байв... Харамсалтай нь дайн төрийн зарим албан тушаалтнуудад хээл хахууль авах боломжийг олгосон байж магадгүй. МакЛауриныг хамаатан садан, өршөөлийн эрх мэдлийг хэтрүүлэн ашигласан гэх мэт янз бүрийн эргэлзээтэй үйлдэлд буруутгаж байсан. Даруу байдлын хөдөлгөөний үеэр шүүмжлэгчид засаг даргыг архичин гэж буруутгаж, олон нийтэд хүлээн зөвшөөрсөн."
Түүхэн алдаа
Санаа зов уламжлалт үржүүлэх алгоритм сургуулийн сургалтын хөтөлбөрөөс. Хэдэн нэг оронтой тоог үржүүлэх шаардлагатай вэ? Та үржлээ гэж бодъё 
- оронтой тоо 
тухай 
- бит 
. Эхлээд эхний цифрийг үржүүлнэ 
цифр бүрийн хувьд 
нэг нэгээр нь. Дараа нь хоёр дахь цифрийг үржүүлнэ 
цифр бүрийн хувьд 
нэг нэгээр нь гэх мэтээр бүх тоог давтлаа 
. Тиймээс уламжлалт үржүүлэх шаардлагатай 
анхдагч үржүүлэх. Ялангуяа хоёр тоог үржүүлэх 
шаардлагатай зэрэглэл 
нэг оронтой үржвэр.
Энэ нь муу, гэхдээ Зөвлөлтийн математикч Анатолий Алексеевич Карацубагийн боловсруулсан аргыг ашиглан үйл явцыг оновчтой болгох боломжтой юм. Ингэж жүжиглэе 
и 
- хоёр оронтой аравтын тоо; өөрөөр хэлбэл тоо байдаг 
, 
, 
, 
тиймэрхүү 
и 
(энэ алгоритмыг илүү том тоо болгон нэгтгэх нь зарим зохицуулалтыг шаарддаг; энэ нь тийм ч хэцүү биш боловч нарийн ширийн зүйлд алдаа гаргахгүйн тулд би энгийн жишээг баримтлах нь дээр). Дараа нь 
, 
, 
. Хоёр гишүүнийг үржүүлэх нь өгөгддөг 
. Одоогоор бидэнд байгаа 
нэг оронтой тоогоор үржүүлэх: 
, 
, 
, 
. Одоо нэмээд хасъя 
. Уншигчдад дасгал болгон үлдээх хэд хэдэн зохицуулалт хийсний дараа энэ нь болж байна 
- зөвхөн гурван нэг оронтой үржвэр! (Зарим тогтмол коэффициентүүд байдаг, гэхдээ тэдгээрийг зөвхөн цифрүүдийг нэмж, шилжүүлэх замаар тооцоолж болно).
Нотлох баримт бүү асуу, гэхдээ Карацуба алгоритм (дээрх жишээнээс рекурсив ерөнхийлсөн) нь уламжлалт үржүүлэх аргыг сайжруулдаг 
өмнөх үйл ажиллагаа 
. Энэ нь алгоритмын бодит сайжруулалт болохоос оюун ухааны тооцооллын оновчлол биш гэдгийг анхаарна уу. Үнэн хэрэгтээ, алгоритм нь рекурсив үйлдлүүдэд их хэмжээний нэмэлт зардал шаарддаг тул сэтгэцийн арифметикийн хувьд тохиромжгүй байдаг. Нэмж дурдахад, тоонууд хангалттай том болтол үр нөлөө нь бүрэн харагдахгүй (аз болоход Карацүбагийн алгоритм нь илүү хурдан аргуудаар солигдсон: 2019 оны XNUMX-р сард зөвхөн алгоритмыг шаарддаг алгоритм хэвлэгджээ. үржүүлэх; хурдатгал нь зөвхөн төсөөлшгүй их тоонд хамаарна).
Энэ алгоритмыг Хагас тоон алгоритмуудын 295-р ботийн XNUMX-р хуудсанд тайлбарласан болно. Тэнд Кнут бичжээ: "Энэ санааг зөвхөн онд л олж мэдсэн нь сонин юм 1962 жил" гэж Карацүбагийн алгоритмыг дүрсэлсэн нийтлэл хэвлэгдсэн. Гэхдээ! 1995 онд Карацуба "Тооцооллын нарийн төвөгтэй байдал" хэмээх нийтлэлээ хэвлүүлсэн бөгөөд үүнд хэд хэдэн зүйлийг дурдсан байдаг: 1) 1956 онд Колмогоров үржүүлэх үйлдлийг XNUMX-ээс бага хугацаанд хийх боломжгүй гэж санал болгосон. 
алхамууд; 2) дотор 1960 жил Карацуба семинарт оролцож, Колмогоров n² таамаглал дэвшүүлсэн. 3) "Яг нэг долоо хоногийн дотор" Карацуба "хувааж, ялах" алгоритмыг боловсруулсан; 4) 1962 онд Колмогоров нийтлэл бичиж хэвлүүлсэн Карацубагийн нэрийн өмнөөс алгоритмын тайлбартай. "Би энэ нийтлэлийг дахин хэвлэгдсэний дараа л мэдсэн."
Тиймээс алдаа нь оронд нь байна 1962 заасан байх ёстой 1960 жил. Тэгээд л болоо.
Анализ
Алдаа хайх нь тусгай ур чадвар шаарддаггүй.
- Эхний алдаа нь аль болох өчүүхэн байсан бөгөөд харьцангуй харагдахуйц газар байсан (бүлгийн эхлэл). Ямар ч тэнэг хүн үүнийг олох байсан; Би зүгээр л тэр тэнэг болж хувирсан.
- Хоёрдахь үсгийн алдааг олоход аз, хичээл зүтгэл шаардагддаг байсан ч ур чадвар биш байв. "Уильямс"-ын индекс нь номын нэлээн алдартай хэсэг болох ботийн сүүлчийн хуудсанд байна. Би зүгээр л индексийг эргүүлж байлаа (энэ нь тийм ч өрөвдмөөр сонсогдохгүй байна, учир нь Кнутын индекст Улаан өндөгний баярын өндөг нуугдаж байгаа. Жишээ нь, араб, еврей хэл дээрх оруулгууд хоёулаа 66-р хуудсыг зааж байна. Гэхдээ тэр хуудсанд энэ талаар дурдаагүй байна. аль ч хэл; оронд нь энэ нь "баруунаас зүүн тийш уншдаг хэл" гэсэн утгатай). Хоёр дахь нэр нь миний анхаарлыг татсан. Би ихэвчлэн Википедиа уншдаг болохоор Робин Уильямсыг шалгаж үзээд зөрүү анзаарсан.
- Би түүхэн алдаа олохын тулд нухацтай судалгаа хийсэн гэж хэлэхийг хүсч байна, гэхдээ би зүгээр л харлаа . Эхний мөрөнд: "Каратсуба алгоритм нь хурдан үржүүлэх алгоритм юм. 1960 онд Анатолий Карацуба нээж, 1962 онд хэвлүүлсэн." Үүний дараа хоёр, хоёрыг нэмэх л үлдлээ.
Ирээдүйд би илүү чухал алдаа, ялангуяа Кнутын кодыг олохыг хүсч байна. Би мөн үндсэн алгоритмуудын эхний ботид алдаа олж мэдмээр байна. Магадгүй би үүнийг олох байсан, гэхдээ яагаад ч юм орон нутгийн номын санд зөвхөн 2, 3, 4А боть байдаг.
Санхүүгийн баримтууд:
- Нийтдээ миний TAOCP-д оруулсан хувь нэмэр ердөө гурван тэмдэгтээс бүрддэг: нэг нэмэлт s, солих m тухай n и 2 тухай 0. 2,56 доллараар эдгээр нь нэлээд ашигтай тэмдэг юм; Хэрэв танд ийм хэмжээний мөнгө төлсөн бол 1000 үгтэй (дунджаар дөрвөн тэмдэгт) нийтлэл танд арван грандын орлого олох байсан.
- Гурван арван арван доллараар би бусад 29 иргэний хамт Сан Серриф банкны хамгийн баян хадгаламж эзэмшигчдийн жагсаалтын 69-р байрт бичигдэж байна (1 оны 2019-р сарын XNUMX-ний байдлаар).
Knuth-ийн чекүүдийн талаархи бусад хэлэлцүүлэг
Кнутын номнуудаас алдаа олох ерөнхий зөвлөмжүүд. Ихэнхдээ тэд техникийн алдаатай холбоотой байдаг бөгөөд энэ нь надад байхгүй. Би нухацтай авч үзсэн нэг санал байна:
Илгээх алдааны багцыг цуглуулах хүртэл хүлээх нь дээр. Хэд хэдэн бодит боловч тийм ч үнэ цэнэтэй биш алдаануудыг нэгтгэснээр та тэдгээрийн аль нэгийг нь алдаа эсвэл зөвлөгөө гэж үзэх магадлалыг нэмэгдүүлдэг. Хэрэв та алдааг нэг нэгээр нь оруулбал тус бүрээс татгалзаж болно.
Би зүгээр л утгагүй үсгийн алдаа илгээхийг хүсээгүй, гэхдээ хангалттай ноцтой санагдсан түүхэн алдааг олж мэдсэнийхээ дараа л зөвлөгөө авч, захидал илгээсэн.
Ашутош Мехра бол BoSS дахь 0x207.f0 долларын цэвэр хөрөнгөтэй Сан Серрифийн гурав дахь хамгийн баян хөрөнгө оруулагч юм.
- Бусад зүйл:
Эх сурвалж: www.habr.com
