დონალდ კნუტი არის კომპიუტერული მეცნიერი, რომელიც იმდენად ზრუნავს თავისი წიგნების სიზუსტეზე, რომ ის ვარაუდობს ერთი ექვსკუთხედი დოლარი ($2,56, 0x$1,00) ნებისმიერი ნაპოვნი „შეცდომისთვის“, სადაც შეცდომა განისაზღვრება, როგორც ყველაფერი, რაც არის „ტექნიკურად, ისტორიულად, ტიპოგრაფიულად ან პოლიტიკურად არასწორი“. მე ძალიან მინდოდა კნუტისგან ჩეკის მიღება, ამიტომ გადავწყვიტე მის მაგნუმ ოპუსში შემესწავლა შეცდომები "პროგრამირების ხელოვნება" (TAOCP). სამის პოვნა მოვახერხეთ. თავისი სიტყვის დაცვით კნუტმა ჩეკი გაუგზავნა 0x3,00$.

როგორც ხედავთ, ეს არ არის რეალური შემოწმება. კნუტი რეალურ ჩეკებს აგზავნიდა, მაგრამ 2008 წელს შეწყვიტა ამის გამო ყოვლისმომცველი თაღლითობა. ის ახლა აგზავნის "პირად სადეპოზიტო სერთიფიკატებს". სან-სერიფის ბანკი (BoSS). ის ამბობს, რომ მზადაა საჭიროების შემთხვევაში რეალური ფული გამოაგზავნოს, მაგრამ, როგორც ჩანს, ეს ძალიან რთულია.

აღმოვაჩინე ორი შეცდომა და ერთი ისტორიული შეცდომა. ჩამოვთვლი მათ ტრივიალურობის შემცირების მიზნით.

ტიპიური შეცდომა #1

პირველი შეცდომა არის „დახარისხება და ძიება“ მესამე ტომის 392-ე გვერდზე, მერვე სტრიქონი ქვემოდან: „წარუმატებელი ძიების შემდეგ, ზოგჯერ (ზოგჯერ) სასურველია შეიტანოთ ახალი ჩანაწერი ცხრილში, რომელიც შეიცავს K; მეთოდს, რომელიც ამას აკეთებს, ეწოდება ძებნისა და ჩასმის ალგორითმი. შეცდომა ის არის, რომ სამაგიეროდ შუალედში უნდა იყოს ზოგჯერ.

რა თქმა უნდა, ასეთი შეცდომა არ არის გასაკვირი. ამ სტატიაში აუცილებლად იქნება რამდენიმე შეცდომა (მათი პოვნისთვის ჯილდო არ არის). რაც ნამდვილად გასაკვირია, ის არის, რომ ამდენი ხნის განმავლობაში შეუმჩნეველი დარჩა. გვერდი 392 ღრმად არ არის ჩაფლული მათემატიკის განყოფილებაში პირველივე გვერდი თავი XNUMX "ძებნა"! შესაძლოა წიგნის ერთ-ერთი ყველაზე წაკითხული ნაწილი. თეორიულად, ყველაზე ცოტა შეცდომა უნდა იყოს, მაგრამ არა.

სხვათა შორის, თუ ოდესმე გიფიქრიათ TAOCP-ის კითხვაზე, სცადეთ. ბევრი იტყვის, რომ ეს ასეა დირექტორია, არ არის განკუთვნილი პირდაპირი კითხვისთვის, მაგრამ ეს ასე არ არის. ავტორს აქვს მკაფიო თვალსაზრისი და გამორჩეული სტილი. ერთადერთი, რაც აფერხებს წაკითხვას, არის მათემატიკის სირთულე. თუმცა, არსებობს მარტივი გამოსავალი: წაიკითხეთ, სანამ მათემატიკას არ მიაღწევთ, რაც არ გესმით, გამოტოვეთ და გადადით შემდეგ განყოფილებაში, რომლის გაგებაც შეგიძლიათ. ასე რომ ვკითხულობ, წიგნის მინიმუმ 80% მენატრება, მაგრამ დანარჩენი 20% მშვენიერია!

