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 e, em 1974, recebedor do Prêmio Turing da ACM, informalmente considerado o Nobel da ciência da computação. Knuth tem sido chamado o "pai da análise de algoritmos" e é o autor da obra em vários volumes The Art of Computer Programming.
Knuth contribuiu ao desenvolvimento da análise rigorosa da complexidade computacional e sistematizou técnicas matemáticas formais para ela, popularizando a notação assintótica. Ele também é o criador do sistema de tipografia computacional TeX, da linguagem de definição de fontes METAFONT e das tipografías Computer Modern. Como escritor e estudioso, ele criou os sistemas de programação WEB e CWEB para programação literária e projetou as arquiteturas de conjunto de instruções MIX/MMIX. Ele se opone firmemente às patentes de software e expressou suas opiniões ao United States Patent and Trademark Office e à European Patent Organisation.
Vida Inicial e Educação
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 um pequeno negócio de impressão e ensinava contabilidade. Durante o ensino médio na Milwaukee Lutheran High School, Knuth mostrou uma precoce capacidade de resolução de problemas. Na oitava série, ele participou de um concurso para encontrar o número de palavras que podían ser rearranjadas das letras em "Ziegler's Giant Bar". Os jurados haviam identificado 2.500 palavras; Knuth, usando um dicionário não abreviado durante um dia falso de doença, encontrou mais de 4.500 palavras e venceu. A escola recebiu uma televisión e barras de chocolate para todos os estudantes.
Knuth recebiu uma bolsa de estudos em física para o Case Institute of Technology (agora parte da Case Western Reserve University) em 1956. Ele se unió ao Capítulo Beta Nu da fraternidade Theta Chi. Introducido ao IBM 650, um dos primeiros computadores comerciales, ele leu seu manual e decidió reescribir o código de montagem e compilador para a máquina, acreditando que podía fazer melhor. Em 1958, ele crió um programa para ajudar a equipe de basquetbol a vencer atribuindo "valores" aos jogadores para medir a probabilidade de pontuação - uma abordagem novedosa reportada por Newsweek e CBS Evening News.
Knuth foi editor fundador do Engineering and Science Review, que ganó um prêmio nacional em 1959. Ele passou da física à matemática e recebiu tanto um Bachelor of Science como um mestrado em 1960, este último por prêmio especial da faculdade. No final de seu último ano, ele propuso à Burroughs Corporation escrever um compilador ALGOL para o B205 por $5.500; a proposta foi aceitada, e ele trabalhou nela entre Case e Caltech. Em 1963, ele obtuvo um PhD em matemática do California Institute of Technology, com Marshall Hall como conselheiro, sobre a tesis Finite Semifields and Projective Planes.
Início da Carreira e The Art of Computer Programming
Depois de receber seu PhD, Knuth se unió à faculdade de Caltech como professor assistente em 1963. Ele também se tornó consultor da Burroughs Corporation, trabalhando no compilador ALGOL para o B220. Ele rejeitó um contrato de $100.000 da Green Tree Corporation para continuar em Caltech e Burroughs. Ele declinó bolsas da National Science Foundation e Woodrow Wilson porque terían impedido o trabalho de consultoría. No verano de 1962, ele escreviu um compilador FORTRAN para Univac, dizendo depois que "vendí mi alma al diablo".
Em Burroughs, Knuth sugerió uma extensão à tabela de símbolos permitindo que um símbolo representara uma cadeia de símbolos, que se tornó a base de DEFINE em Burroughs ALGOL. Edsger Dijkstra inicialmente não gostó da ideia. Knuth também trabalhou em linguagens de simulação, produciendo SOL com J. McNeeley, e influenció a Burroughs para adotar Simula depois de asistir a uma conferencia em 1967 na Noruega. Sua relação de consultoría com Burroughs duró de 1960 a 1968.
Em 1962, Addison-Wesley encargó a Knuth escrever um livro sobre compiladores. Mientras trabalhava nele, ele se deu conta de que precisava de uma teoría fundamental da programação de computadores, que se tornó The Art of Computer Programming. Originalmente planeado como um volume, se expandió a seis ou sete; o primeiro volume foi publicado em 1968. Justo antes da publicação, Knuth deixó Caltech para trabalhar no Institute for Defense Analyses' Communications Research Division em Princeton, realizando pesquisa matemática em criptografía para a National Security Agency.
Contribuciones à Ciência da Computação
O trabalho de Knuth em The Art of Computer Programming estabeleció a análise de algoritmos como uma disciplina rigorosa. Ele introdució e popularizó a notación asintótica (como a notación Big O) para descrever a eficiencia de algoritmos. Seus livros são conhecidos por sua precisión, notas históricas e exercícios graduados por dificultad. A série é considerada uma referencia fundamental na ciência da computación.
Knuth também desenvolveu o sistema de tipografía TeX (lançado em 1978) e METAFONT, permitindo tipografía matemática de alta qualidade. TeX se tornó um padrão na publicação académica. Ele crió os sistemas WEB e CWEB para programación literaria, que combinam código e documentación em uma única fonte. Seus linguajes de montaje MIX e MMIX são usados em seus livros para ilustrar conceitos de programación de baixo nível.
Carreira Posterior e Reconocimiento
Knuth se unió à Universidade de Stanford em 1969, onde se tornó professor e depois professor emérito. Ele recebiu o Prêmio Turing em 1974 por suas contribuciones principais à análise de algoritmos e ao diseño de linguajes de programación. Ele também recebiu a National Medal of Science (1979), a John von Neumann Medal (1995) e o Kyoto Prize (1996). Knuth é conhecido por sua atenção ao detalhe, incluindo oferecer recompensas monetárias por erros encontrados em seus livros.
Knuth tem sido um oponente declarado das patentes de software, apresentando amicus briefs e testificando ante oficinas de patentes. Ele se retiró da pesquisa activa nos anos 1990 para focar-se em completar The Art of Computer Programming, com os volumes 4A e 4B publicados em 2011 e 2022. Seu trabalho influenció generaciones de cientistas da computación, incluindo muitos em MIT e Universidade Carnegie Mellon.
Legado
O impacto de Knuth se extiende através de algoritmos, tipografía e metodología de programación. Seus libros de texto têm sido traduzidos a muitas linguas e permanecen amplamente usados. O sistema TeX e seus derivados (como LaTeX) são ferramentas essenciales na publicación científica. Seu concepto de programación literaria influenció práticas modernas de documentación. A insistencia de Knuth na rigor matemático na análise de algoritmos estabeleció um padrão para o campo, e suas contribuciones à inteligencia artificial e áreas relacionadas são reconhecidas através de numerosos grados honorarios e prêmios.
A pesar de seu foco na ciência da computación clásica, o trabalho de Knuth sustenta muitos desenvolvimentos modernos, incluindo aprendizaje automático e redes neuronales, fornecendo técnicas algorítmicas fundamentais. Seu legado é celebrado no Prêmio Knuth anual, outorgado por contribuciones destacadas aos fundamentos da ciência da computación.