Donald Knuth — um cientista da computação que se preocupa tanto com a precisão de seus livros que oferece um dólar hexadecimal ($2,56, 0x$1,00) por qualquer "erro" encontrado, onde um erro é considerado tudo o que é "tecnicamente, historicamente, tipograficamente ou politicamente incorreto". Eu realmente queria receber um cheque de Knuth, então decidi procurar erros em sua obra-prima "A Arte da Programação" (TAOCP). Consegui encontrar três. Verdade seja dita, Knuth enviou um cheque de 0x$3,00.

Como você pode ver, isso não é um cheque real. Antes, Knuth enviava cheques reais, mas parou em 2008 devido a fraude desenfreada. Agora ele envia "certificados de depósito pessoais" no Banco San Serif (BoSS). Ele diz que está disposto a enviar dinheiro real se necessário, mas parece que isso é um grande incômodo.

Encontrei duas typos e um erro histórico. Listarei-os em ordem decrescente de trivialidade.

Typo #1

A primeira typo — na página 392 do terceiro volume "Ordenação e Busca", oitava linha a partir de baixo: "Após uma busca malsucedida, às vezes (sometime) é desejável inserir um novo registro na tabela contendo K; o método que faz isso é chamado de algoritmo de busca e inserção. O erro é que em vez de sometime deveria ser sometimes.

Claro, não há nada surpreendente em tal erro. Apenas neste artigo, deve haver várias typos (nenhuma recompensa por encontrá-las). O que realmente surpreende é que ninguém notou por tanto tempo. A página 392 não está escondida profundamente em uma seção de matemática, é a primeira página do sexto capítulo "Busca"! Talvez, uma das seções mais lidas do livro. Em teoria, deveria haver menos typos lá, mas não é o caso.

Por falar nisso, se você alguma vez pensou em ler o TAOCP, tente. Muitos dirão que é um manual, não destinado à leitura direta, mas isso não é verdade. O autor tem um ponto de vista claro e um estilo distintivo. A única coisa que dificulta a legibilidade é a complexidade da matemática. No entanto, há uma solução simples: leia até que chegue à matemática que você não entende, pule-a e passe para a próxima seção que você consegue compreender. Lendo dessa forma, eu pulo pelo menos 80% do livro, mas os outros 20% são magníficos!

Também dizem que o TAOCP é irrelevante, obsoleta ou de outra forma irrelevante para a "programação real". Isso também não é verdade. Por exemplo, na primeira seção após a introdução, é discutida a busca de um elemento em um array não ordenado. O algoritmo mais simples é conhecido por todos os programadores. Execute o ponteiro no início do array e, em seguida, execute as seguintes etapas em um loop:

1. Verifique se o elemento atual é o desejado. Se for, retornamos; caso contrário,
2. Verifique se o ponteiro está fora do limite do array. Se estiver, retornamos um erro; caso contrário,
3. Aumente o ponteiro e continue.

Agora, vejamos: quantas verificações de limite este algoritmo requer, em média? No pior caso, quando o array não contém o elemento, para cada elemento na lista será necessária uma verificação, e, em média, isso será algo como . Um algoritmo de busca mais inteligente pode se sair apenas com uma verificação de limite. Anexe o elemento desejado ao final do array, em seguida, execute o ponteiro no início do array e execute as seguintes etapas em um loop:

1. Verifique se o elemento atual é o desejado. Se for, retornamos a resposta se o ponteiro estiver dentro do limite do array ou um erro se não estiver. Caso contrário,
2. Aumente o ponteiro e continue.

De qualquer forma, o elemento será encontrado com certeza, e a verificação de limites é realizada apenas uma vez, quando isso ocorre. Essa é uma ideia profunda, mas é simples o suficiente até para um programador iniciante. Provavelmente, não posso falar sobre a relevância do trabalho para os outros, mas consegui aplicar essa sabedoria imediatamente tanto em códigos pessoais quanto profissionais. O livro TAOCP está cheio de tais joias (para ser justo, há também muitas coisas estranhas lá, como classificação de bolha).

