{"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\/novosti-interneta\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Mora nj\u00eb \u00e7ek nga Knut p\u00ebr 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 informatikes, i cili e intereson shum\u00eb sakt\u00ebsia e librave t\u00eb tij, duke ofruar nj\u00eb dollar hexadeci<\/b> ($2.56, 0x$1.00) p\u00ebr \u00e7do \u00abgabim\u00bb t\u00eb gjetur, ku nj\u00eb gabim konsiderohet gjith\u00e7ka q\u00eb \u00ebsht\u00eb \u00abteknikisht, historikisht, tipografikisht ose politikisht e gabuar\u00bb. Un\u00eb me t\u00eb v\u00ebrtet\u00eb doja t\u00eb merrja nj\u00eb \u00e7ek nga Knuth, k\u00ebshtu q\u00eb vendosa t\u00eb k\u00ebrkoja p\u00ebr gabime n\u00eb vepr\u00ebn e tij t\u00eb shk\u00eblqyer \u00abArt i Programimit\u00bb<\/b> (TAOCP). Arrita t\u00eb gjej tre. N\u00eb p\u00ebrputhje me fjal\u00ebn, Knuth d\u00ebrgoi nj\u00eb \u00e7ek p\u00ebr 0x$3.00<\/b>.<\/p>\n

\"Mora
\n
\nSi\u00e7 e shihni, ky nuk \u00ebsht\u00eb nj\u00eb \u00e7ek i v\u00ebrtet\u00eb. Disa koh\u00eb m\u00eb par\u00eb, Knuth d\u00ebrgonte \u00e7ek\u00eb t\u00eb v\u00ebrtet\u00eb, por e ndaloi n\u00eb vitin 2008 p\u00ebr shkak t\u00eb mashtimeve t\u00eb pand\u00ebrprera<\/a><\/noindex>. Tani ai d\u00ebrgon \u00abcertifikata depoziti personale\u00bb n\u00eb bank\u00ebn San Serrif<\/a><\/noindex> (BoSS). Ai thot\u00eb se \u00ebsht\u00eb gati t\u00eb d\u00ebrgoj\u00eb para t\u00eb v\u00ebrteta n\u00eb rast nevoje, por duket se \u00ebsht\u00eb shum\u00eb e mundimshme.
\n<\/a><\/noindex>
\nGjeta dy gabime tipografike dhe nj\u00eb gabim historik. Do t'i rendit ato sipas r\u00ebnie triviale.<\/p>\n

Gabimi tipografik Nr. 1<\/h1>\n

\nGabimi i par\u00eb \u2014 n\u00eb faqe 392 t\u00eb v\u00ebllimit t\u00eb tret\u00eb \u00abKlasifikimi dhe K\u00ebrkimi\u00bb, rreshti i tet\u00eb lart: \u00abPas nj\u00eb k\u00ebrkimi t\u00eb pasuksessh\u00ebm, ndonj\u00ebher\u00eb (sometime) \u00ebsht\u00eb e d\u00ebshirueshme t\u00eb futni nj\u00eb rekord t\u00eb 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. Problemi \u00ebsht\u00eb se n\u00eb vend t\u00eb ndonj\u00ebher\u00eb<\/i><\/b> duhet t\u00eb jet\u00eb ndonj\u00ebher\u00eb<\/i><\/b>.<\/p>\n

Sigurisht, nuk ka asgj\u00eb t\u00eb \u00e7uditshme n\u00eb nj\u00eb gabim t\u00eb till\u00eb. N\u00eb k\u00ebt\u00eb artikull do t\u00eb ket\u00eb disa gabime shtypi (s'ka \u00e7mime p\u00ebr gjetjen e tyre). Ajo q\u00eb \u00ebsht\u00eb v\u00ebrtet e \u00e7uditshme \u00ebsht\u00eb se nuk jan\u00eb v\u00ebn\u00eb re p\u00ebr kaq gjat\u00eb. Faqja 392 nuk \u00ebsht\u00eb e fshehur thell\u00eb n\u00eb seksionin p\u00ebr matematik\u00ebn, kjo \u00ebsht\u00eb faqja e par\u00eb<\/b> e kapitullit t\u00eb gjasht\u00eb \"K\u00ebrkimi\"! Mund t\u00eb jet\u00eb nj\u00eb nga seksionet m\u00eb t\u00eb lexuara t\u00eb librit. N\u00eb teori, aty duhet t\u00eb ket\u00eb m\u00eb pak gabime, por jo.<\/p>\n

P\u00ebr m\u00eb tep\u00ebr, n\u00ebse ndonj\u00ebher\u00eb keni menduar t\u00eb lexoni TAOCP, provoni. Shum\u00eb do t\u00eb thon\u00eb se kjo \u00ebsht\u00eb nj\u00eb manual<\/b>, jo e destinuar p\u00ebr lexim t\u00eb drejtp\u00ebrdrejt\u00eb, por kjo \u00ebsht\u00eb e v\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 lexueshm\u00ebrin\u00eb \u00ebsht\u00eb v\u00ebshtir\u00ebsia e matematik\u00ebs. Megjithat\u00eb, ka nj\u00eb zgjidhje t\u00eb thjesht\u00eb: lexoni derisa t\u00eb arrini te matematika q\u00eb nuk e kuptoni, kaloni at\u00eb dhe hapni seksionin tjet\u00ebr q\u00eb mund t\u00eb kuptoni. Duke lexuar k\u00ebshtu, un\u00eb kaloj t\u00eb pakt\u00ebn 80% t\u00eb librit, por 20% e tjera jan\u00eb t\u00eb shk\u00eblqyera!<\/p>\n

Po ashtu thuhet se TAOCP nuk \u00ebsht\u00eb e r\u00ebnd\u00ebsishme<\/b>, \u00ebsht\u00eb e vjet\u00ebr ose ndryshe e pap\u00ebrshtatshme p\u00ebr \"programimin e v\u00ebrtet\u00eb\". Kjo \u00ebsht\u00eb gjithashtu e pav\u00ebrtet\u00eb. P\u00ebr shembull, n\u00eb seksionin e par\u00eb pas hyrjes shqyrtohet gjetja e nj\u00eb elementi n\u00eb nj\u00eb array t\u00eb pang sorted. Algoritmi m\u00eb i thjesht\u00eb \u00ebsht\u00eb i njohur p\u00ebr t\u00eb gjith\u00eb programuesit. Aktivizoni treguesin n\u00eb fillim t\u00eb array, 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 i d\u00ebshiruar. N\u00ebse po, e kthejm\u00eb at\u00eb; n\u00eb t\u00eb kund\u00ebrt\u00ebn\n<\/li>\n
  2. Kontrolloni n\u00ebse treguesi \u00ebsht\u00eb jasht\u00eb kufijve t\u00eb array. N\u00ebse po, kthejm\u00eb nj\u00eb gabim; n\u00eb t\u00eb kund\u00ebrt\u00ebn\n<\/li>\n
  3. Rritni treguesin dhe vazhdoni.<\/li>\n<\/ol>\n

    \nTani le t\u00eb shqyrtojm\u00eb: sa kontrolle kufij k\u00ebrkon ky algorit\u00ebm, n\u00eb mesatare? N\u00eb rastin m\u00eb t\u00eb keq, kur array nuk p\u00ebrmban elementin, p\u00ebr \u00e7do element n\u00eb list\u00eb do t\u00eb jet\u00eb e nevojshme nj\u00eb kontroll, dhe n\u00eb mesatare do t\u00eb jet\u00eb di\u00e7ka si \"Mora. Nj\u00eb algorit\u00ebm m\u00eb i men\u00e7ur i k\u00ebrkimit mund t\u00eb ket\u00eb vet\u00ebm nj\u00eb kontroll kufiri. Shtoni elementin e nevojsh\u00ebm n\u00eb fund t\u00eb array, pastaj aktivizoni treguesin n\u00eb fillim t\u00eb array 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 \u00ebsht\u00eb k\u00ebshtu, kthejeni p\u00ebrgjigjen, n\u00ebse treguesi \u00ebsht\u00eb brenda masivit, ose nj\u00eb gabim, n\u00ebse nuk \u00ebsht\u00eb. P\u00ebrndryshe\n<\/li>\n
    2. Rritni treguesin dhe vazhdoni.<\/li>\n<\/ol>\n

      \nN\u00eb \u00e7do rast, elementi do t\u00eb gjendet patjet\u00ebr, dhe kontrolli 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, madje edhe p\u00ebr nj\u00eb programist fillestar. Ndoshta nuk mund t\u00eb flas p\u00ebr r\u00ebnd\u00ebsin\u00eb e k\u00ebsaj pune p\u00ebr t\u00eb tjer\u00ebt, por un\u00eb arrita ta aplikoj k\u00ebt\u00eb men\u00e7uri menj\u00ebher\u00eb n\u00eb kodin tim personal dhe profesional. Libri TAOCP \u00ebsht\u00eb plot me perla t\u00eb tilla (t\u00eb drejtat e drejt\u00ebsis\u00eb, aty ka shum\u00eb gj\u00ebra t\u00eb \u00e7uditshme si renditja me flluska<\/a><\/noindex>).<\/p>\n

      \u00abK\u00ebrkoni, k\u00ebrkoni
      \nKa shum\u00eb koh\u00eb
      \nK\u00ebrkoni, k\u00ebrkoni
      \nUn\u00eb thjesht doja t\u00eb vallzosh\u00bb<\/i>
      \n\u2014 Luther Vandross, \u00abK\u00ebrkoni\u00bb (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 problem rreth planifikimit t\u00eb paraqitjeve t\u00eb komik\u00ebve n\u00eb kazino t\u00eb ndryshme. Si shembuj p\u00ebrmenden disa komik\u00eb real\u00eb, p\u00ebrfshir\u00eb Lily Tomlin, \"Weird Al\" Yankovic dhe Robin Williams, i cili ishte ende gjall\u00eb kur doli libri. Knuth gjithmon\u00eb jep emrat e plota n\u00eb indekse, pra Williams p\u00ebrmendet n\u00eb faqen 882 si \"Williams, Robin Mac-Lorin\". Por emri i tij i dyt\u00eb p\u00ebrfundon me \"n\", dhe jo me \"m\", pra Mac-Lorin.<\/p>\n

      Mac-Lorin \u00ebsht\u00eb mbiemri i vajz\u00ebris\u00eb s\u00eb n\u00ebn\u00ebs s\u00eb tij. Ajo ishte pasardh\u00ebse e Anselm Joseph Mac-Lorin, guvernatorit t\u00eb 34-t\u00eb t\u00eb Mississippi. Qeverisja e 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

      \u00abNgjarja m\u00eb e r\u00ebnd\u00ebsishme gjat\u00eb administrat\u00ebs McLorin ishte shpallja e luft\u00ebs nga Shtetet e Bashkuara ndaj Spanj\u00ebs n\u00eb pranver\u00ebn e vitit 1898\u2026 Fatkeq\u00ebsisht, lufta ndoshta i dha disa zyrtar\u00ebve shtet\u00ebror\u00eb mund\u00ebsin\u00eb p\u00ebr t\u00eb praktikuar korrupsionin. McLorin u akuzua p\u00ebr praktika t\u00eb dyshimta, duke p\u00ebrfshir\u00eb nepotizmin dhe p\u00ebrdorimin e tep\u00ebrt t\u00eb fuqive t\u00eb faljes. N\u00eb epok\u00ebn e l\u00ebvizjes p\u00ebr abstimin, kritik\u00ebt e akuzuan guvernatorin p\u00ebr alkooliz\u00ebm, t\u00eb cilin ai e pranoi publikisht\u00bb.<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Gabimi historik<\/h1>\n

      \nLe t\u00eb shqyrtojm\u00eb algoritmi tradicional i shum\u00ebzimit<\/b> nga programi shkollor. Sa operacione nj\u00ebsh esht\u00eb e nevojshme? Supozoni se po shum\u00ebzoni \"Mora-numrin me nj\u00eb shif\u00ebr \"Mora n\u00eb \"Mora-num\u00ebri me nj\u00eb shif\u00ebr \"Mora. S\u00eb pari, shum\u00ebzoni shifr\u00ebn e par\u00eb \"Mora me \u00e7do shif\u00ebr \"Mora n\u00eb radh\u00eb. Pastaj, shum\u00ebzoni shifr\u00ebn e dyt\u00eb \"Mora me \u00e7do shif\u00ebr \"Mora n\u00eb radh\u00eb dhe k\u00ebshtu me radh\u00eb, derisa t\u00eb kaloni p\u00ebrmes t\u00eb gjitha shifrave \"Mora. K\u00ebshtu, shumzimi tradicional k\u00ebrkon \"Mora shum\u00ebzime primare. N\u00eb ve\u00e7anti, shum\u00ebzimi i dy numrave me \"Mora shifra k\u00ebrkon \"Mora shum\u00ebzime nj\u00ebsh.<\/p>\n

      Kjo \u00ebsht\u00eb e keqe, por procesin mund ta optimizoni duke p\u00ebrdorur metod\u00ebn e zhvilluar nga matematicieni sovjetik Anatoly Alexeyevich Karatsuba. Le t\u00eb supozojm\u00eb se \"Mora dhe \"Mora\u00a0\u2014 numrat dhjetor\u00eb me dy shifra; pra ekzistojn\u00eb numra \"Mora, \"Mora, \"Mora, \"Mora t\u00eb till\u00eb q\u00eb \"Mora dhe \"Mora (zgjerimi i k\u00ebtij algoritmi p\u00ebr numra m\u00eb t\u00eb m\u00ebdhenj k\u00ebrkon disa manipulasione; ndon\u00ebse kjo nuk \u00ebsht\u00eb shum\u00eb e komplikuar, p\u00ebr t\u00eb mos gabuar n\u00eb detaje, do t\u00eb preferoja t\u00eb q\u00ebndroja n\u00eb nj\u00eb shembull t\u00eb thjesht\u00eb). At\u00ebher\u00eb \"Mora, \"Mora, \"Mora. Shum\u00ebzimi i dy-bin\u00ebve jep \"Mora. Deri m\u00eb tani ne ende kemi \"Mora shum\u00ebzime nj\u00eb-shifrore: \"Mora, \"Mora, \"Mora, \"Mora. Tani le t\u00eb shtojm\u00eb dhe heqim \"Mora. Pas disa rregullimeve, t\u00eb cilat do t'i l\u00eb si ushtrim p\u00ebr lexuesin, rezulton \"Mora\u00a0\u2014 vet\u00ebm tre shum\u00ebzime nj\u00eb-shifrore! (Ka disa koeficient\u00eb t\u00eb vazhduesh\u00ebm, por ato mund t\u00eb llogariten vet\u00ebm p\u00ebrmes shtimit dhe shifrave t\u00eb zhvendosura).<\/p>\n

      Mos k\u00ebrkoni prova, por algoritmi i Karatsub\u00ebs<\/b> (i gjeneruar n\u00eb m\u00ebnyr\u00eb rekursive nga shembulli i m\u00ebsip\u00ebrm) p\u00ebrmir\u00ebson metod\u00ebn tradicionale t\u00eb shum\u00ebzimit nga \"Mora operacione deri n\u00eb \"Mora. Vini re se \u00ebsht\u00eb nj\u00eb p\u00ebrmir\u00ebsim real i algoritmit, e jo nj\u00eb optimizim p\u00ebr llogaritjet n\u00eb mendje. N\u00eb t\u00eb v\u00ebrtet\u00eb, algoritmi nuk \u00ebsht\u00eb i p\u00ebrshtatsh\u00ebm p\u00ebr llogaritjet n\u00eb mendje, pasi k\u00ebrkon kosto t\u00eb m\u00ebdha p\u00ebr operacionet rekurzive. P\u00ebr m\u00eb tep\u00ebr, efekti do t\u00eb shfaqet plot\u00ebsisht vet\u00ebm kur numrat t\u00eb jen\u00eb mjaft t\u00eb m\u00ebdhenj (me fat, n\u00eb vend t\u00eb algoritmit t\u00eb Karatsub\u00ebs, jan\u00eb zbuluar metoda edhe m\u00eb t\u00eb shpejta: n\u00eb mars 2019 u publikua nj\u00eb algoritem q\u00eb k\u00ebrkon vet\u00ebm n log n<\/i><\/a><\/noindex> shum\u00ebzimesh; p\u00ebrshpejtimi \u00ebsht\u00eb i aplikuesh\u00ebm vet\u00ebm p\u00ebr numra t\u00eb pabesuesh\u00ebm t\u00eb m\u00ebdhenj).<\/p>\n

      Ky algorit\u00ebm p\u00ebrshkruhet n\u00eb faqen 295 t\u00eb volumit t\u00eb dyt\u00eb t\u00eb \u00abAlgoritmet e fituara\u00bb. Aty Knut shkruan: \u00ab\u00cbsht\u00eb interesante se kjo ide u zbulua vet\u00ebm n\u00eb 1962<\/b> vitin\u00bb, kur u publikua nj\u00eb artikull q\u00eb p\u00ebrshkruan algoritmin e Karatsub\u00ebs. Por! N\u00eb 1995, Karatsuba publikoi nj\u00eb artikull t\u00eb titulluar \u00abKompleksiteti i llogaritjeve\u00bb, ku ai p\u00ebrmend disa gj\u00ebra: 1) rreth vitit 1956 Kolmogorov supozoi se shumzimi nuk mund t\u00eb realizohet p\u00ebr m\u00eb pak se \"Mora hapa; 2) n\u00eb 1960<\/b> N\u00eb vitin 1962, Karacuba mori pjes\u00eb n\u00eb nj\u00eb seminar ku Kolmogorov paraqiti hipotez\u00ebn e tij n\u00b2. 3) \"Sakt\u00ebsisht nj\u00eb jav\u00eb\" Karacuba zhvilloi algoritmin \"ndaj dhe sundo\"; 4) n\u00eb vitin 1962 Kolmogorov shkroi dhe publikoi nj\u00eb artikull n\u00eb em\u00ebr t\u00eb Karacub\u00ebs<\/i> me p\u00ebrshkrimin e algoritmit. \"Mora vesh p\u00ebr k\u00ebt\u00eb artikull vet\u00ebm pasi e ribotuan\".<\/p>\n

      K\u00ebshtu, gabimi p\u00ebrb\u00ebhet nga fakti q\u00eb n\u00eb vend t\u00eb 1962<\/i> duhej t\u00eb ishte e specifikuar 1960<\/i> viti. K\u00ebtu e gjith\u00eb historia.<\/p>\n

      Analiza<\/h1>\n

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

        \n
      1. Gabimi i par\u00eb ishte aq banal sa ishte e mundur dhe ndodhej n\u00eb nj\u00eb vend relativisht t\u00eb duksh\u00ebm (fillimi i kapitullit). Cilido idiot do ta kishte gjetur at\u00eb; thjesht, un\u00eb isha ai idiot.\n<\/li>\n
      2. Gjetja e gabimeve t\u00eb dyta k\u00ebrkonte fat dhe p\u00ebrpjekje, por jo aft\u00ebsi. Indeksi p\u00ebr \"Williams\" ndodhet n\u00eb faqen parafund e librit, nj\u00eb pjes\u00eb e dukshme e librit. Un\u00eb po shfletoja sakt\u00ebsisht indeksin (nuk \u00ebsht\u00eb aq e keqe sa duket, pasi n\u00eb indekset e Knuth jan\u00eb fshehur vez\u00eb Pashke. P\u00ebr shembull, atje ka sh\u00ebnime n\u00eb arabisht dhe hebraisht, dhe t\u00eb dyja tregojn\u00eb tek faqja 66. Por n\u00eb k\u00ebt\u00eb faqe nuk p\u00ebrmendet asnj\u00eb nga k\u00ebto gjuh\u00eb; p\u00ebrkundrazi, p\u00ebrmendet \"gjuh\u00ebt q\u00eb lexohen nga e djathta n\u00eb t\u00eb majt\u00eb\"). Dhe v\u00ebmendja ime u t\u00ebrhoq nga emri i dyt\u00eb. Duke qen\u00eb se zakonisht lexoj Wikipedian, kontrollova Robin Williams dhe vura re nj\u00eb mosmarr\u00ebveshje.\n<\/li>\n
      3. Do doja t\u00eb thoja se kam b\u00ebr\u00eb nj\u00eb hulumtim t\u00eb r\u00ebnd\u00ebsish\u00ebm p\u00ebr t\u00eb gjetur nj\u00eb gabim historik, por n\u00eb t\u00eb v\u00ebrtet\u00eb thjesht shikova faqen e Wikipedias p\u00ebr algoritmin e Karatsub\u00ebs<\/a><\/noindex>. N\u00eb rreshtat e par\u00eb shkruhet: \"Algoritmi i Karatsub\u00ebs \u00ebsht\u00eb nj\u00eb algorit\u00ebm p\u00ebr shumim t\u00eb shpejt\u00eb. U zbulua nga Anatol Karatsuba n\u00eb vitin 1960 dhe u publikua n\u00eb vitin 1962\". Pas k\u00ebsaj nuk mbetej gj\u00eb tjet\u00ebr vet\u00ebm se t\u00eb shtoja 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 t\u00eb r\u00ebnd\u00ebsish\u00ebm, ve\u00e7an\u00ebrisht n\u00eb kodin e Knuth. Do t\u00eb doja gjithashtu t\u00eb gjeja nj\u00eb bug n\u00eb v\u00ebllimin e par\u00eb t\u00eb \"Algoritmet Fundamentale\". Ndoshta do ta kisha gjetur, por p\u00ebr ndonj\u00eb arsye, n\u00eb bibliotek\u00ebn lokale ka vet\u00ebm v\u00ebllimet 2, 3 dhe 4A.<\/p>\n

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