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

Donald Knuth<\/b>\u00a0on inforaatika valdkonna teadlane, kes hoolib oma raamatute t\u00e4psusest nii palju, et pakub \u00fche heksadollar<\/b> ($2,56, 0x$1,00) iga leitud \"viga\" eest, kus vea alla kuulub k\u00f5ik, mis on \"tehniliselt, ajalooliselt, tr\u00fckiviga v\u00f5i poliitiliselt vale\". Ma t\u00f5eliselt tahtsin Knuthilt t\u0161ekki saada, seega otsustasin otsida vigu tema silmapaistvas teoses \"Programmimise kunst\"<\/b> (TAOCP). \u00d5nnestus leida kolm. T\u00f5ele au andes, saatis Knuth t\u0161eki summas 0x$3,00<\/b>.<\/p>\n

\"Sain
\n
\nNagu n\u00e4ete, ei ole see t\u00f5eline t\u0161ekk. Varem saatis Knuth p\u00e4ris t\u0161ekke, kuid l\u00f5petas selle 2008. aastal suure petuskeemi t\u00f5ttu. N\u00fc\u00fcd saadab ta \"isiklikke deposiidisertifikaate\"<\/a><\/noindex>San-Seriffi pangas (BoSS). Ta \u00fctleb, et on valmis vajadusel saatma p\u00e4ris raha, kuid tundub, et see on liiga vaevaline.<\/a><\/noindex> Leidsin kaks tr\u00fckiviga ja \u00fche ajaloolise vea. Loetlen need alates v\u00e4hemolulisest.
\n<\/a><\/noindex>
\nTr\u00fckiviga nr 1<\/p>\n

Esimene tr\u00fckiviga on kolmanda k\u00f6ite \"Sorteerimine ja otsimine\" lehek\u00fcljel 392, kaheksas rida alt \u00fcles: \"P\u00e4rast eba\u00f5nnestunud otsingut on m\u00f5nikord (sometime) soovitatav sisestada tabelisse uus sissekanne, mis sisaldab<\/h1>\n

\nEsimene tr\u00fckiviga on kolmanda k\u00f6ite \u201eSorteerimine ja otsimine\u201c lehek\u00fcljel 392, kaheksas rida alt: \u201eP\u00e4rast eba\u00f5nnestunud otsingut on m\u00f5nikord (sometime) soovitatav tabelisse sisestada uus kirje, mis sisaldab K<\/i>; meetod, mida selleks kasutatakse, nimetatakse leidmise ja lisamise algoritmiks. Probleem on selles, et selle asemel, et millegi!<\/i><\/b> peab olema m\u00f5nikord<\/i><\/b>.<\/p>\n

Loomulikult pole sellises veas midagi \u00fcllatavat. Selles artiklis on kindlasti mitu tr\u00fckiviga (ei mingeid auhindu nende leidmise eest). Mis on t\u00f5eliselt \u00fcllatav, on see, et seda nii kaua ei m\u00e4rgatud. Leht 392 ei asu s\u00fcgaval matemaatika jaotuses, see on esimene leht<\/b> kuuendas peat\u00fckis \u201eOtsing\u201c! V\u00f5ib-olla \u00fcks loetavamaid osi raamatust. Teooria j\u00e4rgi peaks seal olema k\u00f5ige v\u00e4hem tr\u00fckivigu, aga ei ole.<\/p>\n

Muide, kui olete kunagi m\u00f5elnud TAOCP lugemisest, proovige. Paljud \u00fctlevad, et see on k\u00e4siraamat<\/b>, mis ei ole m\u00f5eldud otseseks lugemiseks, kuid see ei ole t\u00f5si. Autoril on selge seisukoht ja iseloomulik stiil. Ainuke, mis takistab lugemist, on matemaatika keerukus. Siiski on lihtne lahendus: lugege, kuni j\u00f5uate matemaatikani, mida te ei m\u00f5ista, j\u00e4tke see vahele ja avage j\u00e4rgmine jaotis, mille m\u00f5istate. Nii lugedes j\u00e4tan ma vahele v\u00e4hemalt 80% raamatust, aga \u00fclej\u00e4\u00e4nud 20% on imelised!<\/p>\n

