Donald Knuth é um cientista da computação que se preocupa tanto com a correção de seus livros que oferece um dólar hexadecimal (US $ 2,56, 0x US $ 1,00) por qualquer "erro" encontrado, onde tudo o que é "tecnicamente, historicamente, tipograficamente, é considerado um erro". ou politicamente errado. " Eu realmente queria receber um cheque de Knut, então decidi procurar erros em seu excelente trabalho "The Art of Programming" (TAOCP). Eu consegui encontrar três. Fiel à palavra, Knut enviou um cheque de 0x $ 3,00 .



Como você pode ver, essa não é uma verificação real. Knut costumava enviar cheques reais, mas parou em 2008 devido a uma fraude desenfreada . Agora ele envia "certificados pessoais de depósito" no Bank of San Serriff (BoSS). Ele diz que está pronto para enviar dinheiro real, se necessário, mas parece ser muito problemático.

Encontrei dois erros de digitação e um erro histórico. Vou listá-los em ordem decrescente de trivialidade.

Digitação número 1

O primeiro erro de digitação está na página 392 do terceiro volume “Classificar e Pesquisar”, a oitava linha da parte inferior: “Após uma pesquisa malsucedida, algumas vezes (em algum momento) é recomendável inserir um novo registro na tabela que contém K ; o método que faz isso é chamado de algoritmo de pesquisa e inserção. O erro é que, em vez de às vezes, deveria ser às vezes .

Obviamente, esse erro não é surpreendente. Somente neste artigo há alguns erros de digitação (não há recompensas por encontrá-los). O que é realmente surpreendente é que isso não é percebido há tanto tempo. A página 392 não está enterrada no fundo da seção de matemática, esta é a primeira página do sexto capítulo de “Pesquisa”! Talvez uma das seções mais lidas do livro. Em teoria, deve haver menos erros de digitação, mas não.

A propósito, se você já pensou em ler o TAOCP, experimente. Muitos dirão que este é um guia não destinado à leitura direta, mas isso não é verdade. O autor tem um ponto de vista claro e um estilo peculiar. A única coisa que impede a legibilidade é a complexidade da matemática. No entanto, existe uma solução simples: leia até chegar à matemática que você não entende, pule e abra a próxima seção que você entender. Lendo dessa maneira, sinto falta de pelo menos 80% do livro, mas os 20% restantes são ótimos!

Eles também dizem que o TAOCP é irrelevante , desatualizado ou inaplicável à "programação real". Isso também não é verdade. Por exemplo, na primeira seção após a introdução, a pesquisa por um elemento em uma matriz não classificada é considerada. O algoritmo mais simples é familiar para todos os programadores. Execute o ponteiro no início da matriz e faça o seguinte em um loop:

1. Verifique se o item atual é desejado. Se sim, devolva-o; caso contrário
   
2. Verifique se o ponteiro está fora da matriz. Se sim, retorne um erro; caso contrário
   
3. Aumente o ponteiro e continue.

Agora considere: quantas verificações de borda esse algoritmo exige, em média? Na pior das hipóteses, quando a matriz não contém um elemento, para cada elemento da lista é necessária uma verificação e, em média, será algo como $$$N / 2$. Um algoritmo de pesquisa mais inteligente pode funcionar com apenas uma verificação de borda. Anexe o elemento desejado ao final da matriz, execute o ponteiro no início da matriz e siga estas etapas em um loop:

1. Verifique se o item atual é desejado. Nesse caso, retornamos a resposta se o ponteiro estiver dentro da matriz ou um erro se não estiver. Caso contrário
   
2. Aumente o ponteiro e continue.

De uma maneira ou de outra, é garantido que o elemento seja encontrado e a verificação de borda é realizada apenas uma vez, quando isso aconteceu. Essa é uma idéia profunda, mas é bastante simples, mesmo para um programador iniciante. Provavelmente, não posso falar sobre a relevância do trabalho para os outros, mas pude aplicar imediatamente essa sabedoria no código pessoal e profissional. O livro do TAOCP está cheio dessas pérolas (na verdade, existem muitas coisas estranhas, como a classificação de bolhas ).