ასევე ნათქვამია, რომ TAOCP შეუსაბამო, მოძველებულია ან სხვაგვარად არ გამოიყენება "რეალურ პროგრამირებაზე". ეს ასევე არ შეესაბამება სიმართლეს. მაგალითად, შესავლის შემდეგ პირველი სექცია განიხილავს ელემენტის პოვნას დაუხარისხებელ მასივში. უმარტივესი ალგორითმი ყველა პროგრამისტისთვის ნაცნობია. დაიწყეთ მაჩვენებელი მასივის დასაწყისში, შემდეგ გააკეთეთ შემდეგი:

1. შეამოწმეთ არის თუ არა მიმდინარე ელემენტი სასურველი. თუ ასეა, ჩვენ მას ვუბრუნებთ; წინააღმდეგ შემთხვევაში
2. შეამოწმეთ არის თუ არა მაჩვენებელი მასივის საზღვრებს გარეთ. თუ ასეა, დააბრუნეთ შეცდომა; წინააღმდეგ შემთხვევაში
3. გაადიდეთ და გააგრძელეთ.

ახლა განიხილეთ: რამდენ საზღვრების შემოწმებას მოითხოვს ეს ალგორითმი, საშუალოდ? უარეს შემთხვევაში, როდესაც მასივი არ შეიცავს ელემენტს, სიის თითოეულ ელემენტს დასჭირდება ერთი შემოწმება და საშუალოდ ეს იქნება რაღაც მსგავსი . უფრო ჭკვიანური ძიების ალგორითმი შეიძლება მოშორდეს საზღვრების მხოლოდ ერთი შემოწმებით. მიამაგრეთ სასურველი ელემენტი მასივის ბოლოს, შემდეგ დაიწყეთ მაჩვენებელი მასივის დასაწყისში და გააკეთეთ შემდეგი ციკლში:

1. შეამოწმეთ არის თუ არა მიმდინარე ელემენტი სასურველი. თუ ასეა, ჩვენ ვაბრუნებთ პასუხს, თუ მაჩვენებელი არის მასივის შიგნით, ან შეცდომას, თუ ის არ არის. წინააღმდეგ შემთხვევაში
2. გაადიდეთ და გააგრძელეთ.

ასეა თუ ისე, ელემენტის პოვნა გარანტირებულია და საზღვრების შემოწმება ხდება მხოლოდ ერთხელ, როცა ეს მოხდება. ეს ღრმა იდეაა, მაგრამ საკმარისად მარტივია თუნდაც დამწყები პროგრამისტისთვის. მე ალბათ ვერ ვისაუბრებ ნაწარმოების აქტუალობაზე სხვებისთვის, მაგრამ მაშინვე შევძელი ამ სიბრძნის გამოყენება როგორც პირად, ისე პროფესიულ კოდებში. TAOCP წიგნი სავსეა ასეთი ძვირფასი ქვებით (სამართლიანად რომ ვთქვათ, იქ ასევე ბევრი უცნაური რამ არის, მაგ. ბუშტის დალაგება).

"ძებნა, ძებნა
Ამდენი ხანი
ძებნა, ძიება
უბრალოდ ცეკვა მინდოდა"
- ლუთერ ვანდროსი, "ძებნა" (1980)

ტიპიური შეცდომა #2

მეორე შეცდომა არის ტომში 4A, კომბინატორული ალგორითმები, ნაწილი 1. გვერდი 60 აღწერს პრობლემას, რომელიც მოიცავს კომიკოსების დაგეგმვას სხვადასხვა კაზინოში შესასრულებლად. მაგალითად მოყვანილია რამდენიმე რეალური კომიკოსი, მათ შორის ლილი ტომლინი, უცნაური ალ იანკოვიჩი და რობინ უილიამსი, რომელიც ჯერ კიდევ ცოცხალი იყო წიგნის გამოქვეყნებისას. კნუტი ყოველთვის ასახელებს სრულ სახელებს ინდექსში, ამიტომ უილიამსი 882-ე გვერდზეა ჩამოთვლილი, როგორც "უილიამსი, რობინ მაკლორიმი". მაგრამ მისი შუა სახელი მთავრდება "n"-ით და არა "m", ანუ მაკლორინი.

