{"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\/novosti-interneta\/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\u2014 un esperto nel campo dell'informatica, cos\u00ec attento alla correttezza dei suoi libri che offre un dollaro esadecimale<\/b> ($2,56, 0x$1,00) per ogni \"errore\" trovato, dove un errore \u00e8 considerato tutto ci\u00f2 che \u00e8 \"tecnicamente, storicamente, tipograficamente o politicamente scorretto\". Volevo davvero ricevere un assegno da Knuth, quindi ho deciso di cercare errori nella sua opera straordinaria \"L'arte della programmazione\"<\/b> (TAOCP). Sono riuscito a trovare tre. A proposito, Knuth mi ha inviato un assegno di 0x$3,00<\/b>.<\/p>\n

\"Ho
\n
\nCome vedete, non si tratta di un vero assegno. In passato Knuth inviava assegni reali, ma ha smesso nel 2008 a causa di frode dilagante<\/a><\/noindex>. Ora invia \"certificati di deposito personali\" nella banca di San Serrif<\/a><\/noindex> (BoSS). Dichiara di essere pronto ad inviare denaro reale se necessario, ma sembra che sia troppo complicato.
\n<\/a><\/noindex>
\nHo trovato due refusi e un errore storico. Elencher\u00f2 in ordine decrescente di banalit\u00e0.<\/p>\n

Refuso n. 1<\/h1>\n

\nIl primo refuso \u2014 a pagina 392 del terzo volume \"Ordinamento e ricerca\", ottava riga dal fondo: \"Dopo una ricerca non riuscita, a volte (sometime) \u00e8 consigliabile inserire nella tabella un nuovo record contenente K<\/i>; il metodo che fa questo si chiama algoritmo di ricerca e inserimento. L'errore \u00e8 che invece di qualche volta<\/i><\/b> deve essere a volte<\/i><\/b>.<\/p>\n

Naturalmente, non c'\u00e8 nulla di sorprendente in un simile errore. Solo in questo articolo ci saranno sicuramente alcuni refusi (nessun premio per trovarli). Ci\u00f2 che \u00e8 davvero sorprendente \u00e8 che non siano stati notati per cos\u00ec tanto tempo. La pagina 392 non \u00e8 sepolta profondamente nella sezione di matematica, \u00e8 la prima pagina<\/b> del sesto capitolo \"Ricerca\"! Potrebbe essere una delle sezioni pi\u00f9 lette del libro. In teoria, dovrebbe avere il minor numero di refusi, ma non \u00e8 cos\u00ec.<\/p>\n

A proposito, se mai hai pensato di leggere TAOCP, prova. Molti diranno che \u00e8 un manuale<\/b>, non destinato alla lettura diretta, ma non \u00e8 vero. L'autore ha un punto di vista chiaro e uno stile unico. 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 capisci, saltala e passa alla sezione successiva 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 non sia rilevante<\/b>, obsoleta o in altro modo non applicabile alla \u00abprogrammazione reale\u00bb. Questo non \u00e8 vero. Ad esempio, nella prima sezione dopo l'introduzione viene trattata la ricerca di un elemento in un array non ordinato. L'algoritmo pi\u00f9 semplice \u00e8 noto a tutti i programmatori. Posiziona il puntatore all'inizio dell'array, quindi esegui le seguenti operazioni in ciclo:<\/p>\n

    \n
  1. Controlla se l'elemento corrente \u00e8 quello desiderato. Se s\u00ec, restituiscilo; altrimenti\n<\/li>\n
  2. Controlla se il puntatore \u00e8 oltre la fine 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 mediamente questo algoritmo? Nel caso peggiore, quando l'array non contiene l'elemento, \u00e8 necessaria una verifica per ogni elemento della lista, e mediamente sar\u00e0 qualcosa del genere \"Ho. Un algoritmo di ricerca pi\u00f9 intelligente potrebbe richiedere solo un controllo dei limiti. Collega l'elemento desiderato alla fine dell'array, quindi posiziona il puntatore all'inizio dell'array e esegui le seguenti operazioni in ciclo:<\/p>\n

      \n
    1. Controlla se l'elemento attuale \u00e8 quello desiderato. Se s\u00ec, restituiamo la risposta se il puntatore \u00e8 all'interno dell'array, oppure 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 il controllo dei limiti viene effettuato solo una volta che ci\u00f2 accade. \u00c8 un'idea profonda, ma \u00e8 abbastanza semplice anche per un programmatore alle prime armi. Probabilmente non posso parlare della rilevanza del lavoro per gli altri, ma sono riuscito a applicare immediatamente questa saggezza sia nel mio codice personale che 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
      \nCos\u00ec a lungo
      \nCerca, cerca
      \nVolevo solo ballare\u00bb<\/i>
      \n\u2014 Luther Vandross, \u00abCerca\u00bb (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Errore #2<\/h1>\n

      \nIl secondo errore si trova nel volume 4A, \"Algoritmi combinatori\", parte 1. A pagina 60 viene descritta una questione relativa alla programmazione delle esibizioni di comici in vari casin\u00f2. Vengono citati alcuni comici reali, tra cui Lily Tomlin, Weird Al Yankovic e Robin Williams, il quale era ancora in vita quando il libro \u00e8 stato pubblicato. Knuth fornisce sempre i nomi completi nell'indice, quindi Williams viene menzionato a pagina 882 come \"Williams, Robin Mac-Laurin\". Ma il suo secondo nome finisce con 'n' e non con 'm', cio\u00e8 Mac-Laurin.<\/p>\n

      Mac-Laurin \u00e8 il cognome da nubile di sua madre. Era pronipote di Anselm Joseph Mac-Laurin, 34\u00b0 governatore del Mississippi. Il suo mandato, evidentemente, non \u00e8 ricordato per nulla di buono. Da \"Mississippi: storia\" \u00abMississippi: storia\u00bb<\/a><\/noindex>:<\/p>\n

      \u00abL'evento pi\u00f9 significativo durante l'amministrazione di Mac-Laurin \u00e8 stata la dichiarazione di guerra da parte degli Stati Uniti contro la Spagna nella primavera del 1898... Purtroppo, la guerra ha forse dato ad alcuni funzionari pubblici l'opportunit\u00e0 di esercitare corruzione. Mac-Laurin \u00e8 stato accusato di varie pratiche discutibili, tra cui nepotismo e uso eccessivo dei poteri di grazia. In un'epoca di movimento per la sobriet\u00e0, i critici hanno accusato il governatore di alcolismo, cosa che egli ha pubblicamente riconosciuto\u00bb.<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Errore storico<\/h1>\n

      \nConsideriamo l'algoritmo tradizionale di moltiplicazione<\/b> che si insegna a scuola. Quante operazioni di moltiplicazione a una cifra richiede? Supponiamo che tu stia moltiplicando \"Ho-cifra \"Ho con \"Ho-cifre \"Ho. Per prima cosa, 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, finch\u00e9 non hai passato tutte le cifre \"Ho. In questo modo, la moltiplicazione tradizionale richiede \"Ho moltiplicazioni primitive. In particolare, la moltiplicazione di due numeri di \"Ho cifre richiede \"Ho moltiplicazioni a una cifra.<\/p>\n

      \u00c8 una cosa negativa, ma il processo pu\u00f2 essere ottimizzato grazie a un metodo sviluppato dal matematico sovietico Anatolij Alekseevi\u010d Kara\u010dub. Supponiamo che \"Ho e \"Ho\u00a0ci siano numeri decimali a due cifre; ovvero ci sono numeri \"Ho, \"Ho, \"Ho, \"Ho tali che \"Ho e \"Ho (l'estensione di questo algoritmo a numeri pi\u00f9 grandi richiede alcune manipolazioni; anche se non \u00e8 troppo complicato, per evitare di sbagliare nei dettagli, preferisco rimanere su un esempio semplice). Allora \"Ho, \"Ho, \"Ho. La moltiplicazione di binomi d\u00e0 \"Ho. Al momento abbiamo ancora \"Ho moltiplicazioni a una cifra: \"Ho, \"Ho, \"Ho, \"Ho. Ora sommiamo e sottraiamo \"Ho. Dopo alcune permutazioni, che lascer\u00f2 come esercizio per il lettore, otteniamo \"Ho\u00a0\u2014 solo tre moltiplicazioni a una cifra! (Ci sono alcuni coefficienti costanti, ma si possono calcolare solo tramite addizione e spostamento di posizioni).<\/p>\n

      Non chiedete prove, ma l'algoritmo di Kara\u010dub<\/b> (che \u00e8 stato generalizzato ricorsivamente dall'esempio sopra) migliora il metodo tradizionale di moltiplicazione da \"Ho operazioni a \"Ho. Si prega di notare che questo \u00e8 un reale miglioramento dell'algoritmo e non un'ottimizzazione per il calcolo mentale. Infatti, l'algoritmo non \u00e8 adatto per il calcolo mentale, poich\u00e9 richiede un notevole sovraccarico per le operazioni ricorsive. Inoltre, l'effetto non si manifester\u00e0 completamente finch\u00e9 i numeri non diventeranno abbastanza grandi (per fortuna, invece dell'algoritmo di Karatsuba sono arrivati metodi ancora pi\u00f9 veloci: nel marzo 2019 \u00e8 stato pubblicato un algoritmo che richiede solo n log n<\/i><\/a><\/noindex> moltiplicazioni; l'accelerazione si applica solo a numeri inimmaginabilmente grandi).<\/p>\n

      Questo algoritmo \u00e8 descritto a pagina 295 del secondo volume di \u00abAlgoritmi numerici\u00bb. L\u00ec Knuth scrive: \u00ab\u00c8 curioso che questa idea sia stata scoperta solo nel 1962<\/b> anno\u00bb, quando \u00e8 stato pubblicato un articolo che descriveva l'algoritmo di Karatsuba. Ma! Nel 1995, Karatsuba pubblic\u00f2 un articolo intitolato \u00abLa complessit\u00e0 dei calcoli\u00bb, in cui afferma diverse cose: 1) intorno al 1956, Kolmogorov ipotizz\u00f2 che la moltiplicazione non pu\u00f2 essere eseguita in meno di \"Ho passi; 2) in 1960<\/b> Nel 1963, Karatsuba ha partecipato a un seminario in cui Kolmogorov ha presentato la sua ipotesi n\u00b2. 3) \u00abProprio una settimana\u00bb Karatsuba ha sviluppato l'algoritmo \u00abdividi e conquista\u00bb; 4) Nel 1962 Kolmogorov ha scritto e pubblicato un articolo a nome di Karatsuba<\/i> che descriveva l'algoritmo. \u00abSono venuto a conoscenza di questo articolo solo dopo che \u00e8 stato ripubblicato\u00bb.<\/p>\n

      Pertanto, l'errore consiste nel fatto che invece di 1962<\/i> deve essere indicato 1960<\/i> l'anno. Ecco tutto.<\/p>\n

      Analisi<\/h1>\n

      \nLa ricerca di errori non richiedeva particolari abilit\u00e0.<\/b><\/p>\n

        \n
      1. Il primo errore era cos\u00ec banale che era quasi impossibile non notarlo, e si trovava in un luogo relativamente evidente (all'inizio del capitolo). Qualsiasi idiota l'avrebbe trovato; semplicemente, io ero quell'idiota.\n<\/li>\n
      2. Trovare il secondo refuso richiedeva fortuna e impegno, ma non abilit\u00e0. L'indice per \"Williams\" si trova penultima pagina del volume, una parte piuttosto evidente del libro. Stavo proprio sfogliando l'indice (non \u00e8 cos\u00ec terribile come sembra, perch\u00e9 negli indici di Knuth si possono trovare uova di Pasqua. Ad esempio, ci sono voci in arabo e ebraico, entrambe che rimandano alla pagina 66. Ma in questa pagina non si menciona nessuna delle lingue; al contrario, si fa riferimento a \"lingue che si leggono da destra a sinistra\"). E la mia attenzione \u00e8 stata attratta dal secondo nome. Poich\u00e9 di solito leggo Wikipedia, ho verificato Robin Williams e ho notato una discrepanza.\n<\/li>\n
      3. Vorrei poter dire di aver condotto una ricerca seria per trovare l'errore storico, ma in realt\u00e0 ho semplicemente dato un'occhiata alla pagina di Wikipedia sull'algoritmo di Karatsuba<\/a><\/noindex>. Nelle prime righe si legge: \"L'algoritmo di Karatsuba \u00e8 un algoritmo di moltiplicazione veloce. 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 individuare un bug nel primo volume di \"Algoritmi fondamenti\". 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