"Busca, busca
Tão longa
Busca, busca
Eu só queria dançar"
— Luther Vandross, "Busca" (1980)

Erro de digitação nº 2

O segundo erro está no volume 4A, "Algoritmos Combinatórios", parte 1. Na página 60, é descrito um problema de planejamento de apresentações de comediantes em vários cassinos. Como exemplo, são mencionados alguns comediantes reais, incluindo Lily Tomlin, Weird Al Yankovic e Robin Williams, que ainda estava vivo quando o livro foi publicado. Knuth sempre fornece os nomes completos no índice, então Williams é mencionado na página 882 como "Williams, Robin McLorin". Mas seu segundo nome termina em "n" e não em "m", ou seja, McLorin.

McLorin é o sobrenome de solteira de sua mãe. Ela era bisneta de Anselm Joseph McLorin, o 34º governador do Mississippi. Seu governo, aparentemente, não foi lembrado por nada de bom. Do livro "Mississippi: História":

"O evento mais importante durante a administração de McLorin foi a declaração de guerra dos Estados Unidos à Espanha na primavera de 1898... Infelizmente, a guerra pode ter proporcionado a alguns funcionários públicos a oportunidade de praticar corrupção. McLorin foi acusado de várias práticas duvidosas, incluindo nepotismo e uso excessivo de poderes de indulto. Na era do movimento de temperança, críticos acusaram o governador de beber, o que ele reconheceu publicamente."

Erro histórico

Vamos considerar o algoritmo tradicional de multiplicação do programa escolar. Quantas operações de multiplicação de um dígito ele requer? Suponha que você está multiplicando um número de -dígitos para de -dígitos . Primeiro, você multiplica o primeiro dígito por cada dígito em ordem. Em seguida, multiplica o segundo dígito por cada dígito em ordem e assim por diante, até percorrer todos os dígitos . Portanto, a multiplicação tradicional requer multiplicações primitivas. Em particular, a multiplicação de dois números com dígitos requer multiplicações de um dígito.

Isso é ruim, mas o processo pode ser otimizado usando um método desenvolvido pelo matemático soviético Anatoly Alexeyevich Karatsuba. Suponha que e  sejam números decimais de dois dígitos; ou seja, existem números , , , tais que e (a generalização deste algoritmo para dígitos maiores requer determinadas manipulações; embora isso não seja muito complicado, para não errar nos detalhes, prefiro manter um exemplo simples). Então , , . A multiplicação de binômios resulta em . Até agora, ainda temos multiplicações de um dígito: , , , . Agora vamos somar e subtrair . Após algumas reorganizações, que deixarei como um exercício para o leitor, obtemos  — apenas três multiplicações de um dígito! (Existem alguns coeficientes constantes, mas eles podem ser calculados apenas com adição e deslocamento de dígitos).

Não peça provas, mas o algoritmo de Karatsuba (generalizado recursivamente a partir do exemplo acima) melhora o método tradicional de multiplicação com operações até . Observe que isso é uma verdadeira melhoria do algoritmo, e não uma otimização para cálculos mentais. De fato, o algoritmo não é adequado para cálculos mentais, pois requer overhead significativo para operações recursivas. Além disso, o efeito não se manifestará plenamente até que os números sejam grandes o suficiente (felizmente, em vez do algoritmo de Karatsuba, surgiram métodos ainda mais rápidos: em março de 2019, foi publicado um algoritmo que requer apenas n log n multiplicações; a aceleração é aplicável apenas a números inimaginavelmente grandes).

