Donald Knuth é un informático que se preocupa tanto pola precisión dos seus libros que el suxire un dólar hexadecimal ($2,56, 0x$1,00) para calquera "erro" atopado, onde un erro se define como "técnicamente, historicamente, tipográficamente ou politicamente incorrecto". Realmente quería conseguir un cheque de Knuth, así que decidín buscar erros na súa obra magna "A arte da programación" (TAOCP). Conseguimos atopar tres. Fiel á súa palabra, Knut enviou un cheque para 0 x 3,00 $.

Como podes ver, esta non é unha verificación real. Knuth adoitaba enviar cheques reais, pero parou en 2008 debido a fraude desenfreado. Agora envía "certificados persoais de depósito" a Banco de San Serriff (Xefe). Di que está disposto a enviar cartos de verdade se é necesario, pero parece que é demasiado complicado.

Atopei dous erros tipográficos e un erro histórico. Enumereinos por orde de trivialidade decrecente.

Erro tipo 1

O primeiro erro tipográfico atópase na páxina 392 do terceiro volume de “Clasificación e busca”, oitava liña desde abaixo: “Despois dunha busca sen éxito, ás veces (ás veces) é desexable introducir un novo rexistro na táboa que contén K; o método que fai isto chámase algoritmo de busca e inserción. O erro é que en cambio nalgún momento debería ser ás veces.

Por suposto, tal erro non é sorprendente. Só neste artigo pode haber algúns erros tipográficos (non hai recompensas por atopalos). O realmente sorprendente é que pasou desapercibido durante tanto tempo. A páxina 392 non está enterrada profundamente na sección de matemáticas, si a primeira páxina Capítulo XNUMX "Buscar"! Posiblemente unha das seccións máis lidas do libro. En teoría, debería haber menos erros tipográficos, pero non.

Por certo, se algunha vez pensaches en ler TAOCP, probalo. Moitos dirán que isto é directorio, non destinado á lectura directa, pero isto non é certo. O autor ten un punto de vista claro e un estilo distintivo. O único que dificulta a lexibilidade é a complexidade das matemáticas. Non obstante, hai unha solución sinxela: le ata chegar ás matemáticas que non entendes, sáltaa e vai á seguinte sección que podes entender. Lendo deste xeito, boto de menos o 80% do libro, pero o outro 20% é xenial!

Tamén se di que TAOCP irrelevante, está desactualizado ou non é aplicable á "programación real". Isto tampouco é certo. Por exemplo, a primeira sección despois da introdución trata de atopar un elemento nunha matriz sen ordenar. O algoritmo máis sinxelo é familiar para todos os programadores. Comeza o punteiro ao principio da matriz e fai o seguinte nun bucle:

1. Comproba se o elemento actual é o desexado. Se é así, devolvémolo; en caso contrario
2. Comproba se o punteiro está fóra do límite da matriz. Se é así, devolve un erro; en caso contrario
3. Achega o zoom e continúa.

Agora considere: cantas comprobacións de límites require este algoritmo, de media? No peor dos casos, onde a matriz non contén un elemento, cada elemento da lista requirirá unha comprobación e, de media, será algo así como . Un algoritmo de busca máis intelixente podería saír con só unha comprobación de límites. Engade o elemento desexado ao final da matriz, despois inicie o punteiro ao principio da matriz e faga o seguinte nun bucle:

1. Comproba se o elemento actual é o desexado. Se é así, devolvemos unha resposta se o punteiro está dentro da matriz, ou un erro se non o está. En caso contrario
2. Achega o zoom e continúa.

Dun xeito ou doutro, o elemento está garantido para ser atopado, e a comprobación de límites realízase só unha vez cando isto ocorre. Esta é unha idea profunda, pero é bastante sinxela incluso para un programador novato. Probablemente non podo falar da relevancia do traballo para os demais, pero inmediatamente puiden aplicar esta sabedoría tanto ao código persoal como ao profesional. O libro TAOCP está cheo de tales xoias (para ser xustos, tamén hai moitas cousas estrañas alí, como clasificación de burbullas).