"Pesquisa, pesquisa
Tanto tempo
Pesquisa, pesquisa
Eu só queria dançar.
- Luther Wandross, Pesquisa (1980)

Digitação número 2

O segundo erro de digitação está no Volume 4A, Algoritmos Combinatórios, Parte 1. Na página 60, descrevemos a tarefa de planejar o desempenho de comediantes em vários cassinos. Alguns comediantes reais são citados como exemplo, incluindo Lily Tomlin, Strange Al Jankovic e Robin Williams, que ainda estavam vivos quando o livro foi lançado. Whip sempre fornece nomes completos no índice ; portanto, Williams é referido na página 882 como "Williams, Robin McLorim". Mas o nome do meio termina com "n", e não com "m", ou seja, McLoreen.

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

“O evento mais importante durante o governo McLorin foi os Estados Unidos declararem uma guerra da Espanha na primavera de 1898 ... Infelizmente, a guerra pode ter permitido que algumas autoridades do governo pratiquem suborno. McLorin foi acusado de várias práticas duvidosas, incluindo nepotismo e uso excessivo de poderes de perdão. Na era da sobriedade, os críticos acusaram o governador de embriaguez, que ele admitiu publicamente. ”

Erro histórico

Considere o algoritmo de multiplicação tradicional do currículo da escola. Quanto requer operações de multiplicação de um bit? Suponha que você multiplique $$$m$número de bits $$$x$em $$$n$-bit $$$y$. Primeiro, multiplique o primeiro dígito $$$x$para cada dígito $$$y$se revezam. Multiplique o segundo dígito $$$x$para cada dígito $$$y$se revezam e assim por diante até passar por todos os números $$$x$. Assim, a multiplicação tradicional requer $$$mn$multiplicações primitivas. Em particular, a multiplicação de dois números por $$$n$descargas requerem $$$n ^ 2$multiplicações de bit único.

Isso é ruim, mas você pode otimizar o processo usando o método desenvolvido pelo matemático soviético Anatoly Alekseevich Karatsuba. Suponha que $$$x$e $$$y$- números decimais de dois dígitos; ou seja, existem números $$$a$, $$$b$, $$$c$, $$$d$tal que $$$x = (ab) _ {10}$e $$$y = (cd) _ {10}$(a generalização desse algoritmo para grandes números requer certas manipulações; embora isso não seja muito difícil, mas para não ser confundido com os detalhes, é melhor seguir um exemplo simples). Então $$$x = 10a + b$, $$$y = 10 c + d$, $$$xy = (10a + b) (10c + d)$. A multiplicação de binômios fornece $$$xy = 100ac + 10ad + 10bc + bd$. No momento, ainda $$$n ^ 2 = 4$multiplicação de bit único: $$$ac$, $$$ad$, $$$bc$, $$$bd$. Agora adicione e subtraia $$$10ac + 10bc$. Depois de algumas permutações, que deixarei como exercício para o leitor, verifica-se $$ - apenas três multiplicações de um dígito! (Existem alguns coeficientes constantes, mas eles só podem ser calculados adicionando e deslocando os dígitos).

Não peça provas, mas o algoritmo Karatsuba (recursivamente generalizado a partir do exemplo acima) melhora o método tradicional de multiplicação com $$$O (n ^ 2)$operações antes $$$O (n ^ {(lg 3)})$. Observe que isso é uma melhoria real no algoritmo, não uma otimização para cálculos mentais. De fato, o algoritmo não é adequado para o cálculo mental, pois requer uma grande sobrecarga para operações recursivas. Além disso, o efeito não será totalmente aparente até que os números se tornem grandes o suficiente (felizmente, em vez do algoritmo Karatsuba, surgiram métodos ainda mais rápidos: em março de 2019, foi publicado um algoritmo que exigia apenas n log n multiplicações; a aceleração é aplicável apenas a inimaginavelmente grandes números).

