A ciência é o que entendemos bem o suficiente para explicar a um computador; a arte é tudo o mais.
Donald Ervin Knuth é um cientista da computação, matemático e professor emérito da Universidade de Stanford. Ele é o destinatário do Prêmio Turing da ACM de 1974, informalmente considerado o Prêmio Nobel da ciência da computação. Knuth foi chamado de "pai da análise de algoritmos".
Ele é o autor da obra de múltiplos volumes The Art of Computer Programming. Contribuiu para o desenvolvimento da análise rigorosa da complexidade computacional de algoritmos e sistematizou técnicas matemáticas formais para isso. No processo, também popularizou a notação assintótica. Além de contribuições fundamentais em vários ramos da ciência da computação teórica, Knuth é o criador do sistema TeX de composição tipográfica computacional, da linguagem de definição de fontes METAFONT relacionada e do sistema de renderização, e da família Computer Modern de fontes tipográficas.
Como escritor e acadêmico, Knuth criou os sistemas de programação computacional WEB e CWEB, projetados para encorajar e facilitar a programação alfabetizada, e projetou as arquiteturas de conjunto de instruções MIX/MMIX. Knuth se opõe fortemente à concessão de patentes de software, tendo expressado sua opinião ao Escritório de Patentes e Marcas dos Estados Unidos e à Organização de Patentes Europeia.
Biografia
Primeiros anos
Knuth nasceu em Milwaukee, Wisconsin, de pais germano-americanos Ervin Henry Knuth e Louise Marie Bohning. Seu pai era proprietário de uma pequena gráfica e ensinava contabilidade. Donald, aluno da Milwaukee Lutheran High School, pensava em formas engenhosas de resolver problemas. Por exemplo, na oitava série, ele participou de um concurso para encontrar o número de palavras que as letras em "Ziegler's Giant Bar" poderiam ser reorganizadas para criar; os juízes haviam identificado 2.500 palavras assim. Com o tempo ganho da escola devido a uma dor de estômago fingida, e resolvendo o problema de forma inversa, Knuth usou um dicionário não abreviado e determinou se cada entrada do dicionário podia ser formada usando as letras da frase. Usando este algoritmo, ele identificou mais de 4.500 palavras, vencendo o concurso. Como prêmios, a escola recebeu uma nova televisão e barras de chocolate suficientes para todos os seus colegas de escola comerem.
Educação
Knuth recebeu uma bolsa de estudos em física para o Case Institute of Technology, agora parte da Case Western Reserve University em Cleveland, Ohio, matriculando-se em 1956. Ele também se juntou ao Beta Nu Chapter da fraternidade Theta Chi. Enquanto estudava física em Case, Knuth foi apresentado ao IBM 650, um computador comercial inicial. Após ler o manual do computador, Knuth decidiu reescrever o código de montagem e compilador para a máquina usada em sua escola, porque acreditava que podia fazer melhor.
Em 1958, Knuth criou um programa para ajudar o time de basquete de sua escola a vencer seus jogos. Ele atribuiu "valores" aos jogadores para avaliar sua probabilidade de marcar pontos, uma abordagem novel que Newsweek e CBS Evening News relataram posteriormente.
Knuth foi um dos editores fundadores da Engineering and Science Review do Case Institute, que ganhou um prêmio nacional como melhor revista técnica em 1959. Ele então mudou de física para matemática e recebeu dois graus de Case em 1960: seu diploma de bacharel em ciência e, simultaneamente, um mestrado em ciência por um prêmio especial da faculdade, que considerou seu trabalho excepcionalmente notável.
Em 1963, com o matemático Marshall Hall como seu orientador, ele obteve um PhD em matemática do California Institute of Technology.
Trabalho inicial
Após receber seu PhD, Knuth se juntou à faculdade de Caltech como professor assistente.
Ele aceitou uma comissão para escrever um livro sobre compiladores de linguagem de programação de computadores. Enquanto trabalhava neste projeto, Knuth decidiu que não poderia adequadamente tratar o tópico sem primeiro desenvolver uma teoria fundamental de programação de computadores, que se tornou The Art of Computer Programming. Ele originalmente planejava publicar isso como um único livro. Conforme Knuth desenvolveu seu esboço para o livro, ele concluiu que precisava de seis volumes, e depois sete, para cobrir completamente o assunto. Ele publicou o primeiro volume em 1968.
Pouco antes de publicar o primeiro volume de The Art of Computer Programming, Knuth deixou Caltech para aceitar emprego na Communications Research Division do Institute for Defense Analyses, que estava localizada no campus da Princeton University, que realizava pesquisa matemática em criptografia para apoiar a Agência de Segurança Nacional.
Em 1967, Knuth participou de uma conferência da Society for Industrial and Applied Mathematics e alguém perguntou o que ele fazia. Na época, a ciência da computação era dividida em análise numérica, inteligência artificial e linguagens de programação. Com base em seu estudo e no livro The Art of Computer Programming, Knuth decidiu que na próxima vez que alguém perguntasse, ele diria "Análise de algoritmos".
Knuth então deixou esta posição para se juntar à faculdade da Universidade de Stanford em 1969, onde é agora Fletcher Jones Professor of Computer Science, Emeritus.
Escritos
Knuth é um escritor, bem como um cientista da computação.
The Art of Computer Programming TAOCP
Na década de 1970, Knuth descreveu a ciência da computação como "um campo totalmente novo sem identidade real. E o padrão das publicações disponíveis não era tão alto. Muitos dos artigos que saíram estavam simplesmente errados. ... Então uma de minhas motivações era colocar em ordem uma história que havia sido muito mal contada." Até 2011, os três primeiros volumes e a primeira parte do volume quatro de sua série haviam sido publicados. Concrete Mathematics: A Foundation for Computer Science 2ª ed., que se originou com uma expansão da seção de preliminares matemáticos do Volume 1 do TAoCP, também foi publicada. Em abril de 2020, Knuth disse que está trabalhando intensamente na parte B do volume 4, e ele antecipa que o livro terá pelo menos partes A até F.
Outras obras
Knuth é também o autor de Surreal Numbers, uma noveleta matemática sobre a construção da teoria dos conjuntos de John Conway de um sistema alternativo de números. Em vez de simplesmente explicar o assunto, o livro procura mostrar o desenvolvimento da matemática. Knuth queria que o livro preparasse os alunos para fazer pesquisa original e criativa.
Em 1995, Knuth escreveu o prefácio do livro A=B de Marko Petkovšek, Herbert Wilf e Doron Zeilberger. Knuth é também um contribuidor ocasional de quebra-cabeças de linguagem para Word Ways: The Journal of Recreational Linguistics.
Knuth também se aprofundou em matemática recreativa. Ele contribuiu com artigos para o Journal of Recreational Mathematics começando nos anos 1960, e foi reconhecido como um grande contribuidor no Mathematics on Vacation de Joseph Madachy.
Knuth também apareceu em uma série de vídeos do Numberphile e Computerphile no YouTube, onde discutiu tópicos desde a escrita de Surreal Numbers até por que não usa e-mail.
Obras sobre as crenças religiosas de Knuth
Além de seus escritos sobre ciência da computação, Knuth, um luterano, é também o autor de 3:16 Bible Texts Illuminated, no qual ele examina a Bíblia através de um processo de amostragem sistemática, ou seja, uma análise do capítulo 3, versículo 16 de cada livro. Cada versículo é acompanhado por uma renderização em arte caligráfica, contribuída por um grupo de calígrafos sob a liderança de Hermann Zapf. Posteriormente, ele foi convidado a dar um conjunto de palestras no MIT sobre suas opiniões de religião e ciência da computação por trás de seu projeto 3:16, resultando em outro livro, Things a Computer Scientist Rarely Talks About, onde ele publicou as palestras "Deus e Ciência da Computação".
Opinião sobre patentes de software
Como membro da comunidade acadêmica e científica, Knuth é fortemente oposto à política de concessão de patentes de software para soluções triviais que deveriam ser óbvias, mas expressou opiniões mais nuançadas para soluções não-triviais, como o método de ponto interior da programação linear. Ele expressou seu desacordo diretamente tanto para o Escritório de Patentes e Marcas dos Estados Unidos quanto para a Organização de Patentes Europeia.
Computer Musings
Knuth dá palestras informais algumas vezes por ano na Universidade de Stanford, que ele intitulou "Computer Musings". Ele foi professor visitante no Department of Computer Science da Oxford University no Reino Unido até 2017 e um Fellow Honorário do Magdalen College.
Programação
Composição tipográfica digital
Na década de 1970, os editores do TAOCP abandonaram o Monotype em favor da fototipografia. Knuth ficou tão frustrado com a incapacidade do último sistema de se aproximar da qualidade dos volumes anteriores, que foram compostos usando o sistema mais antigo, que tirou tempo para trabalhar em composição tipográfica digital e criou TeX e Metafont.
Programação alfabetizada
Enquanto desenvolvia TeX, Knuth criou uma nova metodologia de programação, que ele chamou de programação alfabetizada, porque acreditava que os programadores deveriam pensar em programas como obras de literatura. "Em vez de imaginar que nossa principal tarefa é instruir um computador o que fazer, vamos nos concentrar em explicar aos seres humanos o que queremos que um computador faça."
Knuth incorporou a ideia de programação alfabetizada no sistema WEB. O mesmo código-fonte WEB é usado para tecer um arquivo TeX e para desembaraçar um arquivo-fonte Pascal. Estes, por sua vez, produzem uma descrição legível do programa e um binário executável respectivamente. Uma iteração posterior do sistema, CWEB, substitui Pascal por C.
Knuth usou WEB para programar TeX e METAFONT, e publicou ambos os programas como livros: The TeXbook, que foi originalmente publicado em 1984, e The METAFONTbook, que foi originalmente publicado em 1986. Na mesma época, LaTeX, o pacote de macros agora amplamente adotado baseado em TeX, foi primeiro desenvolvido por Leslie Lamport, que posteriormente publicou seu primeiro manual do usuário em 1986.
Música
Knuth é organista e compositor. Em 2016, ele completou uma peça musical para órgão intitulada Fantasia Apocalyptica, que ele descreve como "tradução do texto grego do Livro do Apocalipse de São João em música". Ela teve sua estreia na Suécia em 10 de janeiro de 2018.
Vida pessoal
Donald Knuth se casou com Nancy Jill Carter em 24 de junho de 1961, enquanto era aluno de pós-graduação no California Institute of Technology. Eles têm dois filhos: John Martin Knuth e Jennifer Sierra Knuth.
Nome chinês
O nome chinês de Knuth é Gao Dena. Em 1977, ele recebeu este nome de Frances Yao, pouco antes de fazer uma viagem de 3 semanas para a China. Em seu volume de 1980 de The Art of Computer Programming, Knuth explica que abraçou seu nome chinês porque queria ser conhecido pelos números crescentes de programadores de computadores na China naquela época. Em 1989, seu nome chinês foi colocado no topo do cabeçalho do Journal of Computer Science and Technology, que Knuth diz "me faz sentir perto de todo o povo chinês, embora eu não possa falar sua língua".
Problemas de saúde
Em 2006, Knuth foi diagnosticado com câncer de próstata. Ele se submeteu a uma cirurgia em dezembro daquele ano e afirmou, "um pouco de radioterapia ... como precaução, mas o prognóstico parece bastante bom", como ele relatou em sua autobiografia em vídeo.
Humor
Knuth costumava pagar uma taxa de localização de $2,56 por qualquer erro tipográfico ou erros descobertos em seus livros, porque "256 centavos é um dólar hexadecimal", e $0,32 por "sugestões valiosas". De acordo com um artigo do Technology Review do Massachusetts Institute of Technology, esses cheques de recompensa de Knuth estão entre "os troféus mais procurados da informática". Knuth teve que parar de enviar cheques reais em 2008 devido a fraude bancária, e em vez disso agora oferece a cada descobridor de erro um "certificado de depósito" de um saldo publicamente listado em seu fictício "Bank of San Serriffe".
Ele uma vez advertiu um correspondente, "Cuidado com bugs no código acima; eu apenas provei que está correto, não tentei."
Knuth publicou seu primeiro artigo "científico" em uma revista escolar em 1957 sob o título "The Potrzebie System of Weights and Measures". Nele, ele definiu a unidade fundamental de comprimento como a espessura de Mad No. 26, e nomeou a unidade fundamental de força "whatmeworry". Mad publicou o artigo na edição No. 33 de junho de 1957.
Para demonstrar o conceito de recursão, Knuth intencionalmente se referiu a "Definição circular" e "Circular definition" um ao outro no índice de The Art of Computer Programming, Volume 1.
O prefácio de Concrete Mathematics tem o seguinte parágrafo:
Quando DEK ensinou Concrete Mathematics em Stanford pela primeira vez, ele explicou o título um tanto estranho dizendo que era sua tentativa de ensinar um curso de matemática que era difícil em vez de fácil. Ele anunciou que, contrariamente às expectativas de seus colegas, ele não ia ensinar a Teoria dos Agregados, nem o Teorema de Incorporação de Stone, nem mesmo a compactificação Stone–Čech. (Vários alunos do departamento de engenharia civil se levantaram e silenciosamente deixaram a sala.)
Na Conferência TUG 2010, Knuth anunciou um sucessor satírico baseado em XML para TeX, intitulado "iTeX", pronunciado , realizado com um sino tocando, que suportaria recursos como unidades irracionais arbitrariamente escaladas, impressão 3D, entrada de seis