"Busca, busca
Moi longo
Busca, busca
Só quería bailar"
- Luther Vandross, "The Search" (1980)

Erro tipo 2

O segundo erro tipográfico atópase no Volume 4A, Combinatoria Algorithms, Parte 1. A páxina 60 describe un problema que implica a programación de comediantes para actuar en varios casinos. Cítanse como exemplos a varios cómicos da vida real, entre eles Lily Tomlin, Weird Al Yankovic e Robin Williams, que aínda estaba vivo cando se publicou o libro. Knuth sempre enumera os nomes completos no índice, polo que Williams aparece na páxina 882 como "Williams, Robin McLorim". Pero o seu segundo nome remata con "n" e non con "m", é dicir, McLaurin.

McLaurin era o nome de solteira da súa nai. Era a bisneta de Anselm Joseph McLaurin, 34º gobernador de Mississippi. O seu reinado, ao parecer, non foi lembrado para nada bo. Do libro "Mississippi: Historia":

“O acontecemento máis importante durante a administración McLaurin foi a declaración de guerra dos Estados Unidos a España na primavera de 1898... Desafortunadamente, a guerra puido ofrecer a algúns funcionarios do goberno a oportunidade de cometer subornos. McLaurin foi acusado de varias prácticas cuestionables, incluíndo nepotismo e uso excesivo de poderes de indulto. Durante o movemento de temperancia, os críticos acusaron ao gobernador de ser un borracho, o que admitiu publicamente.

Erro histórico

Considerar algoritmo de multiplicación tradicional do currículo escolar. Cantas multiplicacións dun só díxito precisa? Supoña que te multiplicas - Número de díxitos en - bit . Primeiro multiplica o primeiro díxito para cada díxito un por un. A continuación, multiplica o segundo díxito para cada díxito un por un e así ata pasar por todos os números . Así, a multiplicación tradicional require multiplicacións primitivas. En particular, multiplicando dous números por rangos necesarios multiplicacións dun só díxito.

Isto é malo, pero é posible optimizar o proceso mediante un método desenvolvido polo matemático soviético Anatoly Alekseevich Karatsuba. Imos finxir iso и  - números decimais de dúas cifras; é dicir, hai números , , , tal que и (Xeneralizar este algoritmo a números máis grandes require algunha manipulación; aínda que non é demasiado difícil, para non cometer erros nos detalles, mellor me atengo a un exemplo sinxelo). Entón , , . Multiplicando binomios dá . Polo momento aínda temos multiplicación dun díxito: , , , . Agora imos sumar e restar . Despois duns cantos reordenamentos, que deixarei como exercicio para o lector, resulta  - só tres multiplicacións dun só díxito! (Hai algúns coeficientes constantes, pero só se poden calcular sumando e desprazando os díxitos).

Non pidas probas, pero Algoritmo de Karatsuba (xeneralizado recursivamente a partir do exemplo anterior) mellora o método tradicional de multiplicación con operacións anteriores . Teña en conta que esta é unha mellora real do algoritmo, non unha optimización para os cálculos mentais. De feito, o algoritmo non é axeitado para a aritmética mental, xa que require grandes custos xerais para operacións recursivas. Ademais, o efecto non se manifestará por completo ata que os números sexan o suficientemente grandes (afortunadamente, o algoritmo de Karatsuba foi substituído por métodos aínda máis rápidos: en marzo de 2019, publicouse un algoritmo que só require n rexistro n multiplicacións; a aceleración só se aplica a números inimaxinábelmente grandes).

