Donald Knuth — un scientifique en informatique qui tient tellement à la précision de ses livres qu'il propose un dollar hexadécimal ($2,56, 0x$1,00) pour toute "erreur" trouvée, où une erreur est définie comme tout ce qui est "techniquement, historiquement, typographiquement ou politiquement incorrect". J'étais très désireux de recevoir un chèque de Knuth, donc j'ai décidé de chercher des erreurs dans son œuvre exceptionnelle «L'Art de la Programmation» (TAOCP). J'ai réussi à en trouver trois. Fidèle à sa parole, Knuth a envoyé un chèque de 0x$3,00.
Comme vous pouvez le voir, ce n'est pas un vrai chèque. Auparavant, Knuth envoyait de vrais chèques, mais il a arrêté en 2008 à cause de . Maintenant, il envoie des "certificats de dépôt personnels" à (BoSS). Il dit qu'il est prêt à envoyer de l'argent réel si nécessaire, mais cela semble trop compliqué.
J'ai trouvé deux coquilles et une erreur historique. Je vais les énumérer par ordre décroissant de trivialité.
Coquille n°1
La première coquille se trouve à la page 392 du troisième volume "Tri et Recherche", huitième ligne en bas : «Après une recherche infructueuse, il peut parfois (sometime) être souhaitable d'insérer un nouvel enregistrement dans le tableau, contenant K; la méthode qui le fait s'appelle l'algorithme de recherche et d'insertion. L'erreur est que, à la place de sometime cela devrait être sometimes.
Bien sûr, il n'y a rien de surprenant dans une telle erreur. Dans cet article, il y aura sûrement plusieurs coquilles (aucune récompense pour les trouver). Ce qui est vraiment surprenant, c'est que cela n'a pas été remarqué plus tôt. La page 392 n'est pas profondément enfouie dans la section mathématique, c'est la toute première page du sixième chapitre "Recherche" ! Peut-être l'une des sections les plus lues du livre. En théorie, il devrait y avoir le moins de coquilles, mais non.
D'ailleurs, si jamais vous avez pensé à lire TAOCP, essayez. Beaucoup diront que c'est un manuel, pas destiné à une lecture directe, mais c'est faux. L'auteur a un point de vue clair et un style unique. La seule chose qui nuit à la lisibilité est la complexité des mathématiques. Pourtant, il existe une solution simple : lisez jusqu'à ce que vous atteigniez les mathématiques que vous ne comprenez pas, sautez-les et passez au prochain chapitre que vous pouvez comprendre. En lisant de cette manière, je saute au moins 80 % du livre, mais les 20 % restants sont magnifiques !
On dit également que TAOCP n'est pas pertinent, obsolète ou autrement inapplicable à « la programmation réelle ». C'est aussi faux. Par exemple, dans la première section après l'introduction, on aborde la recherche d'un élément dans un tableau non trié. L'algorithme le plus simple est connu de tous les programmeurs. Placez un pointeur au début du tableau, puis procédez comme suit dans une boucle :
- Vérifiez si l'élément actuel est le désiré. Si c'est le cas, retournez-le ; sinon,
- Vérifiez si le pointeur est hors des limites du tableau. Si c'est le cas, retournez une erreur ; sinon,
- Augmentez le pointeur et continuez.
Maintenant, examinons : combien de vérifications de limites nécessite cet algorithme en moyenne ? Dans le pire des cas, lorsque le tableau ne contient pas l'élément, il faudra une vérification pour chaque élément de la liste, et en moyenne, cela ressemblera à quelque chose comme 
. Un algorithme de recherche plus intelligent pourrait ne nécessiter qu'une seule vérification des limites. Attachez l'élément souhaité à la fin du tableau, puis lancez le pointeur au début du tableau et procédez comme suit dans une boucle :
- Vérifiez si l'élément actuel est le désiré. Si c'est le cas, retournez la réponse si le pointeur est dans les limites du tableau, ou une erreur le cas échéant. Sinon,
- Augmentez le pointeur et continuez.
De toute façon, l'élément sera garanti d'être trouvé, et la vérification des limites n'est effectuée qu'une seule fois, quand cela se produit. C'est une idée profonde, mais elle est assez simple même pour un programmeur débutant. Je ne peux probablement pas parler de la pertinence du travail pour les autres, mais j'ai immédiatement pu appliquer cette sagesse tant dans mon code personnel que professionnel. Le livre TAOCP regorge de telles perles (pour être juste, il y a aussi beaucoup de choses étranges, telles que ).
« Recherche, recherche
Si longtemps
Recherche, recherche
Je voulais juste danser »
— Luther Vandross, « Recherche » (1980)
Erreur typographique n°2
La deuxième erreur est dans le tome 4A, « Algorithmes combinatoires », partie 1. À la page 60, un problème est décrit concernant la planification des performances des humoristes dans différents casinos. Comme exemple, plusieurs humoristes réels sont mentionnés, y compris Lily Tomlin, Weird Al Yankovic et Robin Williams, qui était encore vivant à la sortie du livre. Knuth mentionne toujours les noms complets dans l'index, donc Williams est cité à la page 882 comme « Williams, Robin Mac-Laurin ». Mais son deuxième prénom se termine par un « n », pas par un « m », c’est-à-dire Mac-Laurin.
Mac-Laurin est le nom de jeune fille de sa mère. Elle était l'arrière-petite-fille d'Anselm Joseph Mac-Laurin, 34ème gouverneur du Mississippi. Son mandat ne semble manifestement pas avoir été marqué par quelque chose de positif. Extrait du livre :
« L'événement le plus important durant l'administration de Mac-Laurin fut la déclaration de guerre des États-Unis à l'Espagne au printemps 1898… Malheureusement, la guerre a peut-être donné à certains fonctionnaires l'occasion de pratiquer la corruption. Mac-Laurin a été accusé de diverses pratiques douteuses, y compris le népotisme et un abus excessif des pouvoirs accordés pour accorder des pardons. À une époque de mouvement pour la tempérance, les critiques ont accusé le gouverneur d'ivrognerie, ce qu'il a publiquement admis. »
Erreur historique
Examinons algorithme traditionnel de multiplication du programme scolaire. Combien d'opérations de multiplication enkaines nécessite-t-il ? Supposons que vous multipliez 
-un chiffre 
sur 
-chiffres 
. D'abord, vous multipliez le premier chiffre 
par chaque chiffre 
à tour de rôle. Ensuite, vous multipliez le deuxième chiffre 
par chaque chiffre 
à tour de rôle et ainsi de suite, jusqu'à ce que vous passiez tous les chiffres 
. Ainsi, la multiplication traditionnelle nécessite 
multiplications primitives. En particulier, multiplier deux nombres par 
chiffres nécessite 
multiplications enkaines.
C'est mauvais, mais il est possible d'optimiser le processus grâce à une méthode développée par le mathématicien soviétique Anatoly Alexeïevitch Karatsuba. Supposons que 
et 
soit des nombres décimaux à deux chiffres ; c'est-à-dire qu'il existe des nombres 
, 
, 
, 
tels que 
et 
(généraliser cet algorithme à des chiffres plus grands nécessite certaines manipulations ; bien que ce ne soit pas trop compliqué, mais pour éviter de faire des erreurs dans les détails, je vais mieux m'en tenir à un exemple simple). Alors 
, 
, 
. Multiplier des binômes donne 
. Pour l'instant, nous avons encore 
multiplications enkaines : 
, 
, 
, 
. Maintenant, additionnons et soustrayons. 
. Après plusieurs réarrangements, que je laisserai comme un exercice au lecteur, on obtient 
— au total trois multiplications unidimensionnelles ! (Il y a quelques coefficients constants, mais ils ne peuvent être calculés que par addition et décalage des chiffres).
Ne demandez pas de preuve, mais l'algorithme de Karatsuba (récursivement généralisé de l'exemple ci-dessus) améliore la méthode de multiplication traditionnelle avec 
opérations jusqu'à 
. Notez qu'il s'agit d'une véritable amélioration de l'algorithme, et non d'une optimisation pour les calculs mentaux. En effet, l'algorithme n'est pas adapté au calcul mental, car il nécessite une surcharge importante d'opérations récursives. De plus, l'effet ne se manifestera pas pleinement tant que les chiffres ne seront pas suffisamment grands (heureusement, d'autres méthodes encore plus rapides ont été introduites : en mars 2019, un algorithme a été publié, ne nécessitant que multiplications ; l'accélération n'est applicable qu'à des nombres immensément grands).
Cet algorithme est décrit à la page 295 du deuxième volume de « Algorithmes calculatoires ». Là, Knuth écrit : « Il est curieux que cette idée n'ait été découverte qu'en 1962 année », lorsque l'article décrivant l'algorithme de Karatsuba a été publié. Mais ! En 1995, Karatsuba a publié un article sur « La complexité des calculs », dans lequel il affirme plusieurs choses : 1) vers 1956, Kolmogorov a supposé qu'on ne pouvait pas multiplier en moins de 
étapes ; 2) en 1960 année, Karatsuba a assisté à un séminaire où Kolmogorov a exposé son hypothèse n². 3) « Juste une semaine plus tard », Karatsuba a développé l'algorithme « diviser pour régner » ; 4) en 1962, Kolmogorov a écrit et publié un article au nom de Karatsuba décrivant l'algorithme. « Je n'ai appris l'existence de cet article qu'après qu'il a été republié ».
Ainsi, l'erreur réside dans le fait que au lieu de 1962 il devrait être indiqué 1960 l'année. C'est tout.
Analyse
La recherche d'erreurs ne nécessitait pas de compétences particulières.
- La première erreur était aussi banale que possible et se trouvait dans un endroit relativement visible (début de chapitre). N'importe quel idiot aurait pu la trouver ; il se trouve simplement que j'étais cet idiot.
- La recherche de la deuxième erreur de typographie a nécessité de la chance et de l'ardeur, mais pas de compétence. L'index pour « Williams » se trouve à l'avant-dernière 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 œufs de Pâques sont cachés dans les index de Knuth. Par exemple, il y a des entrées en arabe et en hébreu, et les deux indiquent la page 66. Mais cette page ne mentionne aucune des langues ; elle parle plutôt des « langues qui se lisent de droite à gauche »). Et mon attention a été attirée par le deuxième prénom. Comme je consulte souvent Wikipédia, j'ai vérifié Robin Williams et j'ai remarqué une incohérence.
- J'aimerais dire que j'ai fait des recherches sérieuses pour trouver une erreur historique, mais en réalité, j'ai juste consulté Dans les premières lignes, il est écrit : « L'algorithme de Karatsuba est un algorithme de multiplication rapide. Découvert par Anatoli Karatsuba en 1960 et publié en 1962 ». Après cela, il ne restait plus qu'à additionner deux fois deux.
À l'avenir, j'aimerais trouver une erreur plus significative, notamment dans le code de Knuth. J'aimerais aussi dénicher un bug dans le premier tome de « Les algorithmes fondamentaux ». Peut-être que j'en aurais trouvé un, mais pour une raison quelconque, la bibliothèque locale ne possède que les tomes 2, 3 et 4A.
Faits financiers :
- En tout, ma contribution à TAOCP se limite à trois symboles : une addition s, un remplacement m sur n et 2 sur 0. À 2,56 $, ce sont des symboles assez rentables ; si on vous payait ainsi, un article de 1000 mots (en moyenne, environ quatre symboles) vous rapporterait dix billets.
- Avec trois dollars hexadécimaux, je partage, avec 29 autres citoyens, la 69e place sur la liste des plus riches contributeurs de la banque San Serif (au 1er mai 2019).
D'autres discussions sur les chèques de Knuth
Recommandations générales pour la recherche d'erreurs dans les livres de Knuth. Elles concernent principalement les erreurs techniques, dont je n'ai pas. Il y a une phrase que j'ai prise au sérieux :
Il vaut mieux attendre d'avoir un ensemble d'erreurs à envoyer. En regroupant plusieurs erreurs réelles mais peu convaincantes, vous augmentez la probabilité que l'une d'elles soit effectivement considérée comme une erreur ou un conseil. Si vous envoyez des erreurs une par une, chacune peut être rejetée.
Je ne voulais pas envoyer de simples erreurs futiles, alors j'ai suivi le conseil et j'ai envoyé le message seulement après avoir trouvé une erreur historique que je pensais assez sérieuse.
Ashutosh Mehra est le troisième contributeur le plus riche de San-Seriff avec une immense fortune de 0x$207,f0 dans BoSS.
- Divers :
Source : habr.com
