Donald Ervin Knuth ( ; nascido em 10 de janeiro de 1938) é um cientista da computação e matemático americano. Ele é professor emérito na Universidade de Stanford. É o recipiente de 1974 do Prêmio Turing da ACM, considerado informalmente como o Prêmio Nobel da ciência da computação. Knuth tem sido chamado de "pai da análise de algoritmos".
Knuth é o autor da obra em múltiplos volumes The Art of Computer Programming ("A Arte da Programação de Computadores"). Ele contribuiu para o desenvolvimento da análise rigorosa da complexidade computacional de algoritmos e sistematizou técnicas matemáticas formais para isso. No processo, ele também popularizou a notação Big O. Além de contribuições fundamentais em vários ramos da ciência da computação teórica, Knuth é o criador do sistema de diagramação computadorizada TeX, do sistema de definição e renderização de fontes relacionado METAFONT e da família de tipos de letra Computer Modern.
Como escritor e estudioso, Knuth criou os sistemas de programação de computadores WEB e CWEB projetados para incentivar e facilitar a programação literata, e projetou as arquiteturas de conjunto de instruções MIX/MMIX. Ele se opõe fortemente à concessão de patentes de software e expressou sua opinião ao Escritório de Patentes e Marcas dos Estados Unidos e à Organização Europeia de Patentes.
Biografia
Primeiros anos Donald Knuth nasceu em Milwaukee, Wisconsin, filho de Ervin Henry Knuth e Louise Marie Bohning. Ele descreve sua herança como "luterana alemã do meio-oeste". Seu pai possuía uma pequena gráfica e ensinava escrituração contábil. Quando estudante na Milwaukee Lutheran High School, Knuth pensava em maneiras engenhosas de resolver problemas. Por exemplo, na oitava série, ele entrou em um concurso para descobrir o número de palavras que as letras em "Ziegler's Giant Bar"Advertisement, Minneapolis Star, 13 de fevereiro de 1952, página 59. poderiam formar; os juízes haviam identificado 2.500 dessas palavras. Com o tempo ganho fora da escola devido a uma falsa dor de estômago, Knuth usou um dicionário completo e determinou se cada entrada do dicionário poderia ser formada usando as letras da frase. 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 no Case Institute of Technology (agora parte da Case Western Reserve University) em Cleveland, Ohio, matriculando-se em 1956. Ele também se juntou ao Capítulo Beta Nu da fraternidade Theta Chi. Enquanto estudava física no Case, Knuth foi apresentado ao IBM 650, um computador comercial antigo. Depois de 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 poderia fazê-lo 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 inovadora sobre a qual a Newsweek e o CBS Evening News relataram posteriormente.
Knuth foi um dos editores fundadores do Engineering and Science Review do Case Institute, que ganhou um prêmio nacional como melhor revista técnica em 1959. Ele então mudou da física para a matemática e recebeu dois diplomas do Case em 1960: seu Bacharelado em Ciências e, simultaneamente, um mestrado em ciências por uma premiação especial do corpo docente, que considerou seu trabalho excepcionalmente notável.
No final de seu último ano no Case em 1960, Knuth propôs à Burroughs Corporation escrever um compilador ALGOL para o B205 por $5.500. A proposta foi aceita e ele trabalhou no compilador ALGOL entre sua formatura no Case e sua ida para o Caltech.
Em 1963, com o matemático Marshall Hall como seu orientador, ele obteve um doutorado em matemática pelo Instituto de Tecnologia da Califórnia, com uma tese intitulada Finite Semifields and Projective Planes ("Semicorpos Finitos e Planos Projetivos").
Trabalho inicial Em 1963, após receber seu doutorado, Knuth ingressou no corpo docente do Caltech como professor assistente.
Enquanto estava no Caltech e após o sucesso do compilador ALGOL para o Burroughs B205, ele se tornou consultor da Burroughs Corporation, juntando-se ao Departamento de Planejamento de Produtos. No Caltech, ele atuava como matemático, mas na Burroughs como programador, trabalhando com as pessoas que ele considerava terem escrito o melhor software da época: o compilador ALGOL para o computador B220 (sucessor do B205).
Knuth recusou um contrato de $100.000 para escrever compiladores na Green Tree Corporation, decidindo em vez disso otimizar a renda e continuar no Caltech e na Burroughs. Ele recebeu uma Bolsa da National Science Foundation e uma Bolsa da Woodrow Wilson Foundation, mas elas tinham a condição de que o beneficiário não pudesse fazer mais nada além de estudar como aluno de pós-graduação, então ele não poderia continuar como consultor da Burroughs. Ele optou por recusar as bolsas e continuou com a Burroughs. No verão de 1962, ele escreveu um compilador FORTRAN para a Univac, mas considerou que "eu vendi minha alma ao diabo" para escrever um compilador FORTRAN.
Após se formar, Knuth retornou à Burroughs em junho de 1961, mas não lhes disse que havia se formado com um mestrado, em vez do bacharelado esperado. Impressionado com o gráfico de sintaxe do ALGOL, a tabela de símbolos, a abordagem de descida recursiva e a separação das funções de varredura, análise sintática e emissão do compilador, Knuth sugeriu uma extensão para a tabela de símbolos: que um símbolo poderia representar uma cadeia de símbolos. Isso se tornou a base do DEFINE no Burroughs ALGOL, que desde então foi adotado por outras linguagens. No entanto, alguns realmente não gostaram da ideia e queriam que o DEFINE fosse removido. A última pessoa a achar que era uma ideia terrível foi Edsger Dijkstra em uma visita à Burroughs.
Knuth trabalhou em linguagens de simulação na Burroughs, produzindo SOL 'Simulation Oriented Language' ("Linguagem Orientada a Simulação"), uma melhoria em relação ao estado da arte, co-projetada com J. McNeeley. Ele participou de uma conferência na Noruega em maio de 1967, organizada pelas pessoas que inventaram a linguagem Simula. Knuth influenciou a Burroughs a usar Simula. Knuth teve uma longa associação com a Burroughs como consultor de 1960 a 1968 até sua mudança para um trabalho mais acadêmico em Stanford em 1969.
Em 1962, Knuth aceitou uma comissão da Addison-Wesley para escrever um livro sobre compiladores de linguagem de programação de computadores. Enquanto trabalhava neste projeto, ele decidiu que não poderia tratar adequadamente o tópico sem primeiro desenvolver uma teoria fundamental da programação de computadores, que se tornou The Art of Computer Programming ("A Arte da Programação de Computadores"). Ele originalmente planejou publicar isso como um único livro, mas à medida que desenvolvia seu esboço para o livro, concluiu que precisaria 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 o Caltech para aceitar um emprego na Divisão de Pesquisa em Comunicações do Institute for Defense Analyses, então situada no campus da Princeton, que estava realizando pesquisas matemáticas 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".
Em 1969, Knuth deixou sua posição em Princeton para se juntar ao corpo docente da Universidade de Stanford, onde se tornou Professor de Ciência da Computação Fletcher Jones em 1977. Ele se tornou Professor de The Art of Computer Programming em 1990 e é emérito desde 1993.
Obras escritas Knuth é um escritor além de cientista da computação.
The Art of Computer Programming (TAOCP)
Na década de 1970, Knuth chamou a ciência da computação de "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íam eram simplesmente errados. ... Então, uma das minhas motivações foi endireitar uma história que havia sido contada muito mal."
De 1972 a 1973, Knuth passou um ano na Universidade de Oslo entre pessoas como Ole-Johan Dahl. Foi lá que ele originalmente pretendia escrever o sétimo volume de sua série de livros, que trataria de linguagens de programação. Mas Knuth havia terminado apenas os dois primeiros volumes quando chegou a Oslo, e assim passou o ano no terceiro volume, além de lecionar. O terceiro volume saiu logo após Knuth retornar a Stanford em 1973.
Concrete Mathematics: A Foundation for Computer Science ("Matemática Concreta: Uma Fundação para a Ciência da Computação") originou-se com uma expansão da seção de preliminares matemáticas do Volume 1 do TAoCP. Knuth descobriu que havia ferramentas matemáticas necessárias para o Volume 1, mas faltando em seu repertório, e decidiu que um curso introduzindo essas ferramentas para estudantes de ciência da computação seria útil. Knuth introduziu o curso em Stanford em 1970. As notas do curso desenvolvidas por Oren Patashnik evoluíram para o texto de 1988, com os autores Ronald Graham, Knuth e Patashnik. Uma segunda edição de Concrete Mathematics foi publicada em 1994.
Em 2011, o Volume 4A do TAoCP havia sido publicado. Em abril de 2020, Knuth disse que previa que o Volume 4 do TAoCP teria pelo menos as partes A a F. O Volume 4B foi publicado em outubro de 2022.
Outras obras Knuth é também o autor de Surreal Numbers ("Números Surreais"), uma novelinha matemática sobre a teoria dos conjuntos de John Horton Conway da construção de um sistema alternativo de números. Em vez de simplesmente explicar o assunto, o livro busca 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. Ele também contribui ocasionalmente com quebra-cabeças linguísticos para a Word Ways: The Journal of Recreational Linguistics.
Knuth se aprofundou na matemática recreativa. Ele contribuiu com artigos para o Journal of Recreational Mathematics a partir da década de 1960 e foi reconhecido como um importante colaborador em Mathematics on Vacation ("Matemática nas Férias") de Joseph Madachy.Madachy, Joseph S.,Mathematics on Vacation, Thomas Nelson & Sons Ltd. 1966
Knuth também aparece em vários vídeos do Numberphile e Computerphile no YouTube, onde discute tópicos desde a escrita de Surreal Numbers até por que ele não usa e-mail.
Knuth havia proposto o nome "algoritmica" como um nome melhor para a disciplina de ciência da computação.
Knuth fez uma contribuição substancial para o estudo do Problema do Emparelhamento Estável.. See in particular Problem 6, pp. 87–94.
Obras sobre suas crenças religiosas