Este algoritmo está descrito na página 295 do segundo volume de "Algoritmos das Artes da Computação". Lá, Knuth escreve: "Curiosamente, esta ideia foi descoberta apenas em 1962 ano", quando foi publicado um artigo descrevendo o algoritmo de Karatsuba. Mas! Em 1995, Karatsuba publicou um artigo "Complexidade dos Cálculos", no qual menciona algumas coisas: 1) por volta de 1956, Kolmogorov supôs que a multiplicação não poderia ser realizada em menos de passos; 2) em 1960 ano, Karatsuba participou de um seminário onde Kolmogorov expôs sua hipótese n². 3) "Exatamente uma semana depois" Karatsuba desenvolveu o algoritmo de "dividir e conquistar"; 4) em 1962, Kolmogorov escreveu e publicou um artigo em nome de Karatsuba descrevendo o algoritmo. "Eu soube deste artigo apenas depois que o republicaram".

Assim, o erro está no fato de que em vez de 1962 deveria ser indicado 1960 ano. Isso é tudo.

Análise

A busca por erros não exigiu grande habilidade.

1. O primeiro erro era tão banal quanto possível e estava em um lugar relativamente visível (o início do capítulo). Qualquer idiota teria encontrado; apenas eu fui o idiota.
2. Encontrar o segundo erro de impressão exigia sorte e esforço, mas não habilidade. O índice para "Williams" está na penúltima página do volume, uma parte bastante visível do livro. Eu estava folheando o índice (isso não é tão doloroso quanto parece, pois nos índices de Knuth estão escondidos ovos de páscoa. Por exemplo, há entradas em árabe e hebraico, e ambas indicam a página 66. Mas nessa página nenhum dos idiomas é mencionado; em vez disso, são mencionados "idiomas que são lidos da direita para a esquerda"). E minha atenção foi atraída pelo segundo nome. Como costumo ler a Wikipedia, verifiquei Robin Williams e notei uma discrepância.
3. Eu gostaria de dizer que fiz uma pesquisa séria para encontrar o erro histórico, mas na verdade apenas olhei para a página da Wikipedia sobre o algoritmo de Karatsuba. Nas primeiras linhas está escrito: "O algoritmo de Karatsuba é um algoritmo de multiplicação rápida. Descoberto por Anatoly Karatsuba em 1960 e publicado em 1962". Depois disso restou apenas somar dois mais dois.

No futuro, eu gostaria de encontrar um erro mais substantivo, especialmente no código de Knuth. Eu também gostaria de encontrar um bug no primeiro volume de "Algoritmos Fundamentais". Talvez eu encontrasse, mas por alguma razão a biblioteca local só possui os volumes 2, 3 e 4A.

Fatos financeiros:

• No total, minha contribuição para TAOCP consite apenas de três símbolos: uma adição s, uma substituição m para n e 2 para 0. Com um custo de $2,56, esses são símbolos bastante lucrativos; se você fosse pago essa quantia, um artigo de 1000 palavras (em média, com quatro símbolos) lhe renderia dez.
• Com três dólares hexadecimais, eu compartilho o 69º lugar na lista dos investidores mais ricos do Banco San Serif (a partir de 1º de maio de 2019).

Outras discussões sobre os cheques de Knuth

• Como obter um cheque de Knuth

  Diretrizes gerais para encontrar erros nos livros de Knuth. Elas geralmente dizem respeito a erros técnicos, que eu não possuo. Há uma frase que eu levei a sério:

  É melhor esperar até que você tenha um conjunto de erros para enviar. Ao combinar alguns erros reais, mas não muito valiosos, você aumentará a probabilidade de que um deles seja realmente considerado um erro ou uma sugestão. Se você enviar erros um por um, cada um deles pode ser rejeitado separadamente.

  Eu não queria enviar apenas erros bobos de digitação, mas segui o conselho e enviei o e-mail somente quando encontrei um erro histórico que me pareceu sério o suficiente.

• Cheques de Ashutosh Mehra

  Ashutosh Mehra é o terceiro maior investidor em San-Serif, com uma fortuna colossal de 0x$207,f0 no BoSS.

• Cheque por alguns erros não funcionais no código real do TeX
• Diversos: #1 #2 #3 #4 #5 #6

Fonte: habr.com