{"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\/sl\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Prejel sem \u010dek od Knuta v vi\u0161ini 0x$3,00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u2014 znanstvenik na podro\u010dju informatike, ki tako zelo skrbi za pravilnost svojih knjig, da ponuja eno \u0161esteri\u010dno dolar<\/b> ($2,56, 0x$1,00) za vsako najdeno \"napako\", pri kateri \u0161teje vse, kar je \"tehni\u010dno, zgodovinsko, tipografsko ali politi\u010dno napa\u010dno\". Zelo sem \u017eelel prejeti \u010dek od Knutha, zato sem se odlo\u010dil poiskati napake v njegovem izjemnem delu \"Kunst programiranja\"<\/b> (TAOCP). Uspelo mi je najti tri. Po resnici povedano, Knuth mi je poslal \u010dek v vi\u0161ini 0x$3,00<\/b>.<\/p>\n

\"Prejel
\n
\nKot vidite, to ni pravi \u010dek. V preteklosti je Knuth po\u0161iljal prave \u010deke, a je to prenehal po\u010deti leta 2008 zaradi neobvladljive goljufije<\/a><\/noindex>. Zdaj po\u0161ilja \"osebne depozitne certifikate\" v banki San-Serif<\/a><\/noindex> (BoSS). Pravi, da je pripravljen poslati prave denarje v primeru potrebe, vendar se zdi, da je to preve\u010d zapleteno.
\n<\/a><\/noindex>
\nNa\u0161el sem dve tipkarski napaki in eno zgodovinsko napako. Na\u0161tel jih bom po vrstnem redu manj\u0161e trivialnosti.<\/p>\n

Tipkarska napaka \u0161t. 1<\/h1>\n

\nPrva tipkarska napaka je na strani 392 tretjega toma \"Razvr\u0161\u010danje in iskanje\", osma vrstica od spodaj: \"Po neuspelem iskanju je v\u010dasih (sometime) priporo\u010dljivo v tabelo vnesti novo zapis, ki vsebuje K<\/i>; metoda, ki to stori, se imenuje algoritem iskanja in vstavljanja. Napaka je v tem, da bi namesto sometime<\/i><\/b> moralo biti sometimes<\/i><\/b>.<\/p>\n

Seveda v taki napaki ni ni\u010d presenetljivega. Le v tem \u010dlanku se gotovo najde nekaj tipkarskih napak (brez nagrad za njihovo iskanje). To, kar je v resnici presenetljivo, pa je, da jih ni nih\u010de opazil tako dolgo. Stran 392 ni globoko zakopana v oddelek z matematiko, to je prva stran<\/b> \u0161este poglavja \"Iskanje\"! Morda en izmed najbolj branih delov knjige. Po logiki bi tam moralo biti najmanj tipkarskih napak, vendar ni.<\/p>\n

Mimogrede, \u010de ste kdaj pomislili, da bi prebrali TAOCP, poskusite. Mnogi bodo rekli, da je to priro\u010dnik<\/b>, ki ni namenjen neposrednemu branju, a to ni res. Avtor ima jasno stali\u0161\u010de in svojstven slog. Edina stvar, ki ovira berljivost, je zapletenost matematike. Vendar pa obstaja preprosta re\u0161itev: berite, dokler ne pridete do matematike, ki je ne razumete, presko\u010dite jo in odprite naslednji odsek, ki ga lahko razumete. Tako pri branju presko\u010dim vsaj 80% knjige, toda preostalih 20% je \u010dudovitih!<\/p>\n

Prav tako pravijo, da je TAOCP nerelevantna<\/b>, zastarela ali na drug na\u010din neprimenljiva na \u201estvarno programiranje\u201c. To tako\u0111e nije ta\u010dno. Na primer, u prvom delu nakon uvoda razmatra se pretra\u017eivanje elementa u nesortiranom nizu. Najjednostavniji algoritam je poznat svim programerima. Pokrenite pokaziva\u010d na po\u010detku niza, a zatim uradite slede\u0107e u petlji:<\/p>\n

    \n
  1. Proverite da li je trenutni element \u017eeljeni. Ako jeste, vra\u0107amo ga; u suprotnom,\n<\/li>\n
  2. Proverite da li je pokaziva\u010d van granica niza. Ako jeste, vra\u0107amo gre\u0161ku; u suprotnom,\n<\/li>\n
  3. Pove\u0107ajte pokaziva\u010d i nastavite.<\/li>\n<\/ol>\n

    \nSada razmislimo: koliko provere granica zahteva ovaj algoritam, u proseku? U najgorem slu\u010daju, kada niz ne sadr\u017ei element, za svaki element na listi bi\u0107e potrebna jedna provera, i u proseku \u0107e to biti ne\u0161to poput \"Prejel. Pametniji algoritam pretrage mo\u017ee da pro\u0111e sa samo jednom proverom granica. Priklju\u010dite \u017eeljeni element na kraj niza, zatim pokrenite pokaziva\u010d na po\u010detku niza i uradite slede\u0107e u petlji:<\/p>\n

      \n
    1. Proverite da li je trenutni element \u017eeljeni. Ako jeste, vra\u0107amo odgovor, ako je pokaziva\u010d unutar granica niza, ili gre\u0161ku, ako nije. U suprotnom,\n<\/li>\n
    2. Pove\u0107ajte pokaziva\u010d i nastavite.<\/li>\n<\/ol>\n

      \nBilo kako bilo, element \u0107e sigurno biti prona\u0111en, a provera granica se vr\u0161i samo jednom, kada se to dogodi. To je duboka ideja, ali je dovoljno jednostavna \u010dak i za po\u010detnika programera. Verovatno ne mogu govoriti o relevantnosti posla za druge, ali sam odmah uspeo da primenim ovu mudrost i u li\u010dnom i u profesionalnom kodu. Knjiga TAOCP je puna takvih dragulja (da budemo po\u0161teni, ima tu i mnogo \u010dudnih stvari, poput bubblersort<\/a><\/noindex>).<\/p>\n

      \u201ePretraga, pretraga
      \nToliko dugo
      \nPretraga, pretraga
      \nSamo sam hteo da ple\u0161em\u201c<\/i>
      \n\u2014 Luther Vandross, \u201ePretraga\u201c (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Gre\u0161ka br. 2<\/h1>\n

      \nDruga napaka je v zvezku 4A, \u201eKombinatorni algoritmi\u201c, del 1. Na strani 60 je opisana naloga na\u010drtovanja nastopov komikov v razli\u010dnih igralnicah. Kot primer je navedenih nekaj realnih komikov, vklju\u010dno z Lily Tomlin, Weird Al Yankovic in Robinom Williamsom, ki je bil \u0161e \u017eiv, ko je knjiga iz\u0161la. Knuth vedno v kazalo vklju\u010duje polna imena, zato je Williams omenjen na strani 882 kot \u201eWilliams, Robin Mac-Lorin\u201c. Vendar se njegovo drugo ime kon\u010da na \u201en\u201c, ne na \u201em\u201c, torej Mac-Lorin.<\/p>\n

      Mac-Lorin je dekli\u0161ka priimek njegove mame. Bila je pravnukinja Anselma Josepha Mac-Lorina, 34. guvernerja Mississippija. Njegovo vladanje naj bi se o\u010ditno zapomnilo po ni\u010demer dobrem. Iz knjige \u201eMississippi: zgodovina\u201c<\/a><\/noindex>:<\/p>\n

      \u201eNajpomembnej\u0161i dogodek v \u010dasu uprave Mac-Lorina je bilo napovedovanje vojne \u0160paniji s strani Zdru\u017eenih dr\u017eav spomladi 1898\u2026 Na \u017ealost je vojna morda nekaterim dr\u017eavnim uslu\u017ebencem dala prilo\u017enost za prakso podkupovanja. Mac-Lorina so obto\u017eili razli\u010dnih dvomljivih praks, vklju\u010dno s kumovstvom in pretirano uporabo pooblastil za pomilostitev. V dobi gibanja za treznost so ga kritiki obto\u017eili alkoholizma, kar je tudi javno priznal.\u201c<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Zgodovinska napaka<\/h1>\n

      \nRazmotrimo tradicionalni algoritem mno\u017eenja<\/b> iz \u0161olske programe. Koliko enomestnih mno\u017eenj zahteva? Recimo, da mno\u017eite \"Prejel-mestno \u0161tevilo \"Prejel na \"Prejel-mestno \"Prejel. Najprej pomno\u017eite prvo \u0161tevilko \"Prejel z vsako \u0161tevilko \"Prejel zaporedoma. Nato pomno\u017eite drugo \u0161tevilko \"Prejel z vsako \u0161tevilko \"Prejel zaporedoma in tako naprej, dokler ne preu\u010dite vseh \u0161tevilk \"Prejel. Tako tradicionalno mno\u017eenje zahteva \"Prejel enostavnih mno\u017eenj. Zlasti mno\u017eenje dveh \u0161tevil po \"Prejel mestih zahteva \"Prejel enomestna mno\u017eenja.<\/p>\n

      To je slabo, vendar lahko proces optimiziramo s metodo, ki jo je razvil sovjetski matematik Anatolij Alekseevi\u010d Karacub. Predpostavimo, da \"Prejel in \"Prejel\u00a0so dvomestna decimalna \u0161tevila; torej obstajajo \u0161tevila \"Prejel, \"Prejel, \"Prejel, \"Prejel taka, da \"Prejel in \"Prejel (posplo\u0161evanje tega algoritma na ve\u010dje \u0161tevilke zahteva dolo\u010dene manipulacije; \u010deprav to ni prete\u017eko, vendar da se ne zmedem v podrobnostih, se bom raje dr\u017eal enostavnega primera). Potem \"Prejel, \"Prejel, \"Prejel. Mno\u017eenje dvokratnikov daje \"Prejel. Do sedaj imamo \u0161e vedno \"Prejel enomestnih mno\u017eenj: \"Prejel, \"Prejel, \"Prejel, \"Prejel. Zdaj se\u0161tejmo in od\u0161tejmo \"Prejel. Po ve\u010d presenetljivih spremembah, ki jih pustim kot vajo za bralca, dobimo \"Prejel\u00a0\u2014 skupno tri enostavne mno\u017eenja! (Obstajajo nekateri stalni koeficienti, a ti se lahko izra\u010dunajo le z Se\u0161tevanjem in premikom mest.)<\/p>\n

      Ne zahtevajte dokazov, toda Karatsuba algoritem<\/b> (rekurzivno splo\u0161en iz zgoraj navedenega primera) izbolj\u0161a tradicionalno mno\u017eenje z \"Prejel operacijami do \"Prejel. Upo\u0161tevajte, da gre za pravo izbolj\u0161avo algoritma in ne optimizacijo za ro\u010dne izra\u010dune. Dejansko algoritem ni primeren za ro\u010dne izra\u010dune, saj zahteva velike stro\u0161ke rekurzivnih operacij. Poleg tega se u\u010dinek ne bo v celoti pokazal, dokler \u0161tevilke ne postanejo dovolj velike (na sre\u010do so se nad algoritmom Karatsube pojavile \u0161e hitrej\u0161e metode: marca 2019 je bil objavljen algoritem, ki potrebuje le n log n<\/i><\/a><\/noindex> mno\u017eenj; pospe\u0161ek velja le za neverjetno velike \u0161tevilke).<\/p>\n

      Ta algoritem je opisan na strani 295 drugega toma \"Knjiga algoritmov\". Tam Knuth pi\u0161e: \"Zanimivo je, da so to idejo odkrili \u0161ele v 1962<\/b> tem letu\", ko je bila objavljena naloga, ki opisuje algoritem Karatsuba. Ampak! Leta 1995 je Karatsuba objavil \u010dlanek \"Zlo\u017eenost izra\u010dunov\", v katerem pravi ve\u010d stvari: 1) okrog leta 1956 je Kolmogorov predpostavil, da mno\u017eenja ni mogo\u010de izvesti v manj kot \"Prejel korakih; 2) v 1960<\/b> tem letu je bil Karatsuba prisoten na seminarju, kjer je Kolmogorov predstavil svojo hipotezo n\u00b2. 3) \"Natan\u010dno teden dni kasneje\" je Karatsuba razvil algoritem \"deli in vladaj\"; 4) leta 1962 je Kolmogorov napisal in objavil \u010dlanek v imenu Karatsuba<\/i> z opisom algoritma. \"O tem \u010dlanku sem izvedel \u0161ele potem, ko so ga ponovno objavili.\"<\/p>\n

      Tako napaka izhaja iz tega, da namesto 1962<\/i> mora biti naveden 1960<\/i> leto. To je vse.<\/p>\n

      Analiza<\/h1>\n

      \nIskanje napak ni zahtevalo posebnega znanja.<\/b><\/p>\n

        \n
      1. Prva napaka je bila tako banala, kot je to mogo\u010de, in se je nahajala na razmeroma vidnem mestu (za\u010detek poglavja). Kdor koli bi jo na\u0161el; jaz pa sem bil tisti idiot.\n<\/li>\n
      2. Iskanje druge napake je zahtevalo sre\u010do in trud, a ne spretnosti. Indeks za \"Williamsa\" se nahaja na predzadnji strani zvezka, kar je precej opazna del knjige. Pravkar sem prelistaval indeks (to ni tako \u017ealostno, kot se zdi, saj so v indeksih Knutha skriti pirhi. Na primer, tam so zapisi v arab\u0161\u010dini in hebrej\u0161\u010dini, ki se oba nana\u0161ata na stran 66. A na tej strani noben od jezikov ni omenjen; namesto tega so omenjeni \"jeziki, ki se berejo z desne proti levi\"). Moje o\u010di so pritegnili drugo ime. Ker obi\u010dajno berem Wikipedijo, sem preveril Robina Williamsa in opazil neskladje.\n<\/li>\n
      3. Rad bi rekel, da sem opravil resno raziskavo, da bi na\u0161el zgodovinsko napako, a v resnici sem bil le na strani Wikipedije o Karatsubovem algoritmu<\/a><\/noindex>. V prvih stavkih pi\u0161e: \"Karatsubov algoritem je algoritem hitrega mno\u017eenja. Odkrit leta 1960 od Anatolija Karatsube in objavljen leta 1962.\" Po tem je ostalo le \u0161e se\u0161teti dva in dva.<\/li>\n<\/ol>\n

        \nV prihodnosti bi rad na\u0161el bolj pomembno napako, \u0161e posebej v Knuthovem kodi. Prav tako bi rad na\u0161el napako v prvem zvezku \"Temeljni algoritmi\". Morda bi jo tudi na\u0161el, a v lokalni knji\u017enici iz nekega razloga imajo le zvezke 2, 3 in 4A.<\/p>\n

        Finan\u010dne dejstva:<\/b><\/p>\n