{"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\/it\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Ho ricevuto da Knut un assegno di 0x$3,00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u00e8 un accademico nel campo dell'informatica, che si preoccupa cos\u00ec tanto della correttezza dei suoi libri che offre un dollaro esadecimale<\/b> ($2,56, 0x$1,00) per qualsiasi \"errore\" trovato, dove per errore si intende tutto ci\u00f2 che \u00e8 \"tecnicamente, storicamente, tipograficamente o politicamente scorretto\". Volevo davvero ricevere un assegno da Knuth, cos\u00ec ho deciso di cercare errori nella sua opera eccezionale \"L'arte della programmazione\"<\/b> (TAOCP). Sono riuscito a trovarne tre. D'accordo con la parola, Knuth ha inviato un assegno per 0x$3,00<\/b>.<\/p>\n

\"Ho
\n
\nCome puoi vedere, questo non \u00e8 un vero assegno. Un tempo Knuth inviava assegni veri, ma ha smesso nel 2008 a causa di frode sfrenata<\/a><\/noindex>. Ora invia \"certificati di deposito personali\" presso la banca San Seriffe<\/a><\/noindex> (BoSS). Dice che \u00e8 pronto a inviare denaro reale se necessario, ma sembra che sia troppo complicato.
\n<\/a><\/noindex>
\nHo trovato due refusi e un errore storico. Li elencher\u00f2 in ordine di complessit\u00e0 decrescente.<\/p>\n

Refuso n. 1<\/h1>\n

\nIl primo refuso si trova a pagina 392 del terzo volume \"Ordinamento e ricerca\", ottava riga dal fondo: \"Dopo una ricerca infruttuosa a volte (sometime) \u00e8 preferibile inserire nella tabella una nuova voce che contiene K<\/i>; il metodo che fa questo si chiama algoritmo di ricerca e inserimento. L'errore \u00e8 che invece di sometime<\/i><\/b> dovrebbe essere sometimes<\/i><\/b>.<\/p>\n

Certo, non c'\u00e8 nulla di sorprendente in un errore del genere. Solo in questo articolo ci saranno sicuramente un paio di refusi (nessun premio per trovarli). Ci\u00f2 che \u00e8 davvero sorprendente \u00e8 quanto tempo ci sia voluto per notarli. La pagina 392 non \u00e8 sepolta profondamente nella sezione di matematica, \u00e8 la prima pagina<\/b> del sesto capitolo \"Ricerca\"! Forse una delle sezioni pi\u00f9 lette del libro. Idealmente, l\u00ec ci dovrebbero essere il minor numero di refusi, ma non \u00e8 cos\u00ec.<\/p>\n

A proposito, se hai mai pensato di leggere TAOCP, prova. Molti diranno che \u00e8 un manuale<\/b>, non destinato alla lettura diretta, ma non \u00e8 vero. L'autore ha una chiara visione e uno stile distintivo. L'unica cosa che ostacola la leggibilit\u00e0 \u00e8 la complessit\u00e0 della matematica. Tuttavia, c'\u00e8 una soluzione semplice: leggi finch\u00e9 non arrivi alla matematica che non comprendi, saltala e apri il prossimo capitolo che puoi comprendere. Leggendo in questo modo, salto almeno l'80% del libro, ma il restante 20% \u00e8 magnifico!<\/p>\n

Si dice anche che TAOCP sia irrilevante<\/b>, obsoleta o in altro modo non applicabile alla \u00abprogrammazione reale\u00bb. Anche questo \u00e8 falso. Ad esempio, nella prima sezione dopo l'introduzione si tratta della ricerca di un elemento in un array non ordinato. L'algoritmo pi\u00f9 semplice \u00e8 conosciuto da tutti i programmatori. Avvia il puntatore all'inizio dell'array, quindi esegui i seguenti passaggi in un ciclo:<\/p>\n

    \n
  1. Controlla se l'elemento attuale \u00e8 quello desiderato. Se s\u00ec, restituiscilo; altrimenti\n<\/li>\n
  2. Controlla se il puntatore \u00e8 fuori dai limiti dell'array. Se s\u00ec, restituisci un errore; altrimenti\n<\/li>\n
  3. Incrementa il puntatore e continua.<\/li>\n<\/ol>\n

    \nOra consideriamo: quante verifiche dei limiti richiede in media questo algoritmo? Nel caso peggiore, quando l'array non contiene l'elemento, per ogni elemento della lista sar\u00e0 necessaria una verifica, e in media sar\u00e0 qualcosa del genere \"Ho. Un algoritmo di ricerca pi\u00f9 intelligente pu\u00f2 richiedere solo una verifica dei limiti. Aggiungi l'elemento desiderato alla fine dell'array, quindi avvia il puntatore all'inizio dell'array e segui i seguenti passaggi in un ciclo:<\/p>\n

      \n
    1. Controlla se l'elemento attuale \u00e8 quello desiderato. Se s\u00ec, restituisci la risposta se il puntatore \u00e8 all'interno dell'array, o un errore se non lo \u00e8. Altrimenti\n<\/li>\n
    2. Incrementa il puntatore e continua.<\/li>\n<\/ol>\n

      \nIn ogni caso, l'elemento sar\u00e0 sicuramente trovato, e la verifica dei limiti viene eseguita solo una volta, quando ci\u00f2 accade. \u00c8 un'idea profonda, ma \u00e8 abbastanza semplice anche per un programmatore principiante. Probabilmente non posso parlare della rilevanza del lavoro per gli altri, ma sono riuscito a applicare immediatamente questa saggezza sia nel codice personale che in quello professionale. Il libro TAOCP \u00e8 pieno di tali gemme (per essere giusti, ci sono anche molte cose strane, come l'ordinamento a bolle<\/a><\/noindex>).<\/p>\n

      \u00abCerca, cerca
      \nTanto tempo fa
      \nCerca, cerca
      \nVolevo solo ballare\u00bb<\/i>
      \n\u2014 Luther Vandross, \u00abCerca\u00bb (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Refuso n. 2<\/h1>\n

      \nIl secondo refuso \u00e8 nel volume 4A, \"Algoritmi combinatori\", parte 1. A pagina 60 viene descritta una questione riguardante la programmazione delle esibizioni dei comici in vari casin\u00f2. Come esempio vengono citati alcuni comici reali, tra cui Lily Tomlin, Weird Al Yankovic e Robin Williams, che era ancora vivo quando il libro \u00e8 stato pubblicato. Knuth include sempre i nomi completi nell'indice, quindi Williams \u00e8 menzionato a pagina 882 come \"Williams, Robin Mac-Laurin\". Ma il suo secondo nome finisce con \"n\" e non con \"m\", ovvero Mac-Laurin.<\/p>\n

      Mac-Laurin \u00e8 il cognome da nubile di sua madre. Era bisnipote di Anselmo Giuseppe Mac-Laurin, 34\u00b0 governatore del Mississippi. Il suo mandato, evidentemente, non \u00e8 ricordato per nulla di buono. Dalla libro \"Mississippi: storia\"<\/a><\/noindex>:<\/p>\n

      \"L'evento pi\u00f9 importante durante l'amministrazione di Mac-Laurin fu la dichiarazione di guerra della Repubblica degli Stati Uniti contro la Spagna nella primavera del 1898... Sfortunatamente, la guerra potrebbe aver dato a alcuni funzionari statali l'opportunit\u00e0 di praticare corruzione. Mac-Laurin fu accusato di varie pratiche dubbie, tra cui il nepotismo e un uso eccessivo dei poteri di grazia. Durante l'epoca del movimento per la sobriet\u00e0, i critici accusarono il governatore di ubriachezza, cosa che egli ammise pubblicamente.\"<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Errore storico<\/h1>\n

      \nConsideriamo l'algoritmo tradizionale della moltiplicazione<\/b> dalla programma scolastica. Quante operazioni di moltiplicazione a cifra singola richiede? Supponiamo che tu stia moltiplicando \"Ho-un numero a \"Ho in \"Ho-cifre \"Ho. Prima moltiplichi la prima cifra \"Ho per ogni cifra \"Ho a turno. Poi moltiplichi la seconda cifra \"Ho per ogni cifra \"Ho a turno e cos\u00ec via, fino a quando non hai trattato tutte le cifre \"Ho. In questo modo, la moltiplicazione tradizionale richiede \"Ho moltiplicazioni primitive. In particolare, moltiplicare due numeri di \"Ho cifre richiede \"Ho moltiplicazioni a cifra singola.<\/p>\n

      Questo \u00e8 negativo, ma \u00e8 possibile ottimizzare il processo con il metodo sviluppato dal matematico sovietico Anatoly Alexeyevich Karatsuba. Supponiamo che \"Ho e \"Ho\u00a0siano numeri decimali a due cifre; cio\u00e8 ci sono numeri \"Ho, \"Ho, \"Ho, \"Ho tali che \"Ho e \"Ho (generalizzare questo algoritmo a numeri pi\u00f9 grandi richiede alcune manovre; anche se non \u00e8 troppo complicato, per non sbagliare nei dettagli, preferisco rimanere su un esempio semplice). Allora \"Ho, \"Ho, \"Ho. La moltiplicazione di binomi d\u00e0 \"Ho. Fino a questo punto abbiamo ancora \"Ho moltiplicazioni a cifra singola: \"Ho, \"Ho, \"Ho, \"Ho. Ora sommiamo e sottraiamo \"Ho. Dopo diversi scambi, che lascer\u00f2 come esercizio per il lettore, si ottiene \"Ho\u00a0\u2014 solo tre moltiplicazioni a una cifra! (Ci sono alcuni coefficienti fissi, ma possono essere calcolati solo tramite somma e spostamento delle cifre).<\/p>\n

      Non chiedere prove, ma l'algoritmo di Karatsuba<\/b> (generalizzato ricorsivamente dall'esempio sopra) migliora il metodo tradizionale di moltiplicazione da \"Ho operazioni a \"Ho. Si noti che questo \u00e8 un reale miglioramento dell'algoritmo e non un'ottimizzazione per i calcoli mentali. Infatti, l'algoritmo non \u00e8 adatto per il calcolo mentale, poich\u00e9 richiede un notevole overhead per le operazioni ricorsive. Inoltre, l'effetto si manifester\u00e0 completamente solo quando i numeri diventeranno sufficientemente grandi (fortunatamente, al posto dell'algoritmo di Karatsuba sono arrivati metodi ancora pi\u00f9 veloci: a marzo 2019 \u00e8 stato pubblicato un algoritmo che richiede solo n log n<\/i><\/a><\/noindex> moltiplicazioni; l'accelerazione \u00e8 applicabile solo ai numeri inimmaginabilmente grandi).<\/p>\n

      Questo algoritmo \u00e8 descritto a pagina 295 del secondo volume di \u00abAlgoritmi Semiconvertibili\u00bb. L\u00ec Knuth scrive: \u00abCuriosamente, questa idea \u00e8 stata scoperta solo nel 1962<\/b> anno\u00bb, quando \u00e8 stato pubblicato un articolo che descrive l'algoritmo di Karatsuba. Ma! Nel 1995 Karatsuba ha pubblicato un articolo \u00abLa complessit\u00e0 dei calcoli\u00bb, in cui dice alcune cose: 1) intorno al 1956, Kolmogorov ha ipotizzato che la moltiplicazione non possa essere effettuata in meno di \"Ho passi; 2) nel 1960<\/b> anno Karatsuba era presente a un seminario in cui Kolmogorov ha esposto la sua ipotesi n\u00b2. 3) \u00abEsattamente una settimana\u00bb Karatsuba ha sviluppato l'algoritmo \u00abdivide et impera\u00bb; 4) nel 1962 Kolmogorov ha scritto e pubblicato un articolo a nome di Karatsuba<\/i> con la descrizione dell'algoritmo. \u00abHo saputo di questo articolo solo dopo che \u00e8 stato ripubblicato\u00bb.<\/p>\n

      Quindi, l'errore \u00e8 che invece di 1962<\/i> dovrebbe essere indicato 1960<\/i> l'anno. Questo \u00e8 tutto.<\/p>\n

      Analisi<\/h1>\n

      \nLa ricerca degli errori non richiedeva particolare abilit\u00e0.<\/b><\/p>\n

        \n
      1. Il primo errore era cos\u00ec banale che era possibile e si trovava in una posizione relativamente evidente (all'inizio del capitolo). Qualsiasi idiota l'avrebbe trovato; semplicemente io sono stato quell'idiota.\n<\/li>\n
      2. La ricerca del secondo refuso richiedeva fortuna e impegno, ma non abilit\u00e0. L'indice per \"Williams\" si trova sulla penultima pagina del volume, una parte piuttosto evidente del libro. Stavo proprio sfogliando l'indice (non \u00e8 cos\u00ec male come sembra, perch\u00e9 negli indici di Knuth ci sono uova di pasqua nascoste. Ad esempio, ci sono voci in arabo ed ebraico, e entrambe indicano pagina 66. Ma in quella pagina non viene menzionata nessuna delle lingue; viene invece menzionata \"languaggi che si leggono da destra a sinistra\"). E la mia attenzione \u00e8 stata attratta dal secondo nome. Poich\u00e9 leggo spesso Wikipedia, ho controllato Robin Williams e ho notato una discrepanza.\n<\/li>\n
      3. Vorrei poter dire che ho condotto una seria ricerca per trovare un errore storico, ma in realt\u00e0 ho semplicemente guardato la pagina di Wikipedia sull'algoritmo di Karatsuba<\/a><\/noindex>. Nelle prime righe si legge: \"L'algoritmo di Karatsuba \u00e8 un algoritmo di moltiplicazione rapida. Scoperto da Anatolij Karatsuba nel 1960 e pubblicato nel 1962\". Dopo di che, rimaneva solo da sommare due pi\u00f9 due.<\/li>\n<\/ol>\n

        \nIn futuro vorrei trovare un errore pi\u00f9 sostanziale, specialmente nel codice di Knuth. Vorrei anche trovare un bug nel primo volume \"Algoritmi fondamentali\". Forse l'avrei trovato, ma nella biblioteca locale, per qualche motivo, ci sono solo i volumi 2, 3 e 4A.<\/p>\n

        Fatti finanziari:<\/b><\/p>\n