Дональд Кнут ал сунуш кылган китептеринин тактыгына абдан маани берген компьютердик илимпоз бир алты доллар ($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

Экинчи тамга катасы 4А томунун Комбинатордук алгоритмдер, 1-бөлүктө. 60-бетте куудулдардын ар кандай казинолордо ойношуна байланыштуу көйгөй сүрөттөлөт. Мисал катары чыныгы жашоодогу бир нече куудулдар келтирилген, алардын арасында Лили Томлин, Уерд Аль Янкович жана китеп жарык көргөндө тирүү болгон Робин Уильямс да бар. Кнут индексте ар дайым толук ысымдарды келтирет, ошондуктан Уильямс 882-бетте "Уильямс, Робин МакЛорим" деп көрсөтүлгөн. Бирок анын экинчи аты "м" эмес, "n" менен аяктайт, башкача айтканда, Маклаурин.

Маклаурин апасынын кыздык фамилиясы болгон. Ал Миссисипи штатынын 34-губернатору Ансельм Жозеф Маклауриндин чөбөрөсү болгон. Анын башкаруусу, кыязы, жакшы эч нерсе менен эсте калган жок. Китептен "Миссисипи: тарых":

«Маклориндин администрациясынын учурундагы эң маанилүү окуя 1898-жылдын жазында Америка Кошмо Штаттарынын Испанияга согуш жарыялоосу болду... Тилекке каршы, согуш кээ бир мамлекеттик кызматкерлерге паракорчулук менен алектенүүгө мүмкүнчүлүк берген болушу мүмкүн. Маклауринге ар кандай шектүү практикалар, анын ичинде тууганчылык жана ырайым кылуу ыйгарым укуктарын ашыкча пайдалануу үчүн айыпталган. Сабырдуулук кыймылынын жүрүшүндө сынчылар губернаторду аракеч деп айыптап, муну эл алдында мойнуна алды».

Тарыхый ката

кароо салттуу көбөйтүү алгоритми мектеп программасынан. Канча бир орундуу көбөйтүүнү талап кылат? Сиз көбөйдүңүз дейли - цифралык сан боюнча -бит . Алгач биринчи санды көбөйтүңүз ар бир сан үчүн кезеги менен. Андан кийин экинчи санды көбөйтүңүз ар бир сан үчүн бардык сандарды аралап өтмөйүнчө бирден жана башка . Ошентип, салттуу көбөйтүү талап кылынат примитивдүү көбөйтүү. Атап айтканда, эки санды көбөйтүү даражалар талап кылынат бир орундуу көбөйтүү.

Бул жаман, бирок советтик математик Анатолий Алексеевич Карацуба иштеп чыккан методду колдонуу менен процессти оптималдаштырууга болот. Келгиле, ошондой түр көрсөтөлү и  - эки орундуу ондук сандар; башкача айтканда сандар бар , , , ушундай и (бул алгоритмди чоңураак сандарга жалпылоо бир аз манипуляцияны талап кылат; бул өтө кыйын болбосо да, майда-чүйдөсүнө чейин ката кетирбөө үчүн, мен жөнөкөй мисалга жабышканым жакшы). Анда , , . биномдуктарды көбөйтүү берет . Учурда бизде дагы бар бир орундуу көбөйтүү: , , , . Эми кошуп жана кемителик . Окурман үчүн көнүгүү катары калтыра турган бир нече иретке келтирилгенден кийин, белгилүү болду  - үч гана бир орундуу көбөйтүү! (Кээ бир туруктуу коэффициенттер бар, бирок аларды сандарды кошуу жана жылдыруу менен гана эсептөөгө болот).

Далил сураба, бирок Карацуба алгоритми (Жогорудагы мисалдан рекурсивдүү жалпыланган) менен салттуу көбөйтүү ыкмасын жакшыртат чейин операциялар . Бул психикалык эсептөөлөрдү оптималдаштыруу эмес, алгоритмдин чыныгы өркүндөтүлүшү экенин эске алыңыз. Чынында эле, алгоритм менталдык арифметика үчүн ылайыктуу эмес, анткени ал рекурсивдүү операциялар үчүн чоң кошумча чыгымдарды талап кылат. Мындан тышкары, эффект сандар жетишерлик чоң болмоюнча өзүн толук көрсөтпөйт (бактыга жараша, Карацубанын алгоритми андан да тезирээк ыкмалар менен алмаштырылды: 2019-жылдын март айында алгоритм жарыяланган. n log n көбөйтүү; ылдамдатуу ойго келбеген чоң сандарга гана тиешелүү).

Бул алгоритм жарым-сандык алгоритмдердин 295-томунун XNUMX-бетинде сүрөттөлгөн. Ал жерде Кнут мындай деп жазат: «Бул идея бир гана жылы ачылганы кызык 1962 жыл», Карацубанын алгоритмин сүрөттөгөн макала жарыяланганда. Бирок! 1995-жылы Карацуба "Эсептөө татаалдыгы" деген макаласын жарыялаган, анда бир нече нерселер айтылат: 1) Болжол менен 1956-жылы Колмогоров көбөйтүүнү XNUMX-жылдан азыраак убакытта жасоого болбойт деп айткан. кадамдар; 2) ичинде 1960 жылы Карацуба семинарга катышып, Колмогоров n² гипотезасын сунуштаган. 3) «Туура бир жумада» Карацуба «бөлүп ал жана жең» алгоритмин иштеп чыкты; 4) 1962-жылы Колмогоров макала жазып, жарыялаган Карацубанын атынан алгоритмдин сүрөттөлүшү менен. "Мен бул макала жөнүндө кайра жарыялангандан кийин гана билдим."