მაკლორინი დედის ქალიშვილობის გვარი იყო. ის იყო მისისიპის 34-ე გუბერნატორის ანსელმ ჯოზეფ მაკლორინის შვილიშვილი. მისი მეფობა, როგორც ჩანს, კარგი არაფერი ახსოვდათ. წიგნიდან "მისსიპი: ისტორია":

„ყველაზე მნიშვნელოვანი მოვლენა მაკლორინის ადმინისტრაციის დროს იყო შეერთებული შტატების მიერ ესპანეთისთვის ომის გამოცხადება 1898 წლის გაზაფხულზე... სამწუხაროდ, ომმა შესაძლოა ზოგიერთ სამთავრობო მოხელეს მისცა მექრთამეობაში ჩართვის შესაძლებლობა. მაკლორინს ბრალი ედებოდა სხვადასხვა საეჭვო პრაქტიკაში, მათ შორის ნეპოტიზმსა და შეწყალების უფლებამოსილების გადამეტებულ გამოყენებაში. ზომიერების მოძრაობის დროს კრიტიკოსები გუბერნატორს მთვრალობაში ადანაშაულებდნენ, რაც მან საჯაროდ აღიარა“.

ისტორიული შეცდომა

განვიხილოთ ტრადიციული გამრავლების ალგორითმი სკოლის სასწავლო გეგმიდან. რამდენ ერთნიშნა გამრავლებას მოითხოვს? დავუშვათ, გამრავლდით - ციფრი ნომერი on - ცოტა . ჯერ გაამრავლეთ პირველი ციფრი თითოეული ციფრისთვის სათითაოდ. შემდეგ გაამრავლეთ მეორე ციფრი თითოეული ციფრისთვის სათითაოდ და ასე შემდეგ, სანამ არ გაივლით ყველა რიცხვს . ამიტომ ტრადიციული გამრავლება მოითხოვს პრიმიტიული გამრავლებები. კერძოდ, ორი რიცხვის გამრავლება საჭიროა წოდებები ერთნიშნა გამრავლება.

ეს ცუდია, მაგრამ პროცესის ოპტიმიზაცია შესაძლებელია საბჭოთა მათემატიკოსის ანატოლი ალექსეევიჩ კარაცუბას მიერ შემუშავებული მეთოდის გამოყენებით. მოდი ვიჩვენოთ, რომ и  - ორნიშნა ათობითი რიცხვები; ანუ არის რიცხვები , , , ისეთივე როგორც и (ამ ალგორითმის უფრო დიდ რიცხვებამდე განზოგადება მოითხოვს გარკვეულ მანიპულირებას; თუმცა არც ისე რთულია, დეტალებში შეცდომები რომ არ დავუშვათ, ჯობია მარტივ მაგალითს მივყვები). მერე , , . ორომალიების გამრავლება იძლევა . ამ მომენტში ჯერ კიდევ გვაქვს ერთნიშნა გამრავლება: , , , . ახლა დავამატოთ და გამოვაკლოთ . რამდენიმე გადაწყობის შემდეგ, რომელსაც მკითხველისთვის სავარჯიშოდ დავტოვებ, თურმე  - მხოლოდ სამი ერთნიშნა გამრავლება! (არსებობს მუდმივი კოეფიციენტები, მაგრამ მათი გამოთვლა შესაძლებელია მხოლოდ ციფრების მიმატებით და გადაადგილებით).

