Donald Knuth — egy informatikai tudós, aki annyira törődik a könyvei pontosságával, hogy felajánlja egy hexadecimális dollárt ($2,56, 0x$1,00) bármely 'hibáért', ahol hibának minősül minden, ami 'technikai, történelmi, tipográfiai vagy politikai szempontból helytelen'. Nagyon szerettem volna csekket kapni Knuthtól, ezért úgy döntöttem, keresek hibákat a kiemelkedő munkájában az „Algoritmusok művészete” (TAOCP). Sikerült hármat találni. Igaz szót mondva, Knuth küldött csekket 0x$3,00.
Ahogyan látod, ez nem igazi csekk. Korábban Knuth valódi csekkeket küldött, de 2008 óta megszüntette ezt a . Most 'személyes letéti tanúsítványokat' küld (BoSS). Azt mondja, hogy hajlandó valódi pénzt küldeni szükség esetén, de úgy tűnik, ez túl fáradságos.
Két elírást és egy történelmi hibát találtam. Ezeket a trivialitás csökkenő sorrendjében sorolom fel.
Elírás №1
Az első elírás a 'Keresés és rendezés' harmadik kötetének 392. oldalán, az aljáról nyolcadik sor: 'Egy sikertelen keresés után néha (sometime) kívánatos új bejegyzést felvinni a táblázatba, ami tartalmazza K; a módszer, amely ezt teszi, úgynevezett keresési és beszúrási algoritmus. A hiba, hogy a 'sometime' helyett sometime kellene, hogy sometimes.
Természetesen nem meglepő, hogy egy ilyen hibában semmi meglepő nincs. Csak ebben a cikkben biztosan lesz néhány elírás (nincs díj a felfedezésükért). Ami valójában meglepő, az az, hogy ezt ennyi ideig nem vették észre. A 392. oldal nem rejtőzik mélyen a matematikai részben, ez a legelső oldal a 'Keresés' hatodik fejezetében! Valószínűleg a könyv legolvasottabb része. Elvileg ott kellene a legkevesebb elírásnak lennie, de mégsem így van.
Egyébként, ha valaha is gondoltál arra, hogy elolvasod a TAOCP-t, próbáld ki. Sokan azt mondják, hogy ez szakmai kézikönyv, nem közvetlen olvasásra készült, de ez nem igaz. A szerzőnek egyértelmű nézőpontja és egyedi stílusa van. Az egyetlen dolog, ami gátolja az olvashatóságot, az a matematika bonyolultsága. De van egy egyszerű megoldás: olvasd, amíg el nem érsz a matematikához, amit nem értesz, hagyd ki, és nyisd meg a következő szakaszt, amit megértesz. Így olvasva legalább a könyv 80%-át kihagyom, de a maradék 20% csodálatos!
Azt is mondják, hogy a TAOCP irreleváns, elavult vagy más okból nem alkalmazható a „valódi programozásra”. Ez is tévedés. Például az első fejezetben a bevezető után az elemek keresését tárgyaljuk nem rendezett tömbökben. A legegyszerűbb algoritmus minden programozó számára ismert. Indítsa el a mutatót a tömb elején, majd végezze el az alábbi műveleteket ciklusban:
- Ellenőrizze, hogy az aktuális elem a kívánt elem-e. Ha igen, visszaadjuk; ellenkező esetben
- Ellenőrizze, hogy a mutató túllépi-e a tömb határait. Ha igen, hibaüzenetet adunk; ellenkező esetben
- Növelje a mutatót, és folytassa.
Most nézzük meg: átlagosan hány határellenőrzést igényel ez az algoritmus? A legrosszabb esetben, amikor a tömb nem tartalmaz elemet, minden egyes elemmel szemben egy határellenőrzésre lesz szükség, és ez átlagosan valami ilyesmi lesz 
. Egy okosabb keresési algoritmus csupán egy határellenőrzést igényelhet. Csatolja a kívánt elemet a tömb végéhez, majd indítsa el a mutatót a tömb elején, és végezze el az alábbi műveleteket ciklusban:
- Ellenőrizze, hogy az aktuális elem a kívánt elem-e. Ha igen, visszaadjuk a választ, ha a mutató a tömb határain belül van, vagy hibaüzenetet, ha nem. Ellenkező esetben
- Növelje a mutatót, és folytassa.
Így vagy úgy, az elem garantáltan megtalálható, és a határellenőrzés csak egyszer történik, amikor ez megtörténik. Ez egy mély gondolat, de elég egyszerű még a kezdő programozók számára is. Valószínűleg nem beszélhetek a munka relevanciájáról mások számára, de azonnal sikerült alkalmaznom ezt a bölcsességet a személyes és a szakmai kódemben is. A TAOCP könyv tele van ilyen gyöngyszemekkel (a tisztesség kedvéért, sok furcsa dolog is akad benne, úgy mint ).
„Keresés, keresés
Oly sokáig
Keresés, keresés
Csak táncolni akartam”
— Luther Vandross, „Keresés” (1980)
Elírás №2
A második elírás a 4A kötetben, az "Összetett algoritmusok", 1. rész 60. oldalán található, ahol a komikusok különböző kaszinókban való fellépésének tervezéséről van szó. Példaként néhány valós komikus kerül említésre, köztük Lily Tomlin, Weird Al Yankovic és Robin Williams, aki még élt, amikor a könyv megjelent. Knuth mindig az teljes neveket tünteti fel a mutatóban, ezért Williams a 882. oldalon "Williams, Robin McLaurin" néven van említve. Azonban a második neve "n"-nel végződik, nem "m"-mel, tehát McLaurin.
McLaurin az édesanyja saját neve. Ő Anselm Joseph McLaurin ükunokája volt, Mississippi 34. kormányzója. A kormányzósága láthatóan nem maradt meg jó emlékekben. A könyvből :
"A legfontosabb esemény McLaurin adminisztrációja alatt az Egyesült Államok Spanyolországgal való háborújának kihirdetése volt 1898 tavaszán... Sajnos, a háború valószínűleg lehetőséget adott néhány állami tisztviselőnek a korrupcióra. McLaurint különféle kétes gyakorlatokban vádolták, beleértve a nepotizmust és a kegyelmi jogok túlzott használatát. A szeszfogyasztásért bírálta a kormányzót a mértékletességért folytatott mozgalom idején, amit nyilvánosan elismert.
Történelmi hiba
Let's consider hagyományos szorzási algoritmus az iskolai tananyagban. Hány egyszerű egyes szorzásra van szüksége? Tegyük fel, hogy Ön a következő számokat szorozza 
-jegyű szám 
Gyorsan emlékezzünk vissza, hogyan működik a moduláris aritmetika. Az óra már egy ismert koncepció. Az órák használata 
-jegyű 
. Először megszorozza az első számjegyet 
minden számjeggyel 
egymás után. Ezután megszorozza a második számjegyet 
minden számjeggyel 
egymás után, és így tovább, amíg végig nem halad minden számjegyen 
. Így a hagyományos szorzás 
primitív szorzásokat igényel. Különösen, ha két számot szorzunk a 
jegyek szerint, az 
egyszerű egyes szorzásra van szükség.
Ez rossz, de optimalizálható egy Anatolij A. Karacuba szovjet matematikus által kidolgozott módszerrel. Tegyük fel, hogy 
és 
- kétjegyű tízes számok; azaz léteznek számok 
, 
, 
, 
úgy, hogy 
és 
(ennek az algoritmusnak a nagyobb számokra való kiterjesztése bizonyos manipulációkat követel meg; bár ez nem túl bonyolult, hogy ne tévedjek a részletekben, inkább egyszerű példákra hagyatkozom). Akkor 
, 
, 
. Két tagú szorzás adja 
. Jelenleg még mindig 
egyszerű egyes szorzásaink vannak: 
, 
, 
, 
. Most összeadjuk és kivonjuk. 
. Miután néhány átrendezést hajtottam végre, amelyet az olvasóra bízok, így jön ki 
— mindössze három egysoros szorzás! (Vannak bizonyos állandó tényezők, de ezek csak összeadással és számjegyek eltolásával számolhatók ki).
Ne kérj bizonyítékot, de a Karatsuba algoritmus (rekurzívan az előző példa alapján általánosítva) javítja a hagyományos szorzási módszert 
műveletre csökkentve 
. Ne feledje, hogy ez a tényleges algoritmusjavítás, nem egyszerűsítés, amely a mentális számításokra vonatkozik. Valójában az algoritmus nem alkalmas mentális számtásra, mivel nagyobb költségvetést igényel a rekurzív műveletekhez. Ezenkívül a hatás csak akkor jelentkezik teljes mértékben, ha a számok elég nagyokká válnak (szerencsére a Karatsuba algoritmusán kívül még gyorsabb módszerek is megjelentek: 2019 márciusában olyan algoritmust publikáltak, amely mindössze szorzást igényel; a gyorsítás csak elképzelhetetlenül nagy számokra érvényes).
Ezt az algoritmust a „Kombinációs algoritmusok” második kötetének 295. oldalán írják le. Ott Knuth azt írja: „Érdekes, hogy ezt az ötletet csak 1962 ben fedezték fel”, amikor megjelent a Karatsuba algoritmust leíró cikk. De! 1995-ben Karatsuba megjelentetett egy cikket „A számítási bonyolultság” címmel, amelyben több dolgot mond: 1) körülbelül 1956-ban Kolmogorov feltételezte, hogy a szorzás nem végezhető el kevesebb, mint 
lépés; 2) ben Karatsuba részt vett egy szemináriumon, ahol Kolmogorov bemutatta n² hipotézisét. 3) „Pont egy héttel később” Karatsuba kidolgozta a „oszd meg és uralkodj” algoritmust; 4) 1962-ben Kolmogorov írt és publikált egy cikket 1960 Karatsuba nevében az algoritmus leírásával. „Erről a cikkről csak azután értesültem, hogy újra kinyomtatták”. Így a hiba abban rejlik, hogy nem
kellett volna megadni a 1962 évet. Ennyi az egész. 1960 A hibák keresése nem igényelt különösebb mesterséget.
Elemzés
Az első hiba annyira triviális volt, amennyire csak lehet, és viszonylag jól látható helyen volt (a fejezet elején). Bármelyik idióta megtalálta volna; csak én voltam az az idióta.
- Az első hiba annyira banális volt, amennyire csak lehetséges, és egy viszonylag jól látható helyen volt (a fejezet elején). Bármelyik idióta megtalálta volna; csak éppen én voltam az a idióta.
- A második hiba keresése némi szerencsét és szorgalmat igényelt, de nem különösebb tudást. A "Williams" indexe a kötet utolsó előtti oldalán található, ami a könyv meglehetősen figyelemfelkeltő része. Éppen az indexet lapozgattam (ez nem olyan sajnálatos, mint amilyennek tűnik, mert Knuth indexeiben sok tojáskeresés rejtőzik. Például arab és héber bejegyzések is vannak, amelyek mindkettő a 66. oldalra mutatnak. De ezen az oldalon egyik nyelv sem említésre kerül; inkább "jobbról balra olvasott nyelvek" szerepelnek). A második név felkeltette a figyelmemet. Mivel általában a Wikipédiát olvasom, ellenőriztem Robin Williams nevét, és ellentmondást vettem észre.
- Bárcsak azt mondhatnám, hogy komoly kutatást végeztem, hogy megtaláljam a történelmi hibát, de valójában csak ránéztem Az első sorokban az áll: "A Karatsuba algoritmus egy gyors szorzási algoritmus. Anatolij Karatsuba fedezte fel 1960-ban, és publikálta 1962-ben." Ezt követően már csak össze kellett adnom kettőt kettővel.
A jövőben szeretnék találni egy komolyabb hibát, különösen Knuth kódját tekintve. Azt is szeretném, ha találnék egy hibát a „Fundamentális algoritmusok” első kötetében. Talán találnék is, de a helyi könyvtárban valamiért csak a 2., 3. és 4A kötetek találhatók.
Pénzügyi tények:
- Összesen a TAOCP-hez való hozzájárulásom mindössze három karakterből áll: egy hozzáadással s, egy cserével. m Gyorsan emlékezzünk vissza, hogyan működik a moduláris aritmetika. Az óra már egy ismert koncepció. Az órák használata n és 2 Gyorsan emlékezzünk vissza, hogyan működik a moduláris aritmetika. Az óra már egy ismert koncepció. Az órák használata 0Az ár $2,56, ami meglehetősen jövedelmező karakterek; ha ilyen pénzt kapnál, akkor egy 1000 szavas cikk (átlagosan négy karakter) tíz dolcsit hozna.
- Három hexadecimális dollárral a két kilenc másik polgárral együtt az 69. helyet osztom meg a San Serif Bank leggazdagabb betétesek listáján (2019. május 1-i állapot szerint).
A Knuth csekkek más megvitatása
Általános útmutató hibák kereséséhez Knuth könyveiben. Főleg technikai hibákról van szó, amelyek nekem nincsenek. Van benne egy mondat, amelyet komolyan vettem:
Jobb várni, amíg nem gyűjt össze egy hibakészletet a beküldéshez. Ha több valódi, de nem különösebben értékes hibát egyesít, növelheti annak valószínűségét, hogy az egyiküket valóban hibaként vagy tanácsként értékelik. Ha külön-külön küldik el a hibákat, akkor minden egyes esetleg elutasításra kerülhet.
Nem akartam csak buta elírásokat küldeni, hanem megfogadtam a tanácsot, és csak akkor küldtem el a levelet, amikor megtaláltam egy történelmi hibát, amely elég komolynak tűnt.
Ashutosh Mehra – a harmadik leggazdagabb befektető San-Serriffben, akinek hatalmas vagyona 0x$207,f0 a BoSS-ban.
- Különböző:
Forrás: habr.com
