Donald Ervin Knuth ([kəˈnuːθ] kə-NOOTH-'; 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.
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" 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.
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").
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.