ნუ გთხოვ მტკიცებულებას, მაგრამ კარაცუბას ალგორითმი (რეკურსიულად განზოგადებული ზემოთ მოყვანილი მაგალითიდან) აუმჯობესებს გამრავლების ტრადიციულ მეთოდს ოპერაციები ადრე . გთხოვთ გაითვალისწინოთ, რომ ეს არის ალგორითმის რეალური გაუმჯობესება და არა გონებრივი გამოთვლების ოპტიმიზაცია. მართლაც, ალგორითმი არ არის შესაფერისი გონებრივი არითმეტიკისთვის, რადგან ის მოითხოვს დიდ ხარჯებს რეკურსიული ოპერაციებისთვის. გარდა ამისა, ეფექტი სრულად არ გამოვლინდება მანამ, სანამ რიცხვები საკმარისად დიდი გახდება (საბედნიეროდ, კარაცუბას ალგორითმი შეიცვალა კიდევ უფრო სწრაფი მეთოდებით: 2019 წლის მარტში გამოქვეყნდა ალგორითმი, რომელიც მოითხოვს მხოლოდ n ჟურნალი n გამრავლება; აჩქარება ეხება მხოლოდ წარმოუდგენლად დიდ რიცხვებს).

ეს ალგორითმი აღწერილია მე-295 ტომის XNUMX-ე გვერდზე, ნახევრად რიცხვითი ალგორითმები. იქ კნუტი წერს: „საინტერესოა, რომ ეს იდეა მხოლოდ ქ 1962 წელი“, როდესაც გამოქვეყნდა სტატია, რომელიც აღწერს კარაცუბას ალგორითმს. მაგრამ! 1995 წელს კარაცუბამ გამოაქვეყნა ნაშრომი "გამოთვლითი სირთულე", რომელშიც ნათქვამია რამდენიმე რამ: 1) დაახლოებით 1956 წელს კოლმოგოროვი ვარაუდობს, რომ გამრავლება არ შეიძლება განხორციელდეს ნაკლებ დროში. ნაბიჯები; 2) in 1960 წელი კარაცუბა დაესწრო სემინარს, სადაც კოლმოგოროვმა წარმოადგინა თავისი ჰიპოთეზა n². 3) „ზუსტად ერთ კვირაში“ კარაცუბამ შეიმუშავა „დაყავი და იბატონე“ ალგორითმი; 4) 1962 წელს კოლმოგოროვმა დაწერა და გამოაქვეყნა სტატია კარაცუბას სახელით ალგორითმის აღწერით. ”ამ სტატიის შესახებ მხოლოდ მისი ხელახალი გამოქვეყნების შემდეგ გავიგე.”

ასე რომ, შეცდომა არის ის, რომ ნაცვლად 1962 უნდა დაზუსტდეს 1960 წელიწადი. Სულ ეს არის.

ანალიზი

შეცდომების პოვნა არ საჭიროებდა განსაკუთრებულ უნარს.

1. პირველი შეცდომა შეძლებისდაგვარად ტრივიალური იყო და შედარებით თვალსაჩინო ადგილას იყო (თავის დასაწყისი). ნებისმიერი იდიოტი იპოვიდა; მე მხოლოდ ის იდიოტი აღმოვჩნდი.
2. მეორე შეცდომას იპოვიდა იღბალი და შრომისმოყვარეობა, მაგრამ არა უნარი. „უილიამსის“ ინდექსი არის ტომის ბოლო გვერდზე, წიგნის საკმაოდ თვალსაჩინო ნაწილი. მე უბრალოდ ვაფურცლე ინდექსს (ეს არც ისე სავალალოა, როგორც ჟღერს, რადგან კნუტის ინდექსებში სააღდგომო კვერცხებია დამალული. მაგალითად, არის ჩანაწერები არაბულ და ებრაულ ენებზე, ორივე 66-ე გვერდზე მიუთითებს. მაგრამ ამ გვერდზე არ არის ნახსენები. რომელიმე ენაზე; ამის ნაცვლად, ეს ეხება "ენებს, რომლებიც იკითხება მარჯვნიდან მარცხნივ"). და მეორე სახელმა მიიპყრო ჩემი ყურადღება. ვინაიდან ჩვეულებრივ ვიკიპედიას ვკითხულობდი, შევამოწმე რობინ უილიამსი და შევნიშნე შეუსაბამობა.
3. ვისურვებდი, რომ მეთქვა, რომ სერიოზული კვლევა ჩავატარე ისტორიული შეცდომის აღმოსაჩენად, მაგრამ რეალურად უბრალოდ გადავხედე ვიკიპედიის გვერდი კარაცუბას ალგორითმის შესახებ. პირველივე სტრიქონებში ნათქვამია: „კარაცუბას ალგორითმი არის სწრაფი გამრავლების ალგორითმი. აღმოაჩინა ანატოლი კარაცუბამ 1960 წელს და გამოქვეყნდა 1962 წელს“. ამის შემდეგ დარჩა მხოლოდ ორი და ორი დამატება.