Este algoritmo descríbese na páxina 295 do Volume XNUMX, Algoritmos seminuméricos. Alí Knuth escribe: "É curioso que esta idea se descubra só en 1962 ano", cando se publicou un artigo que describe o algoritmo de Karatsuba. Pero! En 1995, Karatsuba publicou un artigo "Computational Complexity", que di varias cousas: 1) ao redor de 1956, Kolmogorov suxeriu que a multiplicación non se pode facer en menos de pasos; 2) en 1960 ano Karatsuba asistiu ao seminario onde Kolmogorov presentou a súa hipótese n². 3) "En exactamente unha semana", Karatsuba desenvolveu o algoritmo "divide e vencerás"; 4) en 1962 Kolmogorov escribiu e publicou un artigo en nome de Karatsuba cunha descrición do algoritmo. "Só me decatei deste artigo despois de que foi republicado".

Entón, o erro é que en vez de 1962 debe especificarse 1960 ano. Iso é todo.

Análise

Atopar erros non requiriu habilidade especial.

1. O primeiro erro foi o máis trivial posible e estivo nun lugar relativamente visible (o comezo do capítulo). Calquera idiota teríao atopado; Acabo de resultar ser ese idiota.
2. Encontrar o segundo erro esixiu sorte e dilixencia, pero non habilidade. O índice de "Williams" está na penúltima páxina do volume, unha parte bastante destacada do libro. Só estaba pasando o índice (non é tan patético como parece, porque hai ovos de Pascua agochados nos índices de Knuth. Por exemplo, hai entradas en árabe e en hebreo, ambas apuntan á páxina 66. Pero esa páxina non menciona. calquera dos dous idiomas; en cambio, refírese a "idiomas que se len de dereita a esquerda"). E o segundo nome chamoume a atención. Como adoito ler a Wikipedia, comprobei a Robin Williams e notei unha discrepancia.
3. Gustaríame poder dicir que fixen unha investigación seria para atopar un erro histórico, pero en realidade só mirei Páxina da Wikipedia sobre o algoritmo de Karatsuba. As primeiras liñas din: "O algoritmo de Karatsuba é un algoritmo de multiplicación rápida. Descuberto por Anatoly Karatsuba en 1960 e publicado en 1962. Despois diso só quedaba sumar dous e dous.

No futuro gustaríame atopar un erro máis significativo, especialmente no código de Knuth. Tamén me gustaría atopar un erro no primeiro volume de Algoritmos fundamentais. Quizais o atopara, pero por algo a biblioteca local só ten os volumes 2, 3 e 4A.

Datos financeiros:

• En total, a miña contribución a TAOCP consiste só en tres personaxes: un engadido s, substitución m en n и 2 en 0. A 2,56 dólares, estes son algúns símbolos bastante lucrativos; Se che pagasen ese tipo de diñeiro, un artigo de 1000 palabras (unha media de catro caracteres) gañaríache dez mil.
• Con tres dólares hexadecimais, eu, xunto con outros 29 cidadáns, estou empatado no posto 69 da lista dos depositantes máis ricos do Banco San Serriff (a partir do 1 de maio de 2019).

Outras discusións sobre cheques de Knuth

• Como conseguir un cheque de Knuth

  Recomendacións xerais para atopar erros nos libros de Knuth. Principalmente se refiren a erros técnicos, que non teño. Hai unha suxestión que tomei en serio:

  É mellor esperar ata que recolla un conxunto de erros para enviar. Ao combinar varios erros reais pero non moi valiosos, aumenta a probabilidade de que un deles sexa realmente considerado un erro ou un consello. Se envía os erros un a un, cada un pode ser rexeitado individualmente.

  Non quería enviar só erros tipográficos de tonterías, senón que aceptei o consello e enviei a carta só cando atopei un erro histórico que me parecía o suficientemente grave.

• Cheques de Ashutosh Mehra

  Ashutosh Mehra é o terceiro investidor máis rico de San Serriff cun enorme patrimonio neto de 0x$207.f0 en BoSS.

• Comprobe algúns erros non funcionais no código TeX real
• Varios: #1 #2 #3 #4 #5 #6

Fonte: www.habr.com