{"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\/fr\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"J'ai re\u00e7u un ch\u00e8que de Knuth pour 0x$3,00.","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u2014 un scientifique en informatique qui tient tellement \u00e0 la pr\u00e9cision de ses livres qu'il propose un dollar hexad\u00e9cimal<\/b> ($2,56, 0x$1,00) pour toute \"erreur\" trouv\u00e9e, o\u00f9 une erreur est d\u00e9finie comme tout ce qui est \"techniquement, historiquement, typographiquement ou politiquement incorrect\". J'\u00e9tais tr\u00e8s d\u00e9sireux de recevoir un ch\u00e8que de Knuth, donc j'ai d\u00e9cid\u00e9 de chercher des erreurs dans son \u0153uvre exceptionnelle \u00abL'Art de la Programmation\u00bb<\/b> (TAOCP). J'ai r\u00e9ussi \u00e0 en trouver trois. Fid\u00e8le \u00e0 sa parole, Knuth a envoy\u00e9 un ch\u00e8que de 0x$3,00<\/b>.<\/p>\n

\"J'ai
\n
\nComme vous pouvez le voir, ce n'est pas un vrai ch\u00e8que. Auparavant, Knuth envoyait de vrais ch\u00e8ques, mais il a arr\u00eat\u00e9 en 2008 \u00e0 cause de fraude incessante<\/a><\/noindex>. Maintenant, il envoie des \"certificats de d\u00e9p\u00f4t personnels\" \u00e0 la banque San Serriffe<\/a><\/noindex> (BoSS). Il dit qu'il est pr\u00eat \u00e0 envoyer de l'argent r\u00e9el si n\u00e9cessaire, mais cela semble trop compliqu\u00e9.
\n<\/a><\/noindex>
\nJ'ai trouv\u00e9 deux coquilles et une erreur historique. Je vais les \u00e9num\u00e9rer par ordre d\u00e9croissant de trivialit\u00e9.<\/p>\n

Coquille n\u00b01<\/h1>\n

\nLa premi\u00e8re coquille se trouve \u00e0 la page 392 du troisi\u00e8me volume \"Tri et Recherche\", huiti\u00e8me ligne en bas : \u00abApr\u00e8s une recherche infructueuse, il peut parfois (sometime) \u00eatre souhaitable d'ins\u00e9rer un nouvel enregistrement dans le tableau, contenant K<\/i>; la m\u00e9thode qui le fait s'appelle l'algorithme de recherche et d'insertion. L'erreur est que, \u00e0 la place de sometime<\/i><\/b> cela devrait \u00eatre sometimes<\/i><\/b>.<\/p>\n

Bien s\u00fbr, il n'y a rien de surprenant dans une telle erreur. Dans cet article, il y aura s\u00fbrement plusieurs coquilles (aucune r\u00e9compense pour les trouver). Ce qui est vraiment surprenant, c'est que cela n'a pas \u00e9t\u00e9 remarqu\u00e9 plus t\u00f4t. La page 392 n'est pas profond\u00e9ment enfouie dans la section math\u00e9matique, c'est la toute premi\u00e8re page<\/b> du sixi\u00e8me chapitre \"Recherche\" ! Peut-\u00eatre l'une des sections les plus lues du livre. En th\u00e9orie, il devrait y avoir le moins de coquilles, mais non.<\/p>\n

D'ailleurs, si jamais vous avez pens\u00e9 \u00e0 lire TAOCP, essayez. Beaucoup diront que c'est un manuel<\/b>, pas destin\u00e9 \u00e0 une lecture directe, mais c'est faux. L'auteur a un point de vue clair et un style unique. La seule chose qui nuit \u00e0 la lisibilit\u00e9 est la complexit\u00e9 des math\u00e9matiques. Pourtant, il existe une solution simple : lisez jusqu'\u00e0 ce que vous atteigniez les math\u00e9matiques que vous ne comprenez pas, sautez-les et passez au prochain chapitre que vous pouvez comprendre. En lisant de cette mani\u00e8re, je saute au moins 80 % du livre, mais les 20 % restants sont magnifiques !<\/p>\n

On dit \u00e9galement que TAOCP n'est pas pertinent<\/b>, obsol\u00e8te ou autrement inapplicable \u00e0 \u00ab la programmation r\u00e9elle \u00bb. C'est aussi faux. Par exemple, dans la premi\u00e8re section apr\u00e8s l'introduction, on aborde la recherche d'un \u00e9l\u00e9ment dans un tableau non tri\u00e9. L'algorithme le plus simple est connu de tous les programmeurs. Placez un pointeur au d\u00e9but du tableau, puis proc\u00e9dez comme suit dans une boucle :<\/p>\n

    \n
  1. V\u00e9rifiez si l'\u00e9l\u00e9ment actuel est le d\u00e9sir\u00e9. Si c'est le cas, retournez-le ; sinon,\n<\/li>\n
  2. V\u00e9rifiez si le pointeur est hors des limites du tableau. Si c'est le cas, retournez une erreur ; sinon,\n<\/li>\n
  3. Augmentez le pointeur et continuez.<\/li>\n<\/ol>\n

    \nMaintenant, examinons : combien de v\u00e9rifications de limites n\u00e9cessite cet algorithme en moyenne ? Dans le pire des cas, lorsque le tableau ne contient pas l'\u00e9l\u00e9ment, il faudra une v\u00e9rification pour chaque \u00e9l\u00e9ment de la liste, et en moyenne, cela ressemblera \u00e0 quelque chose comme \"J'ai. Un algorithme de recherche plus intelligent pourrait ne n\u00e9cessiter qu'une seule v\u00e9rification des limites. Attachez l'\u00e9l\u00e9ment souhait\u00e9 \u00e0 la fin du tableau, puis lancez le pointeur au d\u00e9but du tableau et proc\u00e9dez comme suit dans une boucle :<\/p>\n

      \n
    1. V\u00e9rifiez si l'\u00e9l\u00e9ment actuel est le d\u00e9sir\u00e9. Si c'est le cas, retournez la r\u00e9ponse si le pointeur est dans les limites du tableau, ou une erreur le cas \u00e9ch\u00e9ant. Sinon,\n<\/li>\n
    2. Augmentez le pointeur et continuez.<\/li>\n<\/ol>\n

      \nDe toute fa\u00e7on, l'\u00e9l\u00e9ment sera garanti d'\u00eatre trouv\u00e9, et la v\u00e9rification des limites n'est effectu\u00e9e qu'une seule fois, quand cela se produit. C'est une id\u00e9e profonde, mais elle est assez simple m\u00eame pour un programmeur d\u00e9butant. Je ne peux probablement pas parler de la pertinence du travail pour les autres, mais j'ai imm\u00e9diatement pu appliquer cette sagesse tant dans mon code personnel que professionnel. Le livre TAOCP regorge de telles perles (pour \u00eatre juste, il y a aussi beaucoup de choses \u00e9tranges, telles que le tri \u00e0 bulles<\/a><\/noindex>).<\/p>\n

      \u00ab Recherche, recherche
      \nSi longtemps
      \nRecherche, recherche
      \nJe voulais juste danser \u00bb<\/i>
      \n\u2014 Luther Vandross, \u00ab Recherche \u00bb (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Erreur typographique n\u00b02<\/h1>\n

      \nLa deuxi\u00e8me erreur est dans le tome 4A, \u00ab Algorithmes combinatoires \u00bb, partie 1. \u00c0 la page 60, un probl\u00e8me est d\u00e9crit concernant la planification des performances des humoristes dans diff\u00e9rents casinos. Comme exemple, plusieurs humoristes r\u00e9els sont mentionn\u00e9s, y compris Lily Tomlin, Weird Al Yankovic et Robin Williams, qui \u00e9tait encore vivant \u00e0 la sortie du livre. Knuth mentionne toujours les noms complets dans l'index, donc Williams est cit\u00e9 \u00e0 la page 882 comme \u00ab Williams, Robin Mac-Laurin \u00bb. Mais son deuxi\u00e8me pr\u00e9nom se termine par un \u00ab n \u00bb, pas par un \u00ab m \u00bb, c\u2019est-\u00e0-dire Mac-Laurin.<\/p>\n

      Mac-Laurin est le nom de jeune fille de sa m\u00e8re. Elle \u00e9tait l'arri\u00e8re-petite-fille d'Anselm Joseph Mac-Laurin, 34\u00e8me gouverneur du Mississippi. Son mandat ne semble manifestement pas avoir \u00e9t\u00e9 marqu\u00e9 par quelque chose de positif. Extrait du livre \u00ab Mississippi : histoire \u00bb<\/a><\/noindex>:<\/p>\n

      \u00ab L'\u00e9v\u00e9nement le plus important durant l'administration de Mac-Laurin fut la d\u00e9claration de guerre des \u00c9tats-Unis \u00e0 l'Espagne au printemps 1898\u2026 Malheureusement, la guerre a peut-\u00eatre donn\u00e9 \u00e0 certains fonctionnaires l'occasion de pratiquer la corruption. Mac-Laurin a \u00e9t\u00e9 accus\u00e9 de diverses pratiques douteuses, y compris le n\u00e9potisme et un abus excessif des pouvoirs accord\u00e9s pour accorder des pardons. \u00c0 une \u00e9poque de mouvement pour la temp\u00e9rance, les critiques ont accus\u00e9 le gouverneur d'ivrognerie, ce qu'il a publiquement admis. \u00bb<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Erreur historique<\/h1>\n

      \nExaminons algorithme traditionnel de multiplication<\/b> du programme scolaire. Combien d'op\u00e9rations de multiplication enkaines n\u00e9cessite-t-il ? Supposons que vous multipliez \"J'ai-un chiffre \"J'ai sur \"J'ai-chiffres \"J'ai. D'abord, vous multipliez le premier chiffre \"J'ai par chaque chiffre \"J'ai \u00e0 tour de r\u00f4le. Ensuite, vous multipliez le deuxi\u00e8me chiffre \"J'ai par chaque chiffre \"J'ai \u00e0 tour de r\u00f4le et ainsi de suite, jusqu'\u00e0 ce que vous passiez tous les chiffres \"J'ai. Ainsi, la multiplication traditionnelle n\u00e9cessite \"J'ai multiplications primitives. En particulier, multiplier deux nombres par \"J'ai chiffres n\u00e9cessite \"J'ai multiplications enkaines.<\/p>\n

      C'est mauvais, mais il est possible d'optimiser le processus gr\u00e2ce \u00e0 une m\u00e9thode d\u00e9velopp\u00e9e par le math\u00e9maticien sovi\u00e9tique Anatoly Alexe\u00efevitch Karatsuba. Supposons que \"J'ai et \"J'ai\u00a0soit des nombres d\u00e9cimaux \u00e0 deux chiffres ; c'est-\u00e0-dire qu'il existe des nombres \"J'ai, \"J'ai, \"J'ai, \"J'ai tels que \"J'ai et \"J'ai (g\u00e9n\u00e9raliser cet algorithme \u00e0 des chiffres plus grands n\u00e9cessite certaines manipulations ; bien que ce ne soit pas trop compliqu\u00e9, mais pour \u00e9viter de faire des erreurs dans les d\u00e9tails, je vais mieux m'en tenir \u00e0 un exemple simple). Alors \"J'ai, \"J'ai, \"J'ai. Multiplier des bin\u00f4mes donne \"J'ai. Pour l'instant, nous avons encore \"J'ai multiplications enkaines : \"J'ai, \"J'ai, \"J'ai, \"J'ai. Maintenant, additionnons et soustrayons. \"J'ai. Apr\u00e8s plusieurs r\u00e9arrangements, que je laisserai comme un exercice au lecteur, on obtient \"J'ai\u00a0\u2014 au total trois multiplications unidimensionnelles ! (Il y a quelques coefficients constants, mais ils ne peuvent \u00eatre calcul\u00e9s que par addition et d\u00e9calage des chiffres).<\/p>\n

      Ne demandez pas de preuve, mais l'algorithme de Karatsuba<\/b> (r\u00e9cursivement g\u00e9n\u00e9ralis\u00e9 de l'exemple ci-dessus) am\u00e9liore la m\u00e9thode de multiplication traditionnelle avec \"J'ai op\u00e9rations jusqu'\u00e0 \"J'ai. Notez qu'il s'agit d'une v\u00e9ritable am\u00e9lioration de l'algorithme, et non d'une optimisation pour les calculs mentaux. En effet, l'algorithme n'est pas adapt\u00e9 au calcul mental, car il n\u00e9cessite une surcharge importante d'op\u00e9rations r\u00e9cursives. De plus, l'effet ne se manifestera pas pleinement tant que les chiffres ne seront pas suffisamment grands (heureusement, d'autres m\u00e9thodes encore plus rapides ont \u00e9t\u00e9 introduites : en mars 2019, un algorithme a \u00e9t\u00e9 publi\u00e9, ne n\u00e9cessitant que n log n<\/i><\/a><\/noindex> multiplications ; l'acc\u00e9l\u00e9ration n'est applicable qu'\u00e0 des nombres immens\u00e9ment grands).<\/p>\n

      Cet algorithme est d\u00e9crit \u00e0 la page 295 du deuxi\u00e8me volume de \u00ab Algorithmes calculatoires \u00bb. L\u00e0, Knuth \u00e9crit : \u00ab Il est curieux que cette id\u00e9e n'ait \u00e9t\u00e9 d\u00e9couverte qu'en 1962<\/b> ann\u00e9e \u00bb, lorsque l'article d\u00e9crivant l'algorithme de Karatsuba a \u00e9t\u00e9 publi\u00e9. Mais ! En 1995, Karatsuba a publi\u00e9 un article sur \u00ab La complexit\u00e9 des calculs \u00bb, dans lequel il affirme plusieurs choses : 1) vers 1956, Kolmogorov a suppos\u00e9 qu'on ne pouvait pas multiplier en moins de \"J'ai \u00e9tapes ; 2) en 1960<\/b> ann\u00e9e, Karatsuba a assist\u00e9 \u00e0 un s\u00e9minaire o\u00f9 Kolmogorov a expos\u00e9 son hypoth\u00e8se n\u00b2. 3) \u00ab Juste une semaine plus tard \u00bb, Karatsuba a d\u00e9velopp\u00e9 l'algorithme \u00ab diviser pour r\u00e9gner \u00bb ; 4) en 1962, Kolmogorov a \u00e9crit et publi\u00e9 un article au nom de Karatsuba<\/i> d\u00e9crivant l'algorithme. \u00ab Je n'ai appris l'existence de cet article qu'apr\u00e8s qu'il a \u00e9t\u00e9 republi\u00e9 \u00bb.<\/p>\n

      Ainsi, l'erreur r\u00e9side dans le fait que au lieu de 1962<\/i> il devrait \u00eatre indiqu\u00e9 1960<\/i> l'ann\u00e9e. C'est tout.<\/p>\n

      Analyse<\/h1>\n

      \nLa recherche d'erreurs ne n\u00e9cessitait pas de comp\u00e9tences particuli\u00e8res.<\/b><\/p>\n

        \n
      1. La premi\u00e8re erreur \u00e9tait aussi banale que possible et se trouvait dans un endroit relativement visible (d\u00e9but de chapitre). N'importe quel idiot aurait pu la trouver ; il se trouve simplement que j'\u00e9tais cet idiot.\n<\/li>\n
      2. La recherche de la deuxi\u00e8me erreur de typographie a n\u00e9cessit\u00e9 de la chance et de l'ardeur, mais pas de comp\u00e9tence. L'index pour \u00ab Williams \u00bb se trouve \u00e0 l'avant-derni\u00e8re page du tome, une partie assez visible du livre. Je feuilletais justement l'index (ce n'est pas si grave que cela en a l'air, car des \u0153ufs de P\u00e2ques sont cach\u00e9s dans les index de Knuth. Par exemple, il y a des entr\u00e9es en arabe et en h\u00e9breu, et les deux indiquent la page 66. Mais cette page ne mentionne aucune des langues ; elle parle plut\u00f4t des \u00ab langues qui se lisent de droite \u00e0 gauche \u00bb). Et mon attention a \u00e9t\u00e9 attir\u00e9e par le deuxi\u00e8me pr\u00e9nom. Comme je consulte souvent Wikip\u00e9dia, j'ai v\u00e9rifi\u00e9 Robin Williams et j'ai remarqu\u00e9 une incoh\u00e9rence.\n<\/li>\n
      3. J'aimerais dire que j'ai fait des recherches s\u00e9rieuses pour trouver une erreur historique, mais en r\u00e9alit\u00e9, j'ai juste consult\u00e9 la page Wikip\u00e9dia de l'algorithme de Karatsuba.<\/a><\/noindex>Dans les premi\u00e8res lignes, il est \u00e9crit : \u00ab L'algorithme de Karatsuba est un algorithme de multiplication rapide. D\u00e9couvert par Anatoli Karatsuba en 1960 et publi\u00e9 en 1962 \u00bb. Apr\u00e8s cela, il ne restait plus qu'\u00e0 additionner deux fois deux.<\/li>\n<\/ol>\n

        \n\u00c0 l'avenir, j'aimerais trouver une erreur plus significative, notamment dans le code de Knuth. J'aimerais aussi d\u00e9nicher un bug dans le premier tome de \u00ab Les algorithmes fondamentaux \u00bb. Peut-\u00eatre que j'en aurais trouv\u00e9 un, mais pour une raison quelconque, la biblioth\u00e8que locale ne poss\u00e8de que les tomes 2, 3 et 4A.<\/p>\n

        Faits financiers :<\/b><\/p>\n