{"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\/et\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Ma sain Knutilt t\u0161eki summas 0x$3,00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u2014 informaatika alal teadlane, kes hoolib oma raamatute t\u00e4psusest nii palju, et pakub \u00fche kuuenda dollari<\/b> ($2,56, 0x$1,00) iga leitud \u00abvea\u00bb eest, kus veaks loetakse k\u00f5ik, mis on \u00abtehniliselt, ajalooliselt, t\u00fcpograafiliselt v\u00f5i poliitiliselt vale\u00bb. Ma t\u00f5esti tahtsin Knuthilt t\u0161ekki saada, seet\u00f5ttu otsustasin otsida vigu tema silmapaistvas t\u00f6\u00f6s \u00abProgrammeerm kunst\u00bb<\/b> (TAOCP). \u00d5nnestus leida kolm. T\u00f5tt-\u00f6elda, Knuth saatis t\u0161eki summas 0x$3,00<\/b>.<\/p>\n

\"Ma
\n
\nNagu n\u00e4ete, ei ole see t\u00f5eline k\u0161ek. Varem saatis Knuth t\u00f5elisi t\u0161ekke, kuid l\u00f5petas selle 2008. aastal \u00fclem\u00e4\u00e4rase pettuse t\u00f5ttu<\/a><\/noindex>. N\u00fc\u00fcd saadab ta \u00abisiklikke hoiustamise sertifikaate\u00bb San-Seriifi pangas<\/a><\/noindex> (BoSS). Ta \u00fctleb, et on valmis vajadusel t\u00f5elisi raha saatma, kuid tundub, et see on liiga vaevaline.
\n<\/a><\/noindex>
\nLeidsin kaks tr\u00fckiviga ja \u00fche ajaloolise vea. Loetlen need kahanevas triviaaluse j\u00e4rjekorras.<\/p>\n

Tr\u00fckiviga nr 1<\/h1>\n

\nEsimene tr\u00fckiviga on kolmanda k\u00f6ite, \u00abSorteerimine ja otsing\u00bb lehe 392, kaheksas rida alt: \u00abP\u00e4rast eba\u00f5nnestunud otsingut on m\u00f5nikord (sometime) soovitatav tabelisse sisestada uus kirje, mis sisaldab K<\/i>; meetod, mis seda teeb, nimetatakse otsing ja sisestamise algoritmiks. Viga seisneb selles, et \u00absometime\u00bb asemel peaks olema sometimes<\/i><\/b> peab olema Loomulikult pole sellises veas midagi \u00fcllatavat. Ainult selles artiklis leidub kindlasti mitmeid tr\u00fckivigu (tasu nende leidmise eest ei ole). Mis on tegelikult \u00fcllatav, on see, et seda pole nii kaua m\u00e4rgatud. Leht 392 ei asu s\u00fcgaval matemaatika jaotises, see on<\/i><\/b>.<\/p>\n

kogu kuuendast peat\u00fckist \u00abOtsing\u00bb! V\u00f5ib-olla on see \u00fcks loetavamaid jaotisi raames. Idee kohaselt peaks seal olema k\u00f5ige v\u00e4hem tr\u00fckivigu, kuid ei ole. Muide, kui olete kunagi m\u00f5elnud TAOCP lugemisele, proovige. Paljud \u00fctlevad, et see on<\/b> viiteraamat<\/p>\n

, mis ei ole m\u00f5eldud otse lugemiseks, kuid see ei ole t\u00f5si. Autoril on selge seisukoht ja isikup\u00e4rane stiil. Ainus, mis loetavust takistab, on matemaatika keerukus. Kuid sellele on lihtne lahendus: loe, kuni j\u00f5uad matemaatikani, mida sa ei m\u00f5ista, j\u00e4ta see vahele ja avaa j\u00e4rgmine jaotis, mida saad m\u00f5ista. Sellisel viisil lugedes j\u00e4tan ma vahele v\u00e4hemalt 80% raamatust, kuid \u00fclej\u00e4\u00e4nud 20% on suurep\u00e4rased! Samuti \u00f6eldakse, et TAOCP<\/b>ei ole asjakohane<\/p>\n

, ei ole reaalne<\/b>, on vananenud v\u00f5i muul viisil mitteoluline \u00abreaalse programmeerimise\u00bb kontekstis. See pole ka t\u00f5si. N\u00e4iteks k\u00e4sitletakse esimeses jaotises p\u00e4rast sissejuhatust elementide otsimist sorteerimata massiivis. Lihtsaim algoritm on k\u00f5ikidele programmeerijatele tuttav. K\u00e4ivitage suunaja massiivi alguses, seej\u00e4rel tehke allolevaid toiminguid ts\u00fcklis:<\/p>\n

    \n
  1. Kontrollige, kas praegune element on soovitud. Kui jah, tagastage see; vastasel juhul\n<\/li>\n
  2. Kontrollige, kas suunaja on massiivi piiridest v\u00e4ljas. Kui jah, tagastage viga; vastasel juhul\n<\/li>\n
  3. Suurendage suunajat ja j\u00e4tkake.<\/li>\n<\/ol>\n

    \nN\u00fc\u00fcd vaatame: kui palju piiri kontrollimist see algoritm keskmiselt n\u00f5uab? Halvimal juhul, kui massiivis ei ole elementi, vajab iga elemendi puhul loendis \u00fchte kontrolli ning keskmiselt on see midagi sellist \"Ma. Nutikam otsingu algoritm v\u00f5ib vajada vaid \u00fchte piiri kontrolli. Lisage vajalik element massiivi l\u00f5ppu, seej\u00e4rel k\u00e4ivitage suunaja massiivi alguses ja tehke allolevaid toiminguid ts\u00fcklis:<\/p>\n

      \n
    1. Kontrollige, kas praegune element on soovitud. Kui jah, tagastage vastus, kui suunaja on massiivi piirides, v\u00f5i viga, kui see pole nii. Vastasel juhul\n<\/li>\n
    2. Suurendage suunajat ja j\u00e4tkake.<\/li>\n<\/ol>\n

      \nNii v\u00f5i naa, element leidub kindlasti ning piiri kontrollimise teeb ainult \u00fche korra, kui see on juhtunud. See on s\u00fcgav idee, kuid piisavalt lihtne ka algaja programmeerija jaoks. Ilmselt ei saa ma r\u00e4\u00e4kida selle t\u00f6\u00f6 relevantsusest teiste jaoks, kuid mul \u00f5nnestus koheselt seda tarkust rakendada nii isiklikus kui ka ametialases koodis. RAAMAT TAOCP on t\u00e4is selliseid p\u00e4rleid (aususe nimel, seal on ka palju veidraid asju, nagu mullivannide sorteering<\/a><\/noindex>).<\/p>\n

      \u00abOtsimine, otsimine
      \nNii kaua
      \nOtsimine, otsimine
      \nMa tahtsin lihtsalt tantsida\u00bb<\/i>
      \n\u2014 Luther Vandross, \u00abOtsimine\u00bb (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Tr\u00fckiviga nr 2<\/h1>\n

      \nTeine viga on osas 4A, \"Kombinatorilised algoritmid\", osa 1. Lehek\u00fcljel 60 on kirjeldatud koomikute esinemiste kavandamise \u00fclesannet erinevates kasiinodes. N\u00e4iteks tuuakse v\u00e4lja mitmed t\u00f5elised koomikud, sealhulgas Lily Tomlin, Weird Al Yankovic ja Robin Williams, kes oli raamatu ilmumisel veel elus. Knut viitab alati t\u00e4ielikele nimedele, seega mainitakse Williamsi lehek\u00fcljel 882 nimega \"Williams, Robin MacLorin\". Kuid tema teine nimi l\u00f5peb \"n\"-iga, mitte \"m\"-iga, st MacLorin.<\/p>\n

      MacLorin on tema ema neiup\u00f5lvenimi. Ta oli Anselm Joseph MacLorini, Mississippi 34. kuberneri, lapselaps. Tema valitsus ei j\u00e4\u00e4 ilmselt meelde millegi hea poole. Raamatust \u201eMississippi: ajalugu\u201c<\/a><\/noindex>:<\/p>\n

      \u201eAinus oluline s\u00fcndmus MacLorini ametiaja jooksul oli Ameerika \u00dchendriikide s\u00f5da Hispaania vastu, mis kuulutati v\u00e4lja 1898. aasta kevadel\u2026 Kahjuks andis seda s\u00f5da m\u00f5nedele ametnikele v\u00f5imaluse praktiseerida altk\u00e4emaksu. MacLorinit s\u00fc\u00fcdistati mitmesugustes kahtlastes praktikas, sealhulgas sugulaste t\u00f6\u00f6le v\u00f5tmiseks ja volituste kuritarvitamiseks armuandetes. T\u00f5rjumise ajastul s\u00fc\u00fcdistati kuberneri alkoholi tarbimises, mida ta avalikult tunnustas.\u201c<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Ajalooline viga<\/h1>\n

      \nVaadake traditsiooniline korrutamise algoritm<\/b> kooli \u00f5pikust. Kui palju \u00fchekohalisi korrutamistoiminguid see n\u00f5uab? Oletame, et korrutate \"Ma-kohalise numbrega \"Ma . Tundub, et \"Ma-kohaline number \"Ma. Esiteks korrutate esimese numbri \"Ma iga numbri \"Ma j\u00e4rjekorras. Siis korrutate teise numbri \"Ma iga numbri \"Ma j\u00e4rjekorras ja nii edasi, kuni olete k\u00f5ik numbrid l\u00e4bi k\u00e4inud \"Ma. Seega n\u00f5uab traditsiooniline korrutamine \"Ma primitivo korrutamisi. Eriti kahe arvu korrutamine \"Ma -kohtade kaupa n\u00f5uab \"Ma \u00fchekoha korrutamisi.<\/p>\n

      See on halb, kuid protsessi saab optimeerida meetodiga, mille t\u00f6\u00f6tas v\u00e4lja n\u00f5ukogude matemaatik Anatoli Aleksejevit\u0161 Karatsuba. Oletame, et \"Ma ja \"Ma\u00a0on kahekohalised k\u00fcmnendnumbrid; st on olemas numbrid \"Ma, \"Ma, \"Ma, \"Ma nii, et \"Ma ja \"Ma (selle algoritmi laiendamine suurematele arvudele n\u00f5uab teatud manipuleerimisi; kuigi see ei ole liiga keeruline, aga et \u00fcksikasjades eksida ei oleks, eelistan ma pidada kinni lihtsast n\u00e4itest). Siis \"Ma, \"Ma, \"Ma. Kahe liikme korrutamine annab \"Ma. Seni on meil endiselt \"Ma \u00fchekoha korrutamisi: \"Ma, \"Ma, \"Ma, \"Ma. N\u00fc\u00fcd liidame ja lahutame \"Ma. P\u00e4rast mitmeid \u00fcmberkorraldusi, mille ma j\u00e4tan lugeja \u00fclesandeks, tuleb \"Ma\u00a0\u2014 kokku vaid kolm \u00fchekohalist korrutamist! (On m\u00f5ned pidevad koefitsiendid, kuid neid saab arvutada vaid liitmise ja numbrite nihutamisega).<\/p>\n

      \u00c4ra n\u00f5ua t\u00f5estust, kuid Karatsuba algoritm<\/b> (rekursiivselt \u00fcldistatud eeltoodud n\u00e4itest) t\u00e4iustab traditsioonilist korrutamismeetodit \"Ma operatsioonidest tuhandeni \"Ma. Pange t\u00e4hele, et see on tegelik algoritmi t\u00e4iustus, mitte optimeerimine meeles arvutamiseks. T\u00f5epoolest, algoritm ei sobi vaimseks arvestamiseks, kuna see n\u00f5uab suuremaid kulusid rekursiivsete operatsioonide jaoks. Lisaks ilmneb efekt t\u00e4ielikult alles siis, kui numbrid on piisavalt suured (\u00f5nneks on Karatsuba algoritmist veel kiiremad meetodid: 2019. aasta m\u00e4rtsis avaldati algoritm, mis n\u00f5uab vaid n log n<\/i><\/a><\/noindex> korrutamist; kiirus suureneb ainult arusaamatult suurte numbrite korral).<\/p>\n

      Seda algoritmi kirjeldatakse teise k\u00f6ite 295. lehek\u00fcljel \"Aritmeetilised algoritmid\". Seal kirjutab Knuth: \"Huvitav, et seda ideed avastati alles 1962<\/b> aastal\", kui avaldati artikkel, mis kirjeldab Karatsuba algoritmi. Kuid! 1995. aastal avaldas Karatsuba artikli \"Arvutuste keerukus\", kus ta mainib mitmeid asju: 1) umbes 1956. aastal \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043b, et korrutamine pole v\u00f5imalik v\u00e4hem kui \"Ma sammud; 2) aastal 1960<\/b> osales Karatsuba seminaril, kus Kolmogorov esitas oma h\u00fcpoteesi n\u00b2. 3) \u201eJust n\u00e4dal aega hiljem\u201c t\u00f6\u00f6tas Karatsuba v\u00e4lja algoritmi \u201ejaga ja valitse\"; 4) 1962. aastal kirjutas ja avaldas Kolmogorov artikli Karatsuba nimel<\/i> algoritmi kirjeldusega. \u201eMa kuulsin sellest artiklist alles p\u00e4rast seda, kui seda \u00fcmber tr\u00fckiti.\"<\/p>\n

      Nii et viga seisneb selles, et asemel 1962<\/i> peaks olema 1960<\/i> aasta. Nii lihtne see on.<\/p>\n

      Anal\u00fc\u00fcs<\/h1>\n

      \nVigade leidmine ei n\u00f5udnud erilist oskust.<\/b><\/p>\n

        \n
      1. Esimene viga oli nii banaalne kui v\u00f5imalik ja asus suhteliselt silmapaistvas kohas (peat\u00fcki alguses). Iga idioot oleks selle leidnud; lihtsalt mina olin see idioot.\n<\/li>\n
      2. Teise tr\u00fcki vea leidmine n\u00f5udis \u00f5nne ja vaeva, kuid mitte oskust. \"Williams'i\" indeks on eelviimasel lehel, \u00fcsna m\u00e4rkimisv\u00e4\u00e4rne osa raamatust. Ma just sirvisin indeksit (see ei ole nii kahju, nagu tundub, sest Knuthi indeksites on varjatud munade jahtimisi. N\u00e4iteks on seal sissekanne araabia ja heebrea keeles, ja m\u00f5lemad viitavad lehele 66. Kuid sellel lehel ei mainita kumbagi keelt; selle asemel mainitakse \"keeli, mida loetakse paremale poole\"). Ja minu t\u00e4helepanu t\u00f5mbas teise nime. Kuna ma tavaliselt loen Vikipeediat, kontrollisin Robin Williams'i ja m\u00e4rkasin erinevust.\n<\/li>\n
      3. Ma tahaksin \u00f6elda, et ma tegin t\u00f5sist uurimist\u00f6\u00f6d ajaloo vea leidmiseks, kuid tegelikult vaatasin lihtsalt Karatsuba algoritmi Vikipeedia lehte.<\/a><\/noindex>Esimeste ridade seas on kirjas: \"Karatsuba algoritm on kiire korrutamise algoritm. Avas Anatoli Karatsuba 1960. aastal ja avaldati 1962. aastal.\" P\u00e4rast seda j\u00e4i vaid kokku l\u00fc\u00fca kaks ja kaks.<\/li>\n<\/ol>\n

        \nTulevikus tahaksin leida m\u00f5ne olulisema vea, eriti Knuthi koodis. Tahaksin leida vea ka \"Alustavaid algoritme\" k\u00e4sitlevas esimeses osas. V\u00f5ib-olla leidsin selle, kuid kohalikes raamatukogudes on mingil p\u00f5hjusel vaid 2., 3. ja 4A osa.<\/p>\n

        Finantsfaktid:<\/b><\/p>\n