Samuti \u00f6eldakse, et TAOCP pole asjakohane<\/b>, on aegunud v\u00f5i muul viisil rakendumatuks muutunud \"reaalses programmeerimises\". See pole t\u00f5si. N\u00e4iteks k\u00e4sitletakse esimeses jaotises, p\u00e4rast sissejuhatust, elemendi otsimist sorteerimata massiivis. K\u00f5ige lihtsam algoritm on tuttav k\u00f5igile programmeerijatele. K\u00e4ivitage n\u00e4itaja massiivi alguses, seej\u00e4rel tehke ts\u00fcklis j\u00e4rgmised toimingud:<\/p>\n

    \n
  1. Kuidas kontrollida, kas praegune element on soovitud. Kui jah, tagastame selle; vastasel juhul\n<\/li>\n
  2. Kontrollige, kas n\u00e4itaja on massiivi piirist v\u00e4ljas. Kui on, tagastage viga; vastasel juhul\n<\/li>\n
  3. Suurendage n\u00e4itajat ja j\u00e4tkake.<\/li>\n<\/ol>\n

    \nN\u00fc\u00fcd vaatame: kui palju piiri kontrollimisi n\u00f5uab see algoritm keskmiselt? Halvimal juhul, kui massiiv ei sisalda elementi, vajab iga elemendi jaoks loendis \u00fchte kontrollimist ja keskmiselt on see midagi sellist \"Sain. Nutikam otsingu algoritm v\u00f5ib vajada ainult \u00fchte piiri kontrollimist. Lisage vajalik element massiivi l\u00f5ppu, seej\u00e4rel k\u00e4ivitage n\u00e4itaja massiivi alguses ja tehke ts\u00fcklis j\u00e4rgmised toimingud:<\/p>\n

      \n
    1. Kontrollige, kas praegune element on soovitud. Kui jah, tagastame vastuse, kui osutaja on massiivi piirides, v\u00f5i vea, kui see ei ole. Vastasel juhul\n<\/li>\n
    2. Suurendage n\u00e4itajat ja j\u00e4tkake.<\/li>\n<\/ol>\n

      \nNii v\u00f5i naa, element leitakse kindlasti, ja piire kontrollitakse ainult \u00fcks kord, kui see toimub. See on s\u00fcgavam m\u00f5te, kuid piisavalt lihtne isegi algajale programmeerijale. T\u00f5en\u00e4oliselt ei saa ma r\u00e4\u00e4kida ettepaneku relevantsusest teiste jaoks, kuid suutsin rakendada seda tarkust kohe nii isiklikus kui ka professionaalses koodis. Raamat TAOCP on t\u00e4is selliseid p\u00e4rleid (\u00f5igusem\u00f5istmise nimel, seal on ka palju kummalisi asju, nagu mullisortimine<\/a><\/noindex>).<\/p>\n

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

      <\/p>\n

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

      \nTeine tr\u00fckiviga on k\u00f6ites 4A, \u201eKombinatoorsed algoritmid\u201c, osa 1. Lehek\u00fcljel 60 on kirjeldatud kom\u00f6\u00f6dikute etenduste planeerimise \u00fclesannet erinevates kasiinodes. N\u00e4iteks tuuakse v\u00e4lja mitmed tegelikud koomikud, sealhulgas Lily Tomlin, Weird Al Yankovic ja Robin Williams, kes oli raamatu v\u00e4ljaandmise ajal veel elus. Knuth toob alati v\u00e4lja t\u00e4ielikud nimed, seega mainitakse Williamsi lehek\u00fcljel 882 kui \u201eWilliams, Robin McLorin\u201c. Kuid tema teine nimi l\u00f5ppeb \u201en\u201c-iga, mitte \u201em\u201c-iga, seega on McLorin.<\/p>\n

      McLorin on tema ema neiup\u00f5lvenimi. Ta oli Anslem Joseph McLorini lapselapselaps. Tema valitsemine ei j\u00e4tnud ilmselt suurt muljet. Raamatust \u201eMississippi: ajalugu\u201c<\/a><\/noindex>:<\/p>\n

      \u201eK\u00f5ige olulisem s\u00fcndmus Mac-Lorini administratsiooni ajal oli Ameerika \u00dchendriikide s\u00f5jakuulutamine Hispaaniale 1898. aasta kevadel\u2026 Kahjuks andis s\u00f5da ilmselt m\u00f5nele riigiametnikule v\u00f5imaluse praktiseerida altk\u00e4emaksu. Mac-Lorinile esitati s\u00fc\u00fcdistusi erinevates kahtlastes praktikates, sealhulgas nepotismis ja liialdatud armuandmise volituste kasutamises. Suitsuvaba liikumise ajal s\u00fc\u00fcdistati kuberneri alkoholi kuritarvitamises, mida ta avalikult tunnustas.\u201c<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Histooriline viga<\/h1>\n

      \nVaadakem traditsiooniline korrutamisalgoritm<\/b> kooliprogrammist. Kui palju n\u00f5uab see \u00fchekohalisi korrutamisi? Oletame, et korrutad \"Sain-kohalist arvu \"Sain j\u00e4rgnevaga \"Sain-kohaline \"Sain. Esiteks korrutad esimese numbri \"Sain iga numbri \"Sain j\u00e4rgides. Siis korrutad teise numbri \"Sain iga numbri \"Sain j\u00e4rgides ja nii edasi, kuni oled k\u00f5ik numbrid l\u00e4bi teinud \"Sain. Seega n\u00f5uab traditsiooniline korrutamine \"Sain primitiivsete korrutamiste arvu. T\u00e4psemalt vajavad kahe arvu korrutamine \"Sain kohakohalisi korrutamisi. \"Sain \u00fcheharulisi korrutusi.<\/p>\n

      See on halb, kuid protsessi saab optimeerida N\u00f5ukogude matemaatiku Anatoli Aleksejevi\u010d Karatsuba v\u00e4lja t\u00f6\u00f6tatud meetodi abil. Oletame, et \"Sain ja \"Sain\u00a0\u2014 kahekohalised k\u00fcmnendnumbrid; see t\u00e4hendab, et on olemas numbrid \"Sain, \"Sain, \"Sain, \"Sain sellised, et \"Sain ja \"Sain (selle algoritmi laiendamine suurematele numbritele n\u00f5uab teatud manipulatsioone; kuigi see ei ole liiga keeruline, et mitte vale detailide \u00fcle, eelistan ma j\u00e4\u00e4da lihtsa n\u00e4ite juurde). Siis \"Sain, \"Sain, \"Sain. Kahe liikme korrutamine annab \"Sain. Praegu on meil endiselt \"Sain \u00fche numbri korrutamised: \"Sain, \"Sain, \"Sain, \"Sain. N\u00fc\u00fcd liidame ja lahutame \"Sain. P\u00e4rast mitmeid \u00fcmberkorraldusi, mille j\u00e4tan lugejatele harjutamiseks, saame \"Sain\u00a0\u2014 kokku kolm \u00fche numbri korrutamist! (On m\u00f5ned p\u00fcsiv\u00e4\u00e4rtused, kuid neid saab arvutada ainult liitmise ja positsioonide nihutamise kaudu).<\/p>\n

      \u00c4rge paluge t\u00f5estust, kuid Karatsuba algoritm<\/b> (rekursiivselt laiendatud \u00fclaltoodud n\u00e4itest) parandab traditsioonilist korrutamisviisi \"Sain operatsioonidest kuni \"Sain. Pange t\u00e4hele, et see on t\u00f5eline algoritmi t\u00e4iustamine, mitte meeles arvestamiseks optimeerimine. T\u00f5epoolest, algoritm ei sobi meeles arvestamiseks, kuna see n\u00f5uab palju ressursse rekursiivsete toimingute jaoks. Lisaks avaldub efekt t\u00e4ielikult alles siis, kui numbrid on piisavalt suured (\u00f5nneks tuleb Karatsuba algoritmi asemel v\u00e4lja veelgi kiiremaid meetodeid: m\u00e4rtsis 2019 avaldati algoritm, mis vajab vaid n log n<\/i><\/a><\/noindex> korrutamist; kiirus on rakendatav ainult uskumatult suurte numbrite puhul).<\/p>\n

      Seda algoritmi on kirjeldatud \u201eArvutuslikud algoritmid\u201c teise k\u00f6ite lehel 295. Seal kirjutab Knuth: \u201eUskumatu, et seda ideed avastati alles 1962<\/b> aastal\u201c, mil avaldati artikkel, mis kirjeldas Karatsuba algoritmi. Kuid! 1995. aastal avaldas Karatsuba artikli \u201eArvutamise keerukus\u201c, kus ta \u00fctleb mitu asja: 1) umbes 1956. aastal tegi Kolmogorov eelduse, et korrutamine ei saa toimuda v\u00e4hem kui \"Sain sammu; 2) 1960<\/b> aastal osales Karatsuba seminaril, kus Kolmogorov esitas oma h\u00fcpoteesi n\u00b2. 3) \"Just n\u00e4dal aega hiljem\" t\u00f6\u00f6tas Karatsuba v\u00e4lja algoritmi \"jaga ja valitse\"; 4) 1962. aastal kirjutas ja avaldas Kolmogorov artikli Karatsuba nimel<\/i> algoritmi kirjeldustega. \"Saime sellest artiklist teada alles p\u00e4rast seda, kui see tr\u00fckiti uuesti.\"<\/p>\n

      Seega on viga selles, et selle asemel, 1962<\/i> peaks olema m\u00e4rgitud 1960<\/i> aasta. Nii et see ongi.<\/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\u00e4hegi v\u00f5ib olla, ja asus suhteliselt n\u00e4htaval kohal (peat\u00fcki alguses). Igasugune inimene oleks selle \u00fcles leidnud; lihtsalt mina sattusin olema see inimene.\n<\/li>\n
      2. Teise tr\u00fckkimisvea leidmine n\u00f5udis \u00f5nne ja vaeva, mitte oskusi. \u201eWilliamsi\u201c indeks asub raamatu eelviimasel lehek\u00fcljel, mis on \u00fcsna t\u00e4helepanuv\u00e4\u00e4rne osa raamatust. Ma just sirvisin indeksit (see ei ole nii halb, nagu tundub, sest Knuthi indeksites on peidetud \u00fclest\u00e4hendusi. N\u00e4iteks on seal kirjeid araabiakeeles ja heebrea keeles, ja m\u00f5lemad viitavad lehek\u00fcljele 66. Kuid sellel lehek\u00fcljel ei mainita \u00fchtegi neist keeltest; seal r\u00e4\u00e4gitakse hoopis \u201ekeeltest, mida loetakse paremalt vasakule\u201c). Ja mu t\u00e4helepanu k\u00f6itis teine nimi. Kuna ma tavaliselt loen Vikipeediat, kontrollisin Robin Williamsi ja m\u00e4rkasin lahknevust.\n<\/li>\n
      3. Tahaksin \u00f6elda, et tegin t\u00f5sise uurimist\u00f6\u00f6 ajaloolise vea leidmiseks, kuid tegelikult vaid vaatasin Vikipeedia lehte Karatsuba algoritmi kohta<\/a><\/noindex>. Esimeste ridade seas on kirjas: \u201eKaratsuba algoritm on kiire korrutamise algoritm. Avastas Anatoli Karatsub 1960. aastal ja avaldati 1962. aastal\u201c. P\u00e4rast seda j\u00e4i vaid kokku liita kaks korda kaks.<\/li>\n<\/ol>\n

        \nTulevikus tahaksin leida m\u00f5ne suurema vea, eriti Knuthi koodis. Samuti tahaksin leida vea \u201eFundamentaalsed algoritmid\u201c esimese k\u00f6ite kohta. V\u00f5ib-olla oleksin seda leidnud, aga kohalikus raamatukogus on mingil p\u00f5hjusel ainult k\u00f6ited 2, 3 ja 4A.<\/p>\n

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