{"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\/pt\/blog\/news\/ya-poluchil-ot-knuta-chek-na-0x-3-00","title":{"rendered":"Eu recebi de Knuth um cheque de 0x$3,00","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Donald Knuth<\/b>\u00a0\u2014 um cientista da computa\u00e7\u00e3o que se preocupa tanto com a precis\u00e3o de seus livros que oferece um d\u00f3lar hexadecimal<\/b> ($2,56, 0x$1,00) por qualquer \"erro\" encontrado, onde um erro \u00e9 considerado tudo o que \u00e9 \"tecnicamente, historicamente, tipograficamente ou politicamente incorreto\". Eu realmente queria receber um cheque de Knuth, ent\u00e3o decidi procurar erros em sua obra-prima \"A Arte da Programa\u00e7\u00e3o\"<\/b> (TAOCP). Consegui encontrar tr\u00eas. Verdade seja dita, Knuth enviou um cheque de 0x$3,00<\/b>.<\/p>\n

\"Eu
\n
\nComo voc\u00ea pode ver, isso n\u00e3o \u00e9 um cheque real. Antes, Knuth enviava cheques reais, mas parou em 2008 devido a fraude desenfreada<\/a><\/noindex>. Agora ele envia \"certificados de dep\u00f3sito pessoais\" no Banco San Serif<\/a><\/noindex> (BoSS). Ele diz que est\u00e1 disposto a enviar dinheiro real se necess\u00e1rio, mas parece que isso \u00e9 um grande inc\u00f4modo.
\n<\/a><\/noindex>
\nEncontrei duas typos e um erro hist\u00f3rico. Listarei-os em ordem decrescente de trivialidade.<\/p>\n

Typo #1<\/h1>\n

\nA primeira typo \u2014 na p\u00e1gina 392 do terceiro volume \"Ordena\u00e7\u00e3o e Busca\", oitava linha a partir de baixo: \"Ap\u00f3s uma busca malsucedida, \u00e0s vezes (sometime) \u00e9 desej\u00e1vel inserir um novo registro na tabela contendo K<\/i>; o m\u00e9todo que faz isso \u00e9 chamado de algoritmo de busca e inser\u00e7\u00e3o. O erro \u00e9 que em vez de sometime<\/i><\/b> deveria ser sometimes<\/i><\/b>.<\/p>\n

Claro, n\u00e3o h\u00e1 nada surpreendente em tal erro. Apenas neste artigo, deve haver v\u00e1rias typos (nenhuma recompensa por encontr\u00e1-las). O que realmente surpreende \u00e9 que ningu\u00e9m notou por tanto tempo. A p\u00e1gina 392 n\u00e3o est\u00e1 escondida profundamente em uma se\u00e7\u00e3o de matem\u00e1tica, \u00e9 a primeira p\u00e1gina<\/b> do sexto cap\u00edtulo \"Busca\"! Talvez, uma das se\u00e7\u00f5es mais lidas do livro. Em teoria, deveria haver menos typos l\u00e1, mas n\u00e3o \u00e9 o caso.<\/p>\n

Por falar nisso, se voc\u00ea alguma vez pensou em ler o TAOCP, tente. Muitos dir\u00e3o que \u00e9 um manual<\/b>, n\u00e3o destinado \u00e0 leitura direta, mas isso n\u00e3o \u00e9 verdade. O autor tem um ponto de vista claro e um estilo distintivo. A \u00fanica coisa que dificulta a legibilidade \u00e9 a complexidade da matem\u00e1tica. No entanto, h\u00e1 uma solu\u00e7\u00e3o simples: leia at\u00e9 que chegue \u00e0 matem\u00e1tica que voc\u00ea n\u00e3o entende, pule-a e passe para a pr\u00f3xima se\u00e7\u00e3o que voc\u00ea consegue compreender. Lendo dessa forma, eu pulo pelo menos 80% do livro, mas os outros 20% s\u00e3o magn\u00edficos!<\/p>\n

Tamb\u00e9m dizem que o TAOCP \u00e9 irrelevante<\/b>, obsoleta ou de outra forma irrelevante para a \"programa\u00e7\u00e3o real\". Isso tamb\u00e9m n\u00e3o \u00e9 verdade. Por exemplo, na primeira se\u00e7\u00e3o ap\u00f3s a introdu\u00e7\u00e3o, \u00e9 discutida a busca de um elemento em um array n\u00e3o ordenado. O algoritmo mais simples \u00e9 conhecido por todos os programadores. Execute o ponteiro no in\u00edcio do array e, em seguida, execute as seguintes etapas em um loop:<\/p>\n

    \n
  1. Verifique se o elemento atual \u00e9 o desejado. Se for, retornamos; caso contr\u00e1rio,\n<\/li>\n
  2. Verifique se o ponteiro est\u00e1 fora do limite do array. Se estiver, retornamos um erro; caso contr\u00e1rio,\n<\/li>\n
  3. Aumente o ponteiro e continue.<\/li>\n<\/ol>\n

    \nAgora, vejamos: quantas verifica\u00e7\u00f5es de limite este algoritmo requer, em m\u00e9dia? No pior caso, quando o array n\u00e3o cont\u00e9m o elemento, para cada elemento na lista ser\u00e1 necess\u00e1ria uma verifica\u00e7\u00e3o, e, em m\u00e9dia, isso ser\u00e1 algo como \"Eu. Um algoritmo de busca mais inteligente pode se sair apenas com uma verifica\u00e7\u00e3o de limite. Anexe o elemento desejado ao final do array, em seguida, execute o ponteiro no in\u00edcio do array e execute as seguintes etapas em um loop:<\/p>\n

      \n
    1. Verifique se o elemento atual \u00e9 o desejado. Se for, retornamos a resposta se o ponteiro estiver dentro do limite do array ou um erro se n\u00e3o estiver. Caso contr\u00e1rio,\n<\/li>\n
    2. Aumente o ponteiro e continue.<\/li>\n<\/ol>\n

      \nDe qualquer forma, o elemento ser\u00e1 encontrado com certeza, e a verifica\u00e7\u00e3o de limites \u00e9 realizada apenas uma vez, quando isso ocorre. Essa \u00e9 uma ideia profunda, mas \u00e9 simples o suficiente at\u00e9 para um programador iniciante. Provavelmente, n\u00e3o posso falar sobre a relev\u00e2ncia do trabalho para os outros, mas consegui aplicar essa sabedoria imediatamente tanto em c\u00f3digos pessoais quanto profissionais. O livro TAOCP est\u00e1 cheio de tais joias (para ser justo, h\u00e1 tamb\u00e9m muitas coisas estranhas l\u00e1, como classifica\u00e7\u00e3o de bolha<\/a><\/noindex>).<\/p>\n

      \"Busca, busca
      \nT\u00e3o longa
      \nBusca, busca
      \nEu s\u00f3 queria dan\u00e7ar\"<\/i>
      \n\u2014 Luther Vandross, \"Busca\" (1980)<\/p><\/blockquote>\n

      <\/p>\n

      Erro de digita\u00e7\u00e3o n\u00ba 2<\/h1>\n

      \nO segundo erro est\u00e1 no volume 4A, \"Algoritmos Combinat\u00f3rios\", parte 1. Na p\u00e1gina 60, \u00e9 descrito um problema de planejamento de apresenta\u00e7\u00f5es de comediantes em v\u00e1rios cassinos. Como exemplo, s\u00e3o 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 \u00edndice, ent\u00e3o Williams \u00e9 mencionado na p\u00e1gina 882 como \"Williams, Robin McLorin\". Mas seu segundo nome termina em \"n\" e n\u00e3o em \"m\", ou seja, McLorin.<\/p>\n

      McLorin \u00e9 o sobrenome de solteira de sua m\u00e3e. Ela era bisneta de Anselm Joseph McLorin, o 34\u00ba governador do Mississippi. Seu governo, aparentemente, n\u00e3o foi lembrado por nada de bom. Do livro \"Mississippi: Hist\u00f3ria\"<\/a><\/noindex>:<\/p>\n

      \"O evento mais importante durante a administra\u00e7\u00e3o de McLorin foi a declara\u00e7\u00e3o de guerra dos Estados Unidos \u00e0 Espanha na primavera de 1898... Infelizmente, a guerra pode ter proporcionado a alguns funcion\u00e1rios p\u00fablicos a oportunidade de praticar corrup\u00e7\u00e3o. McLorin foi acusado de v\u00e1rias pr\u00e1ticas duvidosas, incluindo nepotismo e uso excessivo de poderes de indulto. Na era do movimento de temperan\u00e7a, cr\u00edticos acusaram o governador de beber, o que ele reconheceu publicamente.\"<\/i><\/p><\/blockquote>\n

      <\/p>\n

      Erro hist\u00f3rico<\/h1>\n

      \nVamos considerar o algoritmo tradicional de multiplica\u00e7\u00e3o<\/b> do programa escolar. Quantas opera\u00e7\u00f5es de multiplica\u00e7\u00e3o de um d\u00edgito ele requer? Suponha que voc\u00ea est\u00e1 multiplicando \"Euum n\u00famero de -d\u00edgitos \"Eu para \"Eude -d\u00edgitos \"Eu. Primeiro, voc\u00ea multiplica o primeiro d\u00edgito \"Eu por cada d\u00edgito \"Eu em ordem. Em seguida, multiplica o segundo d\u00edgito \"Eu por cada d\u00edgito \"Eu em ordem e assim por diante, at\u00e9 percorrer todos os d\u00edgitos \"Eu. Portanto, a multiplica\u00e7\u00e3o tradicional requer \"Eu multiplica\u00e7\u00f5es primitivas. Em particular, a multiplica\u00e7\u00e3o de dois n\u00fameros com \"Eu d\u00edgitos requer \"Eu multiplica\u00e7\u00f5es de um d\u00edgito.<\/p>\n

      Isso \u00e9 ruim, mas o processo pode ser otimizado usando um m\u00e9todo desenvolvido pelo matem\u00e1tico sovi\u00e9tico Anatoly Alexeyevich Karatsuba. Suponha que \"Eu e \"Eu\u00a0sejam n\u00fameros decimais de dois d\u00edgitos; ou seja, existem n\u00fameros \"Eu, \"Eu, \"Eu, \"Eu tais que \"Eu e \"Eu (a generaliza\u00e7\u00e3o deste algoritmo para d\u00edgitos maiores requer determinadas manipula\u00e7\u00f5es; embora isso n\u00e3o seja muito complicado, para n\u00e3o errar nos detalhes, prefiro manter um exemplo simples). Ent\u00e3o \"Eu, \"Eu, \"Eu. A multiplica\u00e7\u00e3o de bin\u00f4mios resulta em \"Eu. At\u00e9 agora, ainda temos \"Eu multiplica\u00e7\u00f5es de um d\u00edgito: \"Eu, \"Eu, \"Eu, \"Eu. Agora vamos somar e subtrair \"Eu. Ap\u00f3s algumas reorganiza\u00e7\u00f5es, que deixarei como um exerc\u00edcio para o leitor, obtemos \"Eu\u00a0\u2014 apenas tr\u00eas multiplica\u00e7\u00f5es de um d\u00edgito! (Existem alguns coeficientes constantes, mas eles podem ser calculados apenas com adi\u00e7\u00e3o e deslocamento de d\u00edgitos).<\/p>\n

      N\u00e3o pe\u00e7a provas, mas o algoritmo de Karatsuba<\/b> (generalizado recursivamente a partir do exemplo acima) melhora o m\u00e9todo tradicional de multiplica\u00e7\u00e3o com \"Eu opera\u00e7\u00f5es at\u00e9 \"Eu. Observe que isso \u00e9 uma verdadeira melhoria do algoritmo, e n\u00e3o uma otimiza\u00e7\u00e3o para c\u00e1lculos mentais. De fato, o algoritmo n\u00e3o \u00e9 adequado para c\u00e1lculos mentais, pois requer overhead significativo para opera\u00e7\u00f5es recursivas. Al\u00e9m disso, o efeito n\u00e3o se manifestar\u00e1 plenamente at\u00e9 que os n\u00fameros sejam grandes o suficiente (felizmente, em vez do algoritmo de Karatsuba, surgiram m\u00e9todos ainda mais r\u00e1pidos: em mar\u00e7o de 2019, foi publicado um algoritmo que requer apenas n log n<\/i><\/a><\/noindex> multiplica\u00e7\u00f5es; a acelera\u00e7\u00e3o \u00e9 aplic\u00e1vel apenas a n\u00fameros inimaginavelmente grandes).<\/p>\n

      Este algoritmo est\u00e1 descrito na p\u00e1gina 295 do segundo volume de \"Algoritmos das Artes da Computa\u00e7\u00e3o\". L\u00e1, Knuth escreve: \"Curiosamente, esta ideia foi descoberta apenas em 1962<\/b> ano\", quando foi publicado um artigo descrevendo o algoritmo de Karatsuba. Mas! Em 1995, Karatsuba publicou um artigo \"Complexidade dos C\u00e1lculos\", no qual menciona algumas coisas: 1) por volta de 1956, Kolmogorov sup\u00f4s que a multiplica\u00e7\u00e3o n\u00e3o poderia ser realizada em menos de \"Eu passos; 2) em 1960<\/b> ano, Karatsuba participou de um semin\u00e1rio onde Kolmogorov exp\u00f4s sua hip\u00f3tese n\u00b2. 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<\/i> descrevendo o algoritmo. \"Eu soube deste artigo apenas depois que o republicaram\".<\/p>\n

      Assim, o erro est\u00e1 no fato de que em vez de 1962<\/i> deveria ser indicado 1960<\/i> ano. Isso \u00e9 tudo.<\/p>\n

      An\u00e1lise<\/h1>\n

      \nA busca por erros n\u00e3o exigiu grande habilidade.<\/b><\/p>\n

        \n
      1. O primeiro erro era t\u00e3o banal quanto poss\u00edvel e estava em um lugar relativamente vis\u00edvel (o in\u00edcio do cap\u00edtulo). Qualquer idiota teria encontrado; apenas eu fui o idiota.\n<\/li>\n
      2. Encontrar o segundo erro de impress\u00e3o exigia sorte e esfor\u00e7o, mas n\u00e3o habilidade. O \u00edndice para \"Williams\" est\u00e1 na pen\u00faltima p\u00e1gina do volume, uma parte bastante vis\u00edvel do livro. Eu estava folheando o \u00edndice (isso n\u00e3o \u00e9 t\u00e3o doloroso quanto parece, pois nos \u00edndices de Knuth est\u00e3o escondidos ovos de p\u00e1scoa. Por exemplo, h\u00e1 entradas em \u00e1rabe e hebraico, e ambas indicam a p\u00e1gina 66. Mas nessa p\u00e1gina nenhum dos idiomas \u00e9 mencionado; em vez disso, s\u00e3o mencionados \"idiomas que s\u00e3o lidos da direita para a esquerda\"). E minha aten\u00e7\u00e3o foi atra\u00edda pelo segundo nome. Como costumo ler a Wikipedia, verifiquei Robin Williams e notei uma discrep\u00e2ncia.\n<\/li>\n
      3. Eu gostaria de dizer que fiz uma pesquisa s\u00e9ria para encontrar o erro hist\u00f3rico, mas na verdade apenas olhei para a p\u00e1gina da Wikipedia sobre o algoritmo de Karatsuba<\/a><\/noindex>. Nas primeiras linhas est\u00e1 escrito: \"O algoritmo de Karatsuba \u00e9 um algoritmo de multiplica\u00e7\u00e3o r\u00e1pida. Descoberto por Anatoly Karatsuba em 1960 e publicado em 1962\". Depois disso restou apenas somar dois mais dois.<\/li>\n<\/ol>\n

        \nNo futuro, eu gostaria de encontrar um erro mais substantivo, especialmente no c\u00f3digo de Knuth. Eu tamb\u00e9m gostaria de encontrar um bug no primeiro volume de \"Algoritmos Fundamentais\". Talvez eu encontrasse, mas por alguma raz\u00e3o a biblioteca local s\u00f3 possui os volumes 2, 3 e 4A.<\/p>\n

        Fatos financeiros:<\/b><\/p>\n