{"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\/sq\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Mora nga Knuth nj\u00eb \u00e7ek prej 0x$3,00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u2014 nj\u00eb shkenc\u00ebtar n\u00eb fush\u00ebn e informatik\u00ebs, i cili \u00ebsht\u00eb aq i kujdessh\u00ebm p\u00ebr sakt\u00ebsin\u00eb e librave t\u00eb tij sa q\u00eb ofron nj\u00eb dollar heksadecimal<\/b> ($2.56, 0x$1.00) p\u00ebr \u00e7do \"gabim\" t\u00eb gjetur, ku nj\u00eb gabim p\u00ebrkufizohet si gjith\u00e7ka q\u00eb \u00ebsht\u00eb \"teknikisht, historikisht, tipografikisht ose politikisht e gabuar\". Un\u00eb isha shum\u00eb i interesuar t\u00eb marr nj\u00eb \u00e7ek nga Knuth, k\u00ebshtu q\u00eb vendosa t\u00eb k\u00ebrkoj gabime n\u00eb vepr\u00ebn e tij t\u00eb jasht\u00ebzakonshme \"Arti i programimit\"<\/b> (TAOCP). Arrita t\u00eb gjej tri. V\u00ebrtet, Knuth m\u00eb d\u00ebrgoi nj\u00eb \u00e7ek p\u00ebr 0x$3.00<\/b>.<\/p>\n

\"Mora
\n
\nSi\u00e7 e shihni, kjo nuk \u00ebsht\u00eb nj\u00eb \u00e7ek i v\u00ebrtet\u00eb. M\u00eb par\u00eb, Knuth d\u00ebrgonte \u00e7eqe t\u00eb v\u00ebrteta, por e ndali k\u00ebt\u00eb n\u00eb vitin 2008 p\u00ebr shkak t\u00eb mashtimeve masive<\/a><\/noindex>. Tani ai d\u00ebrgon \"certifikata personale depozite\" n\u00eb bank\u00ebn San-Serif<\/a><\/noindex> (BoSS). Ai thot\u00eb se \u00ebsht\u00eb i gatsh\u00ebm t\u00eb d\u00ebrgoj\u00eb para t\u00eb v\u00ebrteta n\u00eb rast nevoje, por duket se \u00ebsht\u00eb shum\u00eb e lodhshme.
\n<\/a><\/noindex>
\nGjeta dy gabime shtypi dhe nj\u00eb gabim historik. Do t'i lista ato n\u00eb rendin e zvog\u00eblimit t\u00eb trivialitetit.<\/p>\n

Gabimi i shtypit nr. 1<\/h1>\n

\nGabimi i par\u00eb \u00ebsht\u00eb n\u00eb faqen 392 t\u00eb v\u00ebllimit t\u00eb tret\u00eb \"K\u00ebrkimi dhe renditja\", rreshti i tet\u00eb nga fundi: \"Pas nj\u00eb k\u00ebrkimi t\u00eb pasuksessh\u00ebm ndonj\u00ebher\u00eb (sometime) \u00ebsht\u00eb e d\u00ebshirueshme t\u00eb futet nj\u00eb regjistrim i ri n\u00eb tabel\u00eb, q\u00eb p\u00ebrmban K<\/i>; metodi q\u00eb e b\u00ebn k\u00ebt\u00eb quhet algoritmi i k\u00ebrkimit dhe futjes. Gabimi q\u00ebndron n\u00eb faktin se n\u00eb vend t\u00eb sometime<\/i><\/b> duhet t\u00eb jet\u00eb sometimes<\/i><\/b>.<\/p>\n

Sigurisht, nuk ka asgj\u00eb befasuese n\u00eb nj\u00eb gabim t\u00eb till\u00eb. Vet\u00ebm n\u00eb k\u00ebt\u00eb artikull padyshim se do t\u00eb gjenden disa gabime shtypi (pa shp\u00ebrblime p\u00ebr gjetjen e tyre). Ajo q\u00eb n\u00eb t\u00eb v\u00ebrtet\u00eb \u00ebsht\u00eb befasuese \u00ebsht\u00eb se si nuk u vun\u00eb re gjat\u00eb kaq shum\u00eb koh\u00ebs. Faqja 392 nuk \u00ebsht\u00eb thell\u00ebsisht e varrosur n\u00eb nj\u00eb seksion me matematik\u00eb, ajo \u00ebsht\u00eb faqja m\u00eb e par\u00eb<\/b> e kapitullit t\u00eb gjasht\u00eb \"K\u00ebrkimi\"! Ndoshta, nj\u00eb nga seksionet m\u00eb t\u00eb lexuara t\u00eb librit. Idealisht, aty duhet t\u00eb ket\u00eb m\u00eb pak gabime shtypi, por jo.<\/p>\n

P\u00ebr m\u00eb tep\u00ebr, n\u00ebse keni menduar ndonj\u00ebher\u00eb t\u00eb lexoni TAOCP, provoni. Shum\u00eb do t\u00eb thon\u00eb se kjo \u00ebsht\u00eb nj\u00eb udh\u00ebzues<\/b>, i pa p\u00ebrshtatsh\u00ebm p\u00ebr leximin e drejtp\u00ebrdrejt\u00eb, por kjo \u00ebsht\u00eb e pav\u00ebrtet\u00eb. Autori ka nj\u00eb pik\u00ebpamje t\u00eb qart\u00eb dhe nj\u00eb stil t\u00eb ve\u00e7ant\u00eb. E vetmja gj\u00eb q\u00eb pengon leht\u00ebsin\u00eb e leximit \u00ebsht\u00eb kompleksiteti i matematik\u00ebs. Megjithat\u00eb, ka nj\u00eb zgjidhje t\u00eb thjesht\u00eb: lexoni deri sa t\u00eb arrini te matematika q\u00eb nuk kuptoni, kaloni at\u00eb dhe hapni seksionin tjet\u00ebr q\u00eb mund t\u00eb kuptoni. Duke lexuar n\u00eb k\u00ebt\u00eb m\u00ebnyr\u00eb, un\u00eb kaloj t\u00eb pakt\u00ebn 80% t\u00eb librit, por 20% e tjera jan\u00eb t\u00eb mrekullueshme!<\/p>\n

Gjithashtu thuhet se TAOCP nuk \u00ebsht\u00eb relevante<\/b>, e ka skadoh\u00eb sa i p\u00ebrket \u00abprogramimit real\u00bb. Kjo gjithashtu \u00ebsht\u00eb e pav\u00ebrtet\u00eb. P\u00ebr shembull, n\u00eb seksionin e par\u00eb pas hyrjes, shqyrtohet k\u00ebrkimi i nj\u00eb elementi n\u00eb nj\u00eb masiv t\u00eb neshtuar. Algoritmi m\u00eb i thjesht\u00eb \u00ebsht\u00eb i njohur p\u00ebr \u00e7do programues. Filloni me treguesin n\u00eb fillim t\u00eb masivit, pastaj kryeni hapat e m\u00ebposht\u00ebm n\u00eb nj\u00eb cik\u00ebl:<\/p>\n

    \n
  1. Kontrolloni n\u00ebse elementi aktual \u00ebsht\u00eb ai q\u00eb d\u00ebshironi. N\u00ebse po, e kthejm\u00eb; p\u00ebrndryshe\n<\/li>\n
  2. Kontrolloni n\u00ebse treguesi \u00ebsht\u00eb jasht\u00eb masivit. N\u00ebse po, e kthejm\u00eb nj\u00eb gabim; p\u00ebrndryshe\n<\/li>\n
  3. Shtoni treguesin dhe vazhdoni.<\/li>\n<\/ol>\n

    \nTani le t\u00eb shqyrtojm\u00eb: sa kontrollime kufijesh k\u00ebrkon ky algorit\u00ebm, mesatarisht? N\u00eb rastin m\u00eb t\u00eb keq, kur masivi nuk p\u00ebrmban elementin, p\u00ebr \u00e7do element n\u00eb list\u00eb do t\u00eb k\u00ebrkohet nj\u00eb kontrollim, dhe mesatarisht do t\u00eb jet\u00eb di\u00e7ka e till\u00eb \"Mora. Nj\u00eb algorit\u00ebm m\u00eb i zgjuar i k\u00ebrkimit mund t\u00eb k\u00ebrkoj\u00eb vet\u00ebm nj\u00eb kontrollim kufiri. Shtoni elementin e d\u00ebshiruar n\u00eb fund t\u00eb masivit, pastaj filloni me treguesin n\u00eb fillim t\u00eb masivit dhe kryeni hapat e m\u00ebposht\u00ebm n\u00eb nj\u00eb cik\u00ebl:<\/p>\n

      \n
    1. Kontrolloni n\u00ebse elementi aktual \u00ebsht\u00eb ai q\u00eb d\u00ebshironi. N\u00ebse po, e kthejm\u00eb p\u00ebrgjigjen, n\u00ebse treguesi \u00ebsht\u00eb brenda masivit, ose nj\u00eb gabim, n\u00ebse jo. P\u00ebrndryshe\n<\/li>\n
    2. Shtoni treguesin dhe vazhdoni.<\/li>\n<\/ol>\n

      \nK\u00ebshtu ose ndryshe, elementi do t\u00eb gjendet me siguri, dhe kontrollimi i kufijve b\u00ebhet vet\u00ebm nj\u00eb her\u00eb, kur ndodh kjo. Kjo \u00ebsht\u00eb nj\u00eb ide e thell\u00eb, por mjaft e thjesht\u00eb edhe p\u00ebr programuesit fillestar\u00eb. Ndoshta nuk mund t\u00eb flas p\u00ebr relevanc\u00ebn e k\u00ebtij punimi p\u00ebr t\u00eb tjer\u00ebt, por un\u00eb menj\u00ebher\u00eb e aplikova k\u00ebt\u00eb men\u00e7uri si n\u00eb kodin tim personal ashtu edhe n\u00eb at\u00eb profesional. Libra TAOCP \u00ebsht\u00eb plot me kushte t\u00eb tilla (p\u00ebr t\u00eb qen\u00eb t\u00eb drejt\u00eb, ka shum\u00eb gj\u00ebra t\u00eb \u00e7uditshme aty, si sortimi me balona<\/a><\/noindex>).<\/p>\n

      \"K\u00ebrkim, k\u00ebrkim
      \nKa shum\u00eb koh\u00eb
      \nK\u00ebrkim, k\u00ebrkim
      \nUn\u00eb thjesht doja t\u00eb dansoja\"<\/i>
      \n- Luther Vandross, \"K\u00ebrkimi\" (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Gabimi nr. 2<\/h1>\n

      \nGabimi i dyt\u00eb \u00ebsht\u00eb n\u00eb v\u00ebllimin 4A, \"Algoritmet Kombinatorike\", pjesa 1. N\u00eb faqen 60 p\u00ebrshkruhet nj\u00eb detyr\u00eb p\u00ebr planifikimin e shfaqjeve t\u00eb komik\u00ebve n\u00eb kazino t\u00eb ndryshme. Si shembuj p\u00ebrmenden disa komik\u00eb t\u00eb v\u00ebrtet\u00eb, p\u00ebrfshir\u00eb Lily Tomlin, Weird Al Yankovic dhe Robin Williams, i cili ishte akoma gjall\u00eb kur doli libri. Knuth gjithmon\u00eb jep emrat e plot\u00eb n\u00eb indeks, prandaj Williams p\u00ebrmendet n\u00eb faqen 882 si \"Williams, Robin McLaurin\". Por emri i tij i dyt\u00eb p\u00ebrfundon me \"n\", jo me \"m\", pra McLaurin.<\/p>\n

      McLaurin \u00ebsht\u00eb mbiemri i vajz\u00ebris\u00eb s\u00eb n\u00ebn\u00ebs s\u00eb tij. Ajo ishte vash\u00eb e Anselm Joseph McLaurin, guvernatori i 34-t\u00eb i Mississippi. Sundimi i tij, duket, nuk mbeti n\u00eb kujtes\u00eb p\u00ebr ndonj\u00eb gj\u00eb t\u00eb mir\u00eb. Nga libri \"Mississippi: Historia\"<\/a><\/noindex>:<\/p>\n

      \"Ngjarja m\u00eb e r\u00ebnd\u00ebsishme gjat\u00eb administrat\u00ebs s\u00eb McLaurin ishte shpallja e luft\u00ebs nga Shtetet e Bashkuara kund\u00ebr Spanj\u00ebs n\u00eb pranver\u00ebn e vitit 1898\u2026 Fatkeq\u00ebsisht, lufta ndoshta u dha disa zyrtar\u00ebve t\u00eb shtetit mund\u00ebsin\u00eb p\u00ebr t\u00eb praktikuar korrupsionin. McLaurin u akuzua p\u00ebr praktika t\u00eb ndryshme t\u00eb dyshimta, p\u00ebrfshir\u00eb nepotizmin dhe p\u00ebrdorimin e tepruar t\u00eb t\u00eb drejtave p\u00ebr faljen. N\u00eb epok\u00ebn e l\u00ebvizjes p\u00ebr abstinenc\u00eb, kritik\u00ebt akuzuan guvernatorin p\u00ebr pirje alkooli, t\u00eb cil\u00ebn e pranoi publikisht.\"<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Gabimi Historik<\/h1>\n

      \nLe t\u00eb shqyrtojm\u00eb algoritmi tradicional i shum\u00ebzimit<\/b> nga programa shkollore. Sa k\u00ebrkon ai operacione shum\u00ebzimi me nj\u00eb cif\u00ebr? Le t\u00eb supozojm\u00eb se po shum\u00ebzoni \"Mora-cifr\u00ebn e numrit \"Mora n\u00eb \"Mora-cifrat \"Mora. S\u00eb pari, shum\u00ebzoni numrin e par\u00eb \"Mora me secil\u00ebn cif\u00ebr \"Mora nj\u00eb nga nj\u00eb. Pastaj shum\u00ebzoni numrin e dyt\u00eb \"Mora me secil\u00ebn cif\u00ebr \"Mora nj\u00eb nga nj\u00eb dhe k\u00ebshtu me radh\u00eb, derisa t\u00eb kaloni t\u00eb gjitha cifrat \"Mora. K\u00ebshtu, shum\u00ebzimi tradicional k\u00ebrkon \"Mora shum\u00ebzime primitive. N\u00eb ve\u00e7anti, shum\u00ebzimi i dy numrave sipas \"Mora cifrave k\u00ebrkon \"Mora shum\u00ebzime me nj\u00eb cif\u00ebr.<\/p>\n

      Kjo \u00ebsht\u00eb keq, por procesi mund t\u00eb optimizohet me an\u00eb t\u00eb nj\u00eb metode t\u00eb zhvilluar nga matematikani sovjetik Anatoly Alexeyevich Karatsuba. Le t\u00eb supozojm\u00eb se \"Mora dhe \"Mora\u00a0- numra dyshifror\u00eb decimal\u00eb; pra ekzistojn\u00eb numra \"Mora, \"Mora, \"Mora, \"Mora t\u00eb till\u00eb q\u00eb \"Mora dhe \"Mora (generalizimi i k\u00ebtij algoritmi p\u00ebr numra m\u00eb t\u00eb m\u00ebdhenj k\u00ebrkon disa manipulime; megjithat\u00eb kjo nuk \u00ebsht\u00eb aq e komplikuar, por p\u00ebr t\u00eb mos gabuar n\u00eb detaje, m\u00eb mir\u00eb t\u00eb q\u00ebndroj n\u00eb shembullin e thjesht\u00eb). At\u00ebher\u00eb \"Mora, \"Mora, \"Mora. Shum\u00ebzimi i dy binom\u00ebve jep \"Mora. N\u00eb k\u00ebt\u00eb moment, akoma kemi \"Mora shum\u00ebzime me nj\u00eb cif\u00ebr: \"Mora, \"Mora, \"Mora, \"Mora. Tani, le t\u00eb shtojm\u00eb dhe t\u00eb heqim \"Mora. Pas disa rregullime, q\u00eb do t'i l\u00eb si nj\u00eb ushtrim p\u00ebr lexuesin, rezulton \"Mora\u00a0\u2014 vet\u00ebm tri shum\u00ebzime me nj\u00eb shif\u00ebr! (Ka disa koeficient\u00eb konstant\u00eb, por ata mund t\u00eb llogariten vet\u00ebm me mbledhje dhe zhvendosje t\u00eb shifrave).<\/p>\n

      Mos k\u00ebrkoni d\u00ebshmi, por algoritmi i Karatsub\u00ebs<\/b> (i p\u00ebrgjith\u00ebsuar n\u00eb m\u00ebnyr\u00eb rekursive nga shembulli i m\u00ebsip\u00ebrm) p\u00ebrmir\u00ebson metod\u00ebn tradicionale t\u00eb shum\u00ebzimit nga \"Mora operacionet n\u00eb \"Mora. Vini re se ky \u00ebsht\u00eb nj\u00eb p\u00ebrmir\u00ebsim real i algoritmit, dhe jo optimizim p\u00ebr llogaritjet mendore. N\u00eb t\u00eb v\u00ebrtet\u00eb, algoritmi nuk \u00ebsht\u00eb i p\u00ebrshtatsh\u00ebm p\u00ebr llogaritje n\u00eb mend, pasi k\u00ebrkon shpenzime t\u00eb m\u00ebdha p\u00ebr operacionet rekursive. P\u00ebr m\u00eb tep\u00ebr, efekti do t\u00eb shfaqet plot\u00ebsisht vet\u00ebm kur numrat t\u00eb b\u00ebhen mjaft t\u00eb m\u00ebdhenj (p\u00ebr fat, n\u00eb vend t\u00eb algoritmit t\u00eb Karatsub\u00ebs erdh\u00ebn metoda edhe m\u00eb t\u00eb shpejta: n\u00eb mars 2019 u publikua nj\u00eb algorit\u00ebm q\u00eb k\u00ebrkon vet\u00ebm n log n<\/i><\/a><\/noindex> shum\u00ebzime; p\u00ebrshpejtimi \u00ebsht\u00eb i aplikuar vet\u00ebm p\u00ebr numra t\u00eb jasht\u00ebzakonsh\u00ebm t\u00eb m\u00ebdhenj).<\/p>\n

      Ky algorit\u00ebm \u00ebsht\u00eb p\u00ebrshkruar n\u00eb faqen 295 t\u00eb v\u00ebllimit t\u00eb dyt\u00eb \"Algoritmet e llogaritur\". Atje Knut shkruan: \"\u00cbsht\u00eb e \u00e7uditshme se k\u00ebt\u00eb ide e zbuluan vet\u00ebm n\u00eb 1962<\/b> vitin\", kur u publikua nj\u00eb artikull q\u00eb p\u00ebrshkruan algoritmin e Karatsub\u00ebs. Por! N\u00eb vitin 1995, Karatsuba publikoi nj\u00eb artikull \"Karakteshimi i llogaritjeve\", n\u00eb t\u00eb cilin thot\u00eb disa gj\u00ebra: 1) rreth vitit 1956, Kolmogorov supozoi se shum\u00ebzimi nuk mund t\u00eb kryhet n\u00eb m\u00eb pak se \"Mora hapa; 2) n\u00eb 1960<\/b> vitin, Karatsuba mori pjes\u00eb n\u00eb nj\u00eb seminar, ku Kolmogorov paraqiti hipotez\u00ebn e tij n\u00b2. 3) \"Pik\u00ebrisht p\u00ebr nj\u00eb jav\u00eb\" Karatsuba zhvilloi algoritmin \"ndaje dhe mbizot\u00ebro\"; 4) n\u00eb vitin 1962 Kolmogorov shkroi dhe publikoi nj\u00eb artikull n\u00eb em\u00ebr t\u00eb Karatsub\u00ebs<\/i> me p\u00ebrshkrimin e algoritmit. \"M\u00ebsoja p\u00ebr k\u00ebt\u00eb artikull vet\u00ebm pasi e ribotuan\".<\/p>\n

      Pra, gabimi \u00ebsht\u00eb se n\u00eb vend t\u00eb 1962<\/i> duhet t\u00eb p\u00ebrmendet 1960<\/i> viti. Kaq \u00ebsht\u00eb gjith\u00e7ka.<\/p>\n

      Analiza<\/h1>\n

      \nK\u00ebrkimi i gabimeve nuk k\u00ebrkonte ndonj\u00eb mjesht\u00ebri t\u00eb ve\u00e7ant\u00eb.<\/b><\/p>\n

        \n
      1. Gabimi i par\u00eb ishte aq banal sa mund t\u00eb jet\u00eb, dhe ishte n\u00eb nj\u00eb vend relativisht t\u00eb duksh\u00ebm (fillimi i kapitullit). \u00c7do idiot mund ta gjente at\u00eb; thjesht un\u00eb isha ai idiot.\n<\/li>\n
      2. K\u00ebrkimi i gabimit t\u00eb dyt\u00eb k\u00ebrkonte fat dhe p\u00ebrkushtim, por jo aft\u00ebsi. Indeksi p\u00ebr \"Williams\" ndodhet n\u00eb faqen e parafundit t\u00eb volumit, nj\u00eb pjes\u00eb e konsiderueshme e librit. Pash\u00eb pik\u00ebrisht indeksin (nuk \u00ebsht\u00eb aq keq sa duket, sepse n\u00eb indekset e Knuth-it jan\u00eb t\u00eb fshehura vez\u00ebt e Pashk\u00ebs. P\u00ebr shembull, ka regjistrime n\u00eb arabisht dhe hebraisht, dhe t\u00eb dy tregojn\u00eb p\u00ebr faqen 66. Por n\u00eb k\u00ebt\u00eb faqe nuk p\u00ebrmendet asnj\u00eb nga k\u00ebto gjuh\u00eb; p\u00ebrkundrazi, aty p\u00ebrmenden \"gjuhet q\u00eb lexohen nga e djathta n\u00eb t\u00eb majt\u00eb\"). Dhe v\u00ebmendjen time t\u00ebrhoqi emri i dyt\u00eb. Pasi zakonisht lexoj Wikipedia-n, kontrollova Robin Williams dhe pash\u00eb nj\u00eb mosmarr\u00ebveshje.\n<\/li>\n
      3. D\u00ebshiroja t\u00eb thosha se kam b\u00ebr\u00eb k\u00ebrkimin serioz p\u00ebr t\u00eb gjetur nj\u00eb gabim historik, por n\u00eb t\u00eb v\u00ebrtet\u00eb thjesht shikova faqen e Wikipedia-s p\u00ebr algoritmin Karatsuba.<\/a><\/noindex>N\u00eb rreshtat e par\u00eb shkruhet: \"Algoritmi i Karatsub\u00ebs \u00ebsht\u00eb nj\u00eb algorit\u00ebm shum\u00eb t\u00eb shpejt\u00eb p\u00ebr shum\u00ebzim. U zbulua nga Anatoli Karatsuba n\u00eb vitin 1960 dhe u publikua n\u00eb vitin 1962\". Pas k\u00ebsaj, mbetej vet\u00ebm t\u00eb shtosh dy her\u00eb dy.<\/li>\n<\/ol>\n

        \nN\u00eb t\u00eb ardhmen do t\u00eb doja t\u00eb gjeja nj\u00eb gabim m\u00eb thelb\u00ebsor, ve\u00e7an\u00ebrisht n\u00eb kodin e Knuth-it. Do doja gjithashtu t\u00eb gjeja nj\u00eb gabim n\u00eb volumit t\u00eb par\u00eb \"Algoritmet themelore\". Ndoshta do t\u00eb kisha gjetur, por n\u00eb bibliotek\u00ebn lokale p\u00ebr nj\u00eb arsye, ka vet\u00ebm volumin 2, 3 dhe 4A.<\/p>\n

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