Esse algoritmo é descrito na página 295 do segundo volume, Algoritmos Derivados. Knuth escreve: “É curioso que essa idéia tenha sido descoberta apenas em 1962 ” quando um artigo foi publicado descrevendo o algoritmo Karatsuba. Mas! Em 1995, Karatsuba publicou um artigo, “Complexity of Computing”, que diz várias coisas: 1) por volta de 1956, Kolmogorov sugeriu que a multiplicação não pode ser feita em menos de $$$O (n ^ 2)$etapas; 2) em 1960 , Karatsuba participou de um seminário em que Kolmogorov apresentou sua hipótese n². 3) “Exatamente em uma semana” A Karatsuba desenvolveu o algoritmo “dividir e conquistar”; 4) em 1962, Kolmogorov escreveu e publicou um artigo em nome de Karatsuba com uma descrição do algoritmo. "Eu só descobri este artigo depois que ele foi reimpresso."

Assim, o erro é que 1960 deve ser indicado em vez de 1962 . Isso é tudo.

Análise

A busca por erros não exigiu muita habilidade.

1. O primeiro erro foi o mais comum possível e estava em um lugar relativamente proeminente (o início do capítulo). Qualquer idiota a encontraria; Acabei de ser esse idiota.
   
2. Encontrar um segundo erro de digitação exigia sorte e diligência, mas não habilidade. O índice de "Williams" está na penúltima página do volume, uma parte bastante proeminente do livro. Eu estava folheando o índice (não é tão patético quanto parece, porque os ovos da Páscoa estão ocultos nos índices de Knuth. Por exemplo, existem entradas em árabe e hebraico, e ambas apontam para a página 66. Mas esta página também não menciona idiomas; em vez disso, refere-se a "idiomas lidos da direita para a esquerda"). E minha atenção foi atraída pelo nome do meio. Como costumo ler a Wikipedia, verifiquei Robin Williams e notei uma discrepância.
   
3. Eu gostaria de dizer que conduzi um estudo sério para encontrar um erro histórico, mas na verdade apenas olhei a página da Wikipedia sobre o algoritmo Karatsuba . As primeiras linhas dizem: “O algoritmo Karatsuba é um algoritmo para multiplicação rápida. Descoberto por Anatoly Karatsuba em 1960 e publicado em 1962. " Depois disso, restava apenas dobrar duas vezes dois.

No futuro, eu gostaria de encontrar um erro mais significativo, especialmente no código de Knuth. Eu também gostaria de encontrar um bug no primeiro volume, Algoritmos fundamentais. Talvez eu tivesse encontrado, mas por algum motivo, existem apenas os volumes 2, 3 e 4A na biblioteca local.

Fatos financeiros:

• No total, minha contribuição ao TAOCP consiste em apenas três caracteres: um adicionando s , substituindo m por n e 2 por 0 . Ao preço de US $ 2,56, esses são símbolos bastante lucrativos; se você recebesse esse tipo de dinheiro, um artigo de 1000 palavras (em média, quatro caracteres cada) lhe traria dez peças.
  
• Com três dólares hexadecimais, eu, juntamente com outros 29 cidadãos, compartilho o 69º lugar na lista dos depositantes mais ricos do Bank of San Serriff (em 1 de maio de 2019).

Outras discussões sobre verificações de Knut

• Como obter um cheque de Knut
  
  Diretrizes gerais para encontrar bugs nos livros de Knut. Principalmente erros técnicos que não tenho. Há uma sugestão que levei a sério:
  
  

  É melhor esperar até você coletar um conjunto de erros para enviar. Ao combinar vários erros reais, mas não muito valiosos, você aumentará a probabilidade de que um deles seja realmente considerado um erro ou conselho. Se você enviar erros um de cada vez, cada um individualmente poderá ser rejeitado.

  
  Não queria enviar erros sem sentido, mas segui o conselho e enviei uma carta apenas quando encontrei um erro histórico que parecia sério o suficiente.
  
• Cheques de Ashutosh Mehra
  
  Ashutosh Mehra é o terceiro colaborador mais rico de San Serriff, com uma fortuna enorme de 0x $ 207, f0 no BoSS.
  
• Verifique se há erros não funcionais no código TeX real
  
• Diversos: # 1 # 2 # 3 # 4 # 5 # 6