Демек, ката анын ордуна 1962 белгилениши керек 1960 жыл. Баары болду.

талдоо

Каталарды табуу атайын чеберчиликти талап кылган эмес.

1. Биринчи ката мүмкүн болушунча майда-чүйдөсүнө чейин жана салыштырмалуу көрүнүктүү жерде болгон (бөлүмдүн башталышы). Кандайдыр бир келесоо таап алмак; Мен ошол акмак болуп чыктым.
2. Экинчи катаны табуу ийгиликти жана тырышчаактыкты талап кылды, бирок чеберчиликти талап кылбайт. "Уильямс" үчүн индекс томдун акыркы бетинде, китептин кыйла көрүнүктүү бөлүгү болуп саналат. Мен жөн гана индексти барактап жаттым (бул анчалык аянычтуу эмес, анткени Кнуттун индекстеринде Пасха жумурткалары катылган. Мисалы, арабча жана ивритче жазуулар бар, экөө тең 66-бетти көрсөтүп турат. Бирок ал баракта айтылган эмес. же тилдер; анын ордуна ал "оңдон солго окулуучу тилдерди" билдирет). Ал эми экинчи аты менин көңүлүмдү бурду. Мен адатта Википедияны окугандыктан Робин Уильямсты текшерип, дал келбестигин байкадым.
3. Тарыхый катаны табуу үчүн олуттуу изилдөө жүргүздүм деп айткым келет, бирок чындап эле карап койдум Карацубанын алгоритми жөнүндө Wikipedia баракчасы. Биринчи саптарда мындай деп айтылат: “Каратсуба алгоритми – бул тез көбөйтүү алгоритми. 1960-жылы Анатолий Карацуба тарабынан ачылган жана 1962-жылы жарык көргөн». Андан кийин эки жана эки кошуу гана калды.

Келечекте мен өзгөчө Кнуттун кодексинен олуттуураак ката тапкым келет. Мен ошондой эле Фундаменталдык Алгоритмдердин биринчи томунан ката тапкым келет. Балким, мен аны тапмакмын, бирок эмнегедир жергиликтүү китепканада 2, 3 жана 4А томдору гана бар.

Финансылык фактылар:

• Жалпысынан менин 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

Source: www.habr.com