მომავალში მსურს ვიპოვო უფრო მნიშვნელოვანი ხარვეზი, განსაკუთრებით კნუტის კოდში. ასევე მინდა ვიპოვო ხარვეზი ფუნდამენტური ალგორითმების პირველ ტომში. შეიძლება მე ვიპოვოდი, მაგრამ რატომღაც ადგილობრივ ბიბლიოთეკას აქვს მხოლოდ 2, 3 და 4A ტომები.

ფინანსური ფაქტები:

• მთლიანობაში, ჩემი წვლილი TAOCP-ში მხოლოდ სამი სიმბოლოსგან შედგება: ერთი დამატება s, გამოცვლა m on n и 2 on 0. $2,56-ად, ეს არის საკმაოდ მომგებიანი სიმბოლო; თუ ასეთ ფულს გადაგიხდიდნენ, 1000 სიტყვიანი სტატია (საშუალოდ ოთხი სიმბოლო) ათი გრანდს მოგიტანდა.
• სამი თექვსმეტობითი დოლარით, მე, 29 სხვა მოქალაქესთან ერთად, სან-სერიფ ბანკის უმდიდრესი მეანაბრეთა სიაში 69-ე ადგილზე ვართ (1 წლის 2019 მაისი).

სხვა დისკუსიები კნუტის ჩეკების შესახებ

• როგორ მივიღოთ ჩეკი კნუთისგან

  ზოგადი რეკომენდაციები კნუტის წიგნებში შეცდომების მოსაძებნად. ძირითადად ტექნიკურ შეცდომებს ეხება, რაც მე არ მაქვს. არის ერთი წინადადება, რომელიც სერიოზულად მივიღე:

  უმჯობესია დაელოდოთ სანამ შეაგროვებთ შეცდომების კრებულს, რათა გაგზავნოთ. რამდენიმე რეალური, მაგრამ არც თუ ისე ღირებული შეცდომის გაერთიანებით, თქვენ გაზრდით იმის ალბათობას, რომ ერთ-ერთი მათგანი რეალურად ჩაითვალოს შეცდომად ან რჩევად. თუ შეცდომებს ერთჯერადად წარადგენთ, თითოეული ცალკე შეიძლება უარყოფილი იყოს.

  არ მინდოდა უბრალოდ უაზრო ბეჭდვითი შეცდომების გაგზავნა, მაგრამ რჩევა გავითვალისწინე და წერილი გავაგზავნე მხოლოდ მაშინ, როცა აღმოვაჩინე ისტორიული შეცდომა, რომელიც საკმაოდ სერიოზული ჩანდა.

• აშუტოშ მეჰრას ჩეკები

  აშუტოშ მეჰრა არის მესამე უმდიდრესი ინვესტორი სან-სერიფში, უზარმაზარი წმინდა ღირებულებით 0x207.f0 BoSS-ში.

• შეამოწმეთ რამდენიმე არაფუნქციური ხარვეზი რეალურ TeX კოდში
• სხვადასხვა: #1 #2 #3 #4 #5 #6

წყარო: www.habr.com