{"id":34164,"date":"2019-10-31T21:56:44","date_gmt":"2019-10-31T18:56:44","guid":{"rendered":"https:\/\/prohoster.info\/blog\/ya-poluchil-ot-knuta-chek-na-0x-3-00\/"},"modified":"2019-10-31T21:56:44","modified_gmt":"2019-10-31T18:56:44","slug":"ya-poluchil-ot-knuta-chek-na-0x-3-00","status":"publish","type":"post","link":"https:\/\/prohoster.info\/sk\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Dostal som od Knuta \u0161ek na 0x$3,00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u2014 vedec v oblasti informatiky, ktor\u00fd sa tak ve\u013emi star\u00e1 o spr\u00e1vnos\u0165 svojich kn\u00edh, \u017ee pon\u00faka jeden \u0161estn\u00e1stkov\u00fd dol\u00e1r<\/b> ($2,56, 0x$1,00) za ak\u00fako\u013evek n\u00e1jden\u00fa \u201echybu\u201c, kde chybou sa pova\u017euje v\u0161etko, \u010do je \u201etechnicky, historicky, typograficky alebo politicky nespr\u00e1vne\u201c. Ve\u013emi som chcel dosta\u0165 \u0161ek od Knuta, preto som sa rozhodol h\u013eada\u0165 chyby v jeho v\u00fdnimo\u010dnom diele \u201eUm\u011bn\u00ed programov\u00e1n\u00ed\u201c<\/b> (TAOCP). Podarilo sa mi n\u00e1js\u0165 tri. Verne slovu, Knuth poslal \u0161ek na 0x$3,00<\/b>.<\/p>\n

\"Dostal
\n
\nAko vid\u00edte, nejde o skuto\u010dn\u00fd \u0161ek. Kedysi posielal Knuth skuto\u010dn\u00e9 \u0161eky, ale prestal s t\u00fdm v roku 2008 z d\u00f4vodu neobmedzen\u00e9ho podvodu<\/a><\/noindex>. Teraz rozosiela \u201eosobn\u00e9 depozitn\u00e9 certifik\u00e1ty\u201c v bance San-Serif<\/a><\/noindex> (BoSS). Hovor\u00ed, \u017ee je pripraven\u00fd posla\u0165 skuto\u010dn\u00e9 peniaze, ak to bude potrebn\u00e9, ale zd\u00e1 sa, \u017ee je to pr\u00edli\u0161 zlo\u017eit\u00e9.
\n<\/a><\/noindex>
\nNa\u0161iel som dve preklepy a jednu historick\u00fa chybu. Vymen\u00edm ich v porad\u00ed klesaj\u00facej trivi\u00e1lnosti.<\/p>\n

Preklep \u010d. 1<\/h1>\n

\nPrv\u00fd preklep \u2014 na strane 392 tretieho zv\u00e4zku \u201eZoradenie a vyh\u013ead\u00e1vanie\u201c, \u00f4smy riadok zospodu: \u201ePo ne\u00faspe\u0161nom h\u013eadan\u00ed je niekedy (sometime) \u017eiaduce vlo\u017ei\u0165 do tabu\u013eky nov\u00fd z\u00e1znam obsahuj\u00faci K<\/i>; met\u00f3da, ktor\u00e1 to rob\u00ed, sa naz\u00fdva algoritmus h\u013eadania a vlo\u017eenia. Chyba spo\u010d\u00edva v tom, \u017ee namiesto sometime<\/i><\/b> m\u00e1 by\u0165 sometimes<\/i><\/b>.<\/p>\n

Samozrejme, v takej chybe nie je ni\u010d prekvapuj\u00face. Iba v tomto \u010dl\u00e1nku ur\u010dite n\u00e1jdete nieko\u013eko preklepov (\u017eiadne ocenenie za ich n\u00e1jdenie). \u010co je v\u0161ak naozaj prekvapuj\u00face, je to, \u017ee si ich tak dlho nikto nev\u0161imol. Strana 392 nie je hlboko zakryt\u00e1 v oddelen\u00ed matematiky, je to najprv\u00e1 strana<\/b> \u0161iestich kapitol \u201eVyh\u013ead\u00e1vanie\u201c! Mo\u017eno jeden z naj\u010d\u00edtanej\u0161\u00edch oddielov knihy. Teoreticky by tam malo by\u0165 najmenej preklepov, ale nie.<\/p>\n

Mimochodom, ak ste niekedy rozm\u00fd\u0161\u013eali nad \u010d\u00edtan\u00edm TAOCP, sk\u00faste to. Mnoh\u00ed povedia, \u017ee ide o pr\u00edru\u010dku<\/b>, ktor\u00e1 nie je ur\u010den\u00e1 na priame \u010d\u00edtanie, ale to nie je pravda. Autor m\u00e1 jasn\u00fd n\u00e1zor a svojsk\u00fd \u0161t\u00fdl. Jedin\u00e9, \u010do br\u00e1ni \u010d\u00edtate\u013enosti, je zlo\u017eitost matematiky. Existuje v\u0161ak jednoduch\u00e9 rie\u0161enie: \u010d\u00edtajte, k\u00fdm ned\u00f4jdete k matematike, ktor\u00fa nerozumiete, presko\u010dte ju a otvor\u00edte nasleduj\u00facu \u010das\u0165, ktor\u00fa m\u00f4\u017eete pochopi\u0165. Takto preskakujem aspo\u0148 80 % knihy, ale ostatn\u00fdch 20 % je n\u00e1dhern\u00fdch!<\/p>\n

Taktie\u017e sa hovor\u00ed, \u017ee TAOCP nerelevantn\u00e1<\/b>, zastaran\u00e1 alebo inak nepou\u017eite\u013en\u00e1 na \u201ere\u00e1lne programovanie\u201c. To je tie\u017e nepravda. Napr\u00edklad v prvej \u010dasti po \u00favode sa zaober\u00e1 vyh\u013ead\u00e1van\u00edm prvku v nesotrdenom poli. Najjednoduch\u0161\u00ed algoritmus je zn\u00e1my v\u0161etk\u00fdm program\u00e1torom. Spustite ukazovate\u013e na za\u010diatku po\u013ea, potom vykonajte nasleduj\u00face kroky v cykle:<\/p>\n

    \n
  1. Skontrolujte, \u010di je aktu\u00e1lny prvok \u017eiadan\u00fd. Ak \u00e1no, vr\u00e1\u0165te ho; v opa\u010dnom pr\u00edpade\n<\/li>\n
  2. Skontrolujte, \u010di je ukazovate\u013e mimo po\u013ea. Ak \u00e1no, vr\u00e1\u0165te chybu; v opa\u010dnom pr\u00edpade\n<\/li>\n
  3. Zv\u00fd\u0161te ukazovate\u013e a pokra\u010dujte.<\/li>\n<\/ol>\n

    \nTeraz zv\u00e1\u017ete: ko\u013eko kontrol hran\u00edc si tento algoritmus vy\u017eaduje, v priemere? V najhor\u0161om pr\u00edpade, ke\u010f pole neobsahuje prvok, si pre ka\u017ed\u00fd prvok v zozname vy\u017eaduje jednu kontrolu, a v priemere to bude nie\u010do ako \"Dostal. Inteligentnej\u0161\u00ed algoritmus vyh\u013ead\u00e1vania m\u00f4\u017ee zvl\u00e1dnu\u0165 len jednu kontrolu hran\u00edc. Pripojte po\u017eadovan\u00fd prvok na koniec po\u013ea, potom spustite ukazovate\u013e na za\u010diatku po\u013ea a vykonajte nasleduj\u00face kroky v cykle:<\/p>\n

      \n
    1. Skontrolujte, \u010di je aktu\u00e1lny prvok \u017eiadan\u00fd. Ak \u00e1no, vr\u00e1\u0165te odpove\u010f, ak je ukazovate\u013e v r\u00e1mci po\u013ea, alebo chybu, ak nie je. V opa\u010dnom pr\u00edpade\n<\/li>\n
    2. Zv\u00fd\u0161te ukazovate\u013e a pokra\u010dujte.<\/li>\n<\/ol>\n

      \nTak \u010di onak, prvok bude zaru\u010dene n\u00e1jden\u00fd a kontrola hran\u00edc sa vykon\u00e1 len raz, ke\u010f k tomu d\u00f4jde. Je to hlbok\u00e1 my\u0161lienka, ale dos\u0165 jednoduch\u00e1 aj pre za\u010diato\u010dn\u00edka program\u00e1tora. Asi nem\u00f4\u017eem hovori\u0165 o aktu\u00e1lnosti tejto pr\u00e1ce pre in\u00fdch, ale hne\u010f som bol schopn\u00fd aplikova\u0165 t\u00fato m\u00fadros\u0165 ako vo svojom osobnom, tak aj v profesion\u00e1lnom k\u00f3de. Kniha TAOCP je pln\u00e1 tak\u00fdchto per\u00e1l (na spravodlivos\u0165, s\u00fa tam aj mnoh\u00e9 podivn\u00e9 veci, ako napr\u00edklad bublinkov\u00e9 triedenie<\/a><\/noindex>).<\/p>\n

      \u201eH\u013eadanie, h\u013eadanie
      \nTak dlho
      \nH\u013eadanie, h\u013eadanie
      \nI simply wanted to dance\"<\/i>
      \n\u2014 Luther Vandross, \u201eH\u013eadanie\u201c (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Tiskov\u00e1 chyba \u010d. 2<\/h1>\n

      \nDruh\u00e1 chyba sa nach\u00e1dza vo zv\u00e4zku 4A, \u201eKombinatorick\u00e9 algoritmy\u201c, \u010das\u0165 1. Na strane 60 je op\u00edsan\u00e1 \u00faloha pl\u00e1novania vyst\u00fapen\u00ed komikov v r\u00f4znych kas\u00ednach. Ako pr\u00edklad s\u00fa uveden\u00ed niektor\u00ed skuto\u010dn\u00ed komici, vr\u00e1tane Lily Tomlin, Weird Al Yankovic a Robin Williams, ktor\u00fd bol e\u0161te na\u017eive, ke\u010f kniha vy\u0161la. Knuth v\u017edy uv\u00e1dza v indexe cel\u00e9 men\u00e1, tak\u017ee Williams je uveden\u00fd na strane 882 ako \u201eWilliams, Robin Mac-Lorin\u201c. No jeho druh\u00e9 meno sa kon\u010d\u00ed na \u201en\u201c, a nie na \u201em\u201c, teda Mac-Lorin.<\/p>\n

      Mac-Lorin je diev\u010densk\u00e9 priezvisko jeho matky. Bola pravnu\u010dkou Anselma Jozefa Mac-Lorina, 34. guvern\u00e9ra Mississippi. Jeho p\u00f4sobenie, zd\u00e1 sa, nebolo zapam\u00e4tan\u00e9 ni\u010d\u00edm dobr\u00fdm. Z knihy \u201eMississippi: hist\u00f3ria\u201c<\/a><\/noindex>:<\/p>\n

      \u201eNajd\u00f4le\u017eitej\u0161ou udalos\u0165ou po\u010das administrat\u00edvy Mac-Lorina bolo vyhl\u00e1senie USA vojny \u0160panielsku na jar 1898... \u017dia\u013e, vojna pravdepodobne poskytla niektor\u00fdm \u0161t\u00e1tnym \u00faradn\u00edkom pr\u00edle\u017eitos\u0165 praktizova\u0165 korupciu. Mac-Lorin bol obvinen\u00fd z r\u00f4znych pochybnych prakt\u00edk, vr\u00e1tane rodink\u00e1rstva a nadmern\u00e9ho vyu\u017e\u00edvania pr\u00e1vomoc\u00ed na milos\u0165. V dobe hnutia za triezvos\u0165 kritici obvi\u0148ovali guvern\u00e9ra z alkoholizmu, \u010do verejne priznal.\u201c<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Historick\u00e1 chyba<\/h1>\n

      \nZv\u00e1\u017eme tradi\u010dn\u00fd algoritmus n\u00e1sobenia<\/b> z u\u010debn\u00e9ho pl\u00e1nu. Ko\u013eko vy\u017eaduje jednocifern\u00fdch oper\u00e1ci\u00ed n\u00e1sobenia? Predpokladajme, \u017ee n\u00e1sob\u00edte \"Dostal-cifern\u00e9 \u010d\u00edslo \"Dostal na \"Dostal-cifern\u00e9 \"Dostal. Najprv n\u00e1sob\u00edte prv\u00fa cifru \"Dostal ka\u017edou cifrou \"Dostal po rade. Potom n\u00e1sob\u00edte druh\u00fa cifru \"Dostal ka\u017edou cifrou \"Dostal po rade a tak \u010falej, k\u00fdm neprejdete v\u0161etk\u00fdmi ciferami \"Dostal. T\u00fdmto sp\u00f4sobom tradi\u010dn\u00e9 n\u00e1sobenie vy\u017eaduje \"Dostal primit\u00edvne n\u00e1sobenia. Konkr\u00e9tne, n\u00e1sobenie dvoch \u010d\u00edsel po \"Dostal cifr\u00e1ch vy\u017eaduje \"Dostal jednocifern\u00fdch n\u00e1soben\u00ed.<\/p>\n

      Je to zl\u00e9, ale proces m\u00f4\u017eeme optimalizova\u0165 pomocou met\u00f3dy vyvinutej rusk\u00fdm matematikom Anatolijom Alexejevi\u010dom Karacubom. Predpokladajme, \u017ee \"Dostal a \"Dostal\u00a0s\u00fa dvojcifern\u00e9 desatinn\u00e9 \u010d\u00edsla; to znamen\u00e1, \u017ee existuj\u00fa \u010d\u00edsla \"Dostal, \"Dostal, \"Dostal, \"Dostal tak\u00e9, \u017ee \"Dostal a \"Dostal (generaliz\u00e1cia tohto algoritmu na vy\u0161\u0161ie \u010d\u00edsla si vy\u017eaduje ur\u010dit\u00e9 manipul\u00e1cie; hoci to nie je pr\u00edli\u0161 zlo\u017eit\u00e9, aby som sa vyhol chyb\u00e1m v detailoch, rad\u0161ej sa budem dr\u017ea\u0165 jednoduch\u00e9ho pr\u00edkladu). Potom \"Dostal, \"Dostal, \"Dostal. N\u00e1sobenie dvoj\u010dlenov d\u00e1va \"Dostal. V tejto chv\u00edli m\u00e1me st\u00e1le \"Dostal jednocifern\u00fdch n\u00e1soben\u00ed: \"Dostal, \"Dostal, \"Dostal, \"Dostal. Teraz s\u010d\u00edtajme a odpo\u010d\u00edtajme \"Dostal. Po nieko\u013ek\u00fdch preskupeniach, ktor\u00e9 nech\u00e1m ako cvi\u010denie pre \u010ditate\u013ea, vznik\u00e1 \"Dostal\u00a0\u2014 iba tri jednocifern\u00e9 n\u00e1sobenia! (Existuj\u00fa niektor\u00e9 kon\u0161tantn\u00e9 koeficienty, ale tie sa daj\u00fa vypo\u010d\u00edta\u0165 len s\u010d\u00edtan\u00edm a pos\u00favan\u00edm \u010d\u00edslic).<\/p>\n

      Ne\u017eiadajte o d\u00f4kaz, ale Karatsubov algoritmus<\/b> (rekurz\u00edvne zobecnen\u00fd z predch\u00e1dzaj\u00faceho pr\u00edkladu) zlep\u0161uje tradi\u010dn\u00fa met\u00f3du n\u00e1sobenia s \"Dostal oper\u00e1ciami na \"Dostal. Majte na pam\u00e4ti, \u017ee toto je skuto\u010dn\u00e9 zlep\u0161enie algoritmu, a nie optimaliz\u00e1cia pre v\u00fdpo\u010dty v hlave. Skuto\u010dne, algoritmus nie je vhodn\u00fd na po\u010d\u00edtanie v hlave, preto\u017ee si vy\u017eaduje ve\u013ek\u00e9 re\u017eijn\u00e9 n\u00e1klady na rekurz\u00edvne oper\u00e1cie. Okrem toho sa efekt neprejav\u00ed naplno, k\u00fdm \u010d\u00edsla nie s\u00fa dostato\u010dne ve\u013ek\u00e9 (\u0161\u0165astne, namiesto Karatsubovho algoritmu sa objavili e\u0161te r\u00fdchlej\u0161ie met\u00f3dy: v marci 2019 bol publikovan\u00fd algoritmus, ktor\u00fd si vy\u017eaduje iba n log n<\/i><\/a><\/noindex> n\u00e1soben\u00ed; zr\u00fdchlenie sa uplat\u0148uje len na nepredstavite\u013ene ve\u013ek\u00e9 \u010d\u00edsla).<\/p>\n

      Tento algoritmus je pop\u00edsan\u00fd na strane 295 druh\u00e9ho zv\u00e4zku \u00abAlgoritmy a ich anal\u00fdzy\u00bb. Tam Knuth p\u00ed\u0161e: \u201eZauj\u00edmav\u00e9 je, \u017ee t\u00fato my\u0161lienku objavili a\u017e v 1962<\/b> roku\u201c, ke\u010f bola publikovan\u00e1 \u010dl\u00e1nok popisuj\u00faci Karatsubov algoritmus. Ale! V roku 1995 publikoval Karatsuba \u010dl\u00e1nok \u201eZlo\u017eitosti v\u00fdpo\u010dtov\u201c, v ktorom hovor\u00ed nieko\u013eko vec\u00ed: 1) okolo roku 1956 Kolmogorov predpokladal, \u017ee n\u00e1sobenie nie je mo\u017en\u00e9 vykona\u0165 za menej ako \"Dostal krokov; 2) v 1960<\/b> roku bol Karatsuba na semin\u00e1ri, kde Kolmogorov zhrnul svoju hypot\u00e9zu n\u00b2. 3) \u201ePr\u00e1ve za t\u00fd\u017ede\u0148\u201c Karatsuba vyvinul algoritmus \u201erozde\u013euj a panuj\u201c; 4) v roku 1962 nap\u00edsal a publikoval \u010dl\u00e1nok v mene Karatsubu<\/i> s popisom algoritmu. \u201eO tomto \u010dl\u00e1nku som sa dozvedel a\u017e po tom, \u010do ho pretl\u00e1\u010dali\u201c.<\/p>\n

      T\u00fdm p\u00e1dom chyba spo\u010d\u00edva v tom, \u017ee namiesto 1962<\/i> mal by\u0165 uveden\u00fd 1960<\/i> rok. A to je v\u0161etko.<\/p>\n

      Anal\u00fdza<\/h1>\n

      \nH\u013eadanie ch\u00fdb nevy\u017eadovalo osobitn\u00e9 zru\u010dnosti.<\/b><\/p>\n

        \n
      1. Prv\u00e1 chyba bola tak ban\u00e1lna, ako len m\u00f4\u017ee by\u0165, a nach\u00e1dzala sa v relat\u00edvne vidite\u013enom mieste (za\u010diatok kapitoly). Ka\u017ed\u00fd idiot by ju na\u0161iel; jednoducho som bol t\u00fdm idiotom.\n<\/li>\n
      2. H\u013eadanie druhej chyby si vy\u017eadovalo \u0161\u0165astie a usilovnos\u0165, nie v\u0161ak zru\u010dnos\u0165. Index pre \u201eWilliamsa\u201c sa nach\u00e1dza na predposlednej strane zv\u00e4zku, dos\u0165 v\u00fdrazn\u00e1 \u010das\u0165 knihy. Pr\u00e1ve som prelistov\u00e1val index (nie je to tak \u017eiaduce, ako sa zd\u00e1, preto\u017ee v indexoch Knutha s\u00fa schovan\u00e9 ve\u013ek\u00e9 prekvapenia. Napr\u00edklad, s\u00fa tam polo\u017eky v arab\u010dine a hebrej\u010dine, a obidve ukazuj\u00fa na stranu 66. Ale na tejto strane nie je spomenut\u00fd \u017eiaden z t\u00fdchto jazykov; namiesto toho sa tu spom\u00ednaj\u00fa \u201ejazyky, ktor\u00e9 sa \u010d\u00edtaj\u00fa sprava do\u013eava\u201c). A moja pozornos\u0165 up\u00fatalo druh\u00e9 meno. Ke\u010f\u017ee zvy\u010dajne \u010d\u00edtam Wikip\u00e9diu, skontroloval som Robina Williamsa a v\u0161imol si nes\u00falad.\n<\/li>\n
      3. R\u00e1d by som povedal, \u017ee som urobil seri\u00f3zny v\u00fdskum, aby som na\u0161iel historick\u00fa chybu, ale v skuto\u010dnosti som sa len pozrel na str\u00e1nku Wikip\u00e9die o Karatsubovom algoritme.<\/a><\/noindex>U\u017e v prv\u00fdch vet\u00e1ch sa p\u00ed\u0161e: \u201eKaratsubov algoritmus je algoritmus r\u00fdchlej n\u00e1sobilky. Objavil ho Anatolij Karatsuba v roku 1960 a publikoval v roku 1962.\u201c Po tom sa u\u017e len zdalo, \u017ee sta\u010d\u00ed spo\u010d\u00edta\u0165 dve a dve.<\/li>\n<\/ol>\n

        \nV bud\u00facnosti by som chcel n\u00e1js\u0165 podstatnej\u0161iu chybu, najm\u00e4 v k\u00f3de Knutha. Rovnako by som chcel n\u00e1js\u0165 bug v prvom zv\u00e4zku \u201eZ\u00e1kladn\u00e9 algoritmy\u201c. Mo\u017eno by som aj na\u0161iel, ale v miestnej kni\u017enici z nejak\u00e9ho d\u00f4vodu maj\u00fa iba zv\u00e4zky 2, 3 a 4A.<\/p>\n

        Finan\u010dn\u00e9 fakty:<\/b><\/p>\n