{"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\/ro\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Am primit de la Knut un cec \u00een valoare de 0x$3,00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u2014 un om de \u0219tiin\u021b\u0103 \u00een domeniul informaticii, care se \u00eengrijoreaz\u0103 at\u00e2t de mult de corectitudinea c\u0103r\u021bilor sale \u00eenc\u00e2t ofer\u0103 o sut\u0103 de dolari hexadecimali<\/b> ($2,56, 0x$1,00) pentru orice \u201eeroare\u201d g\u0103sit\u0103, unde o eroare este considerat\u0103 tot ceea ce este \u201etehnic, istoric, tipografic sau politic gre\u0219it\u201d. Mi-a pl\u0103cut mult s\u0103 primesc un cec de la Knuth, a\u0219a c\u0103 am decis s\u0103 caut erori \u00een opera sa remarcabil\u0103 \u201eArta program\u0103rii\u201d<\/b> (TAOCP). Am reu\u0219it s\u0103 g\u0103sesc trei. \u00cen conformitate cu cuv\u00e2ntul, Knuth mi-a trimis un cec de 0x$3,00<\/b>.<\/p>\n

\"Am
\n
\nA\u0219a cum vede\u021bi, acesta nu este un cec adev\u0103rat. C\u00e2ndva, Knuth trimitea cecuri reale, dar a \u00eencetat \u00een 2008 din cauza fraudei necontrolate<\/a><\/noindex>. Acum trimite \u201ecertificate de depozit personale\u201d \u00een banca San Serriffe<\/a><\/noindex> (BoSS). El spune c\u0103 este gata s\u0103 trimit\u0103 bani reali dac\u0103 este necesar, dar, se pare, este prea complicat.
\n<\/a><\/noindex>
\nAm g\u0103sit dou\u0103 gre\u0219eli de tipografie \u0219i o gre\u0219eal\u0103 istoric\u0103. Le voi enumera \u00een ordine de la cea mai pu\u021bin trivial\u0103.<\/p>\n

Gre\u0219eala de tipografie nr. 1<\/h1>\n

\nPrima gre\u0219eal\u0103 de tipografie \u2014 pe pagina 392 a volumului trei \u201eSortare \u0219i c\u0103utare\u201d, a opta linie de jos: \u201eDup\u0103 o c\u0103utare nereu\u0219it\u0103, uneori (sometime) este recomandabil s\u0103 introduci o nou\u0103 \u00eenregistrare \u00een tabel care con\u021bine K<\/i>; metoda care face acest lucru se nume\u0219te algoritm de c\u0103utare \u0219i inserare. Gre\u0219eala este c\u0103 \u00een loc de sometime<\/i><\/b> ar trebui s\u0103 fie sometimes<\/i><\/b>.<\/p>\n

Desigur, o astfel de gre\u0219eal\u0103 nu este surprinz\u0103toare. Doar \u00een acest articol cu siguran\u021b\u0103 se vor g\u0103si c\u00e2teva gre\u0219eli de tipografie (f\u0103r\u0103 recompense pentru g\u0103sirea lor). Ceea ce este cu adev\u0103rat surprinz\u0103tor este c\u0103 a fost neremarcat\u0103 at\u00e2t de mult timp. Pagina 392 nu este \u00eengropat\u0103 ad\u00e2nc \u00een sec\u021biunea de matematic\u0103, aceasta este cea mai prima pagin\u0103<\/b> a \u0219asea capitol\u201e C\u0103utare\u201d! Poate unul dintre cele mai citite sec\u021biuni ale c\u0103r\u021bii. \u00cen teorie, acolo ar trebui s\u0103 fie cele mai pu\u021bine gre\u0219eli de tipografie, dar nu este a\u0219a.<\/p>\n

Apropo, dac\u0103 ai g\u00e2ndit vreodat\u0103 s\u0103 cite\u0219ti TAOCP, \u00eencearc\u0103. Mul\u021bi vor spune c\u0103 este un ghid<\/b>, nu destinat citirii directe, dar aceasta nu este adev\u0103rat. Autorul are un punct de vedere clar \u0219i un stil distinctiv. Singurul lucru care \u00eempiedic\u0103 citibilitatea este complexitatea matematicii. Totu\u0219i, exist\u0103 o solu\u021bie simpl\u0103: cite\u0219te p\u00e2n\u0103 ajungi la matematica pe care nu o \u00een\u021belegi, s\u0103ri peste ea \u0219i deschide urm\u0103toarea sec\u021biune pe care o po\u021bi \u00een\u021belege. Citind astfel, sar peste cel pu\u021bin 80% din carte, dar restul de 20% este minunat!<\/p>\n

De asemenea, se spune c\u0103 TAOCP nu este relevant\u0103<\/b>, este \u00eenvechit\u0103 sau \u00een alt mod inaplicabil program\u0103rii \u201ereale\u201d. Aceasta este, de asemenea, o minciun\u0103. De exemplu, \u00een prima sec\u021biune dup\u0103 introducere se discut\u0103 despre c\u0103utarea unui element \u00eentr-un tablou nesortat. Cel mai simplu algoritm este cunoscut de to\u021bi programatorii. Porni\u021bi un pointer la \u00eenceputul tabloului, apoi efectua\u021bi urm\u0103torii pa\u0219i \u00eentr-un ciclu:<\/p>\n

    \n
  1. Verifica\u021bi dac\u0103 elementul curent este cel dorit. Dac\u0103 da, returna\u021bi-l; \u00een caz contrar\n<\/li>\n
  2. Verifica\u021bi dac\u0103 pointerul este \u00een afara tabloului. Dac\u0103 da, returna\u021bi o eroare; \u00een caz contrar\n<\/li>\n
  3. Cre\u0219te\u021bi pointerul \u0219i continua\u021bi.<\/li>\n<\/ol>\n

    \nAcum s\u0103 ne g\u00e2ndim: c\u00e2te verific\u0103ri de limit\u0103 necesit\u0103 acest algoritm, \u00een medie? \u00cen cel mai r\u0103u caz, c\u00e2nd tabloul nu con\u021bine elementul, pentru fiecare element din list\u0103 va fi necesar\u0103 o verificare, iar \u00een medie va fi ceva de genul \"Am. Un algoritm de c\u0103utare mai inteligent poate necesita doar o verificare de limit\u0103. Ata\u0219a\u021bi elementul dorit la sf\u00e2r\u0219itul tabloului, apoi porni\u021bi pointerul la \u00eenceputul tabloului \u0219i efectua\u021bi urm\u0103torii pa\u0219i \u00eentr-un ciclu:<\/p>\n

      \n
    1. Verifica\u021bi dac\u0103 elementul curent este cel dorit. Dac\u0103 da, returna\u021bi r\u0103spunsul, dac\u0103 pointerul este \u00een limitele tabloului, sau o eroare, dac\u0103 nu este. \u00cen caz contrar\n<\/li>\n
    2. Cre\u0219te\u021bi pointerul \u0219i continua\u021bi.<\/li>\n<\/ol>\n

      \nA\u0219a sau altfel, elementul va fi g\u0103sit garantat, iar verificarea limitelor se face doar o singur\u0103 dat\u0103, atunci c\u00e2nd se \u00eent\u00e2mpl\u0103. Aceasta este o idee profund\u0103, dar suficient de simpl\u0103 chiar \u0219i pentru un programator \u00eencep\u0103tor. Probabil c\u0103 nu pot vorbi despre relevan\u021ba lucr\u0103rii pentru al\u021bii, dar am reu\u0219it imediat s\u0103 aplic aceast\u0103 \u00een\u021belepciune at\u00e2t \u00een codul personal, c\u00e2t \u0219i \u00een cel profesional. Cartea TAOCP este plin\u0103 de astfel de perle (p\u00e2n\u0103 la urm\u0103, este plin\u0103 \u0219i de lucruri ciudate, cum ar fi sortarea prin bucle<\/a><\/noindex>).<\/p>\n

      \u201eC\u0103utare, c\u0103utare
      \nAt\u00e2t de mult timp
      \nC\u0103utare, c\u0103utare
      \nEu doar voiam s\u0103 dansez\u201d<\/i>
      \n\u2014 Luther Vandross, \u201eC\u0103utare\u201d (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Typo #2<\/h1>\n

      \nA doua gre\u0219eal\u0103 se afl\u0103 \u00een volumul 4A, \u201eAlgoritmi combinatori\u201d, partea 1. Pe pagina 60 este descris\u0103 o problem\u0103 legat\u0103 de programarea spectacolelor comediantului \u00een diferite cazinouri. Ca exemplu, sunt men\u021biona\u021bi c\u00e2\u021biva comedianti reali, inclusiv Lily Tomlin, Weird Al Yankovic \u0219i Robin Williams, care era \u00eenc\u0103 \u00een via\u021b\u0103 c\u00e2nd cartea a fost publicat\u0103. Knuth men\u021bioneaz\u0103 \u00eentotdeauna numele complete \u00een index, astfel \u00eenc\u00e2t Williams este men\u021bionat pe pagina 882 ca \u201eWilliams, Robin Mac-Laurin\u201d. Dar al doilea s\u0103u prenume se termin\u0103 cu \u201en\u201d \u0219i nu cu \u201em\u201d, adic\u0103 Mac-Laurin.<\/p>\n

      Mac-Laurin este numele de familie al mamei sale. Ea a fost str\u0103-str\u0103nepoata lui Anselm Joseph Mac-Laurin, al 34-lea guvernator al Mississippi-ului. Se pare c\u0103 mandatul s\u0103u nu a fost marcat de nimic bun. Din carte \u201eMississippi: Istorie\u201d<\/a><\/noindex>:<\/p>\n

      \u201eCel mai important eveniment din timpul administra\u021biei lui Mac-Laurin a fost declara\u021bia de r\u0103zboi a Statelor Unite \u00eempotriva Spaniei \u00een prim\u0103vara anului 1898... Din p\u0103cate, r\u0103zboiul a dat poate ocazia unor func\u021bionari publici s\u0103 practice mit\u0103. Mac-Laurin a fost acuzat de diverse practici discutabile, inclusiv nepotism \u0219i abuz excesiv de putere \u00een ceea ce prive\u0219te gra\u021bierea. \u00cen epoca mi\u0219c\u0103rii pentru temperan\u021b\u0103, criticii l-au acuzat pe guvernator de alcoolism, ceea ce el a recunoscut public.\u201d<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Eroare istoric\u0103<\/h1>\n

      \nS\u0103 examin\u0103m algoritmul tradi\u021bional de \u00eenmul\u021bire<\/b> din programa \u0219colar\u0103. C\u00e2te opera\u021bii de \u00eenmul\u021bire cu un singur digit necesit\u0103? S\u0103 presupunem c\u0103 \u00eenmul\u021bi\u021bi \"Am-digit number \"Am pe \"Am-digit \"Am. Mai \u00eent\u00e2i, \u00eenmul\u021bi\u021bi prima cifr\u0103 \"Am cu fiecare cifr\u0103 \"Am pe r\u00e2nd. Apoi \u00eenmul\u021bi\u021bi a doua cifr\u0103 \"Am cu fiecare cifr\u0103 \"Am pe r\u00e2nd \u0219i a\u0219a mai departe, p\u00e2n\u0103 trece\u021bi prin toate cifrele \"Am. Astfel, \u00eenmul\u021birea tradi\u021bional\u0103 necesit\u0103 \"Am \u00eenmul\u021biri primitive. \u00cen special, \u00eenmul\u021birea a dou\u0103 numere pe \"Am digit necesit\u0103 \"Am \u00eenmul\u021biri cu un singur digit.<\/p>\n

      Este r\u0103u, dar procesul poate fi optimizat printr-o metod\u0103 dezvoltat\u0103 de matematicianul sovietic Anatoliy Alexeyevich Karatsuba. S\u0103 presupunem c\u0103 \"Am \u0219i \"Am\u00a0- sunt numere zecimale de dou\u0103 cifre; adic\u0103 exist\u0103 numere \"Am, \"Am, \"Am, \"Am astfel \u00eenc\u00e2t \"Am \u0219i \"Am (generalizarea acestui algoritm pentru cifre mai mari necesit\u0103 anumite manevre; de\u0219i nu este foarte complicat, pentru a nu gre\u0219i \u00een detalii, mai bine r\u0103m\u00e2n la un exemplu simplu). Atunci \"Am, \"Am, \"Am. \u00cenmul\u021birea binomilor d\u0103 \"Am. P\u00e2n\u0103 acum, avem \u00een continuare \"Am \u00eenmul\u021biri cu un singur digit: \"Am, \"Am, \"Am, \"Am. Acum s\u0103 adun\u0103m \u0219i s\u0103 sc\u0103dem \"Am. Dup\u0103 c\u00e2teva permut\u0103ri, pe care le voi l\u0103sa ca exerci\u021biu pentru cititor, se ob\u021bine \"Am\u00a0\u2014 doar trei multiplic\u0103ri de un singur digit! (Exist\u0103 anumi\u021bi coeficien\u021bi constan\u021bi, dar ace\u0219tia pot fi calcula\u021bi doar prin adunare \u0219i deplasare de cifre).<\/p>\n

      Nu cere dovezi, dar algoritmul Karatsuba<\/b> (generalizat recursiv din exemplul de mai sus) \u00eembun\u0103t\u0103\u021be\u0219te metoda tradi\u021bional\u0103 de multiplicare cu \"Am opera\u021bii p\u00e2n\u0103 la \"Am. A\u0219adar, observa\u021bi c\u0103 este o \u00eembun\u0103t\u0103\u021bire real\u0103 a algoritmului, nu o optimizare pentru calcule mentale. De fapt, algoritmul nu este potrivit pentru a fi utilizat \u00een minte, deoarece necesit\u0103 cheltuieli mari pentru opera\u021bii recursive. \u00cen plus, efectul nu va deveni evident dec\u00e2t c\u00e2nd numerele devin suficient de mari (din fericire, \u00een locul algoritmului Karatsuba au ap\u0103rut metode \u0219i mai rapide: \u00een martie 2019 a fost publicat un algoritm care necesit\u0103 doar n log n<\/i><\/a><\/noindex> multiplic\u0103ri; accelerarea se aplic\u0103 doar numerelor at\u00e2t de mari \u00eenc\u00e2t nu sunt imaginabile).<\/p>\n

      Acest algoritm este descris pe pagina 295 a celui de-al doilea volum \u201eAlgoritmi calcula\u021bi\u201d. Acolo, Knuth scrie: \u201eEste interesant c\u0103 aceast\u0103 idee a fost descoperit\u0103 abia \u00een 1962<\/b> anul\u201d, c\u00e2nd a fost publicat un articol care descria algoritmul Karatsuba. Dar! \u00cen 1995, Karatsuba a publicat un articol intitulat \u201eComplexitatea calculului\u201d, \u00een care afirm\u0103 c\u00e2teva lucruri: 1) \u00een jurul anului 1956, Kolmogorov a sugerat c\u0103 multiplicarea nu poate fi efectuat\u0103 \u00een mai pu\u021bin de \"Am pa\u0219i; 2) \u00een 1960<\/b> anul, Karatsuba a fost prezent la un seminar unde Kolmogorov a expus ipoteza sa n\u00b2. 3) \u201eExact \u00een urm\u0103 cu o s\u0103pt\u0103m\u00e2n\u0103\u201d Karatsuba a elaborat algoritmul \u201e\u00eemparte \u0219i st\u0103p\u00e2ne\u0219te\u201d; 4) \u00een 1962, Kolmogorov a scris \u0219i a publicat un articol \u00een numele lui Karatsuba<\/i> despre algoritm. \u201eAm aflat despre acest articol doar dup\u0103 ce a fost reprintat.\u201d<\/p>\n

      Astfel, eroarea const\u0103 \u00een faptul c\u0103 \u00een loc de 1962<\/i> trebuie s\u0103 fie men\u021bionat 1960<\/i> anul. Asta e tot.<\/p>\n

      Analiz\u0103<\/h1>\n

      \nC\u0103utarea erorilor nu necesita abilit\u0103\u021bi deosebite.<\/b><\/p>\n

        \n
      1. Prima eroare a fost at\u00e2t de banal\u0103 pe c\u00e2t se poate, \u0219i se afla \u00eentr-un loc relativ vizibil (\u00eenceputul capitolului). Orice idiot ar putea s\u0103 o g\u0103seasc\u0103; doar c\u0103 eu am fost acel idiot.\n<\/li>\n
      2. C\u0103utarea celei de-a doua gre\u0219eli tipografice a necesitat noroc \u0219i d\u0103ruire, dar nu abilit\u0103\u021bi. Indexul pentru \u201eWilliams\u201d se afl\u0103 pe penultima pagin\u0103 a volumului, o parte destul de vizibil\u0103 a c\u0103r\u021bii. Tocmai r\u0103sfoiam indexul (nu este at\u00e2t de r\u0103u pe c\u00e2t pare, deoarece \u00een indexurile lui Knuth sunt ascunse ou\u0103 de Pa\u0219te. De exemplu, exist\u0103 \u00eenregistr\u0103ri \u00een arab\u0103 \u0219i ebraic\u0103, ambele indic\u00e2nd pagina 66. Dar pe aceast\u0103 pagin\u0103 nu este men\u021bionat niciunul dintre limbile respective; \u00een schimb, se men\u021bioneaz\u0103 \u201elimbile care se citesc de la dreapta la st\u00e2nga\u201d). \u0218i aten\u021bia mi-a fost atras\u0103 de al doilea nume. Deoarece de obicei citesc Wikipedia, am verificat Robin Williams \u0219i am observat o discrepan\u021b\u0103.\n<\/li>\n
      3. Mi-a\u0219 dori s\u0103 pot spune c\u0103 am f\u0103cut o cercetare serioas\u0103 pentru a g\u0103si o gre\u0219eal\u0103 istoric\u0103, dar de fapt doar am aruncat o privire pe pagina Wikipedia despre algoritmul lui Karatsuba.<\/a><\/noindex>. \u00cen primele linii scrie: \u201eAlgoritmul lui Karatsuba este un algoritm de multiplicare rapid\u0103. A fost descoperit de Anatoli Karatsuba \u00een 1960 \u0219i publicat \u00een 1962\u201d. Dup\u0103 aceasta, nu a mai fost dec\u00e2t s\u0103 adun dou\u0103 \u0219i cu dou\u0103.<\/li>\n<\/ol>\n

        \n\u00cen viitor, mi-a\u0219 dori s\u0103 g\u0103sesc o gre\u0219eal\u0103 mai semnificativ\u0103, \u00een special \u00een codul lui Knuth. De asemenea, a\u0219 dori s\u0103 g\u0103sesc un bug \u00een primul volum \u201eAlgoritmi fundamentali\u201d. Poate c\u0103 a\u0219 fi g\u0103sit, dar biblioteca local\u0103 are dintr-un motiv oarecare doar volumele 2, 3 \u0219i 4A.<\/p>\n

        Fapte financiare:<\/b><\/p>\n