Dossiê · Pioneiros da computação
Donald Knuth: o pai da análise de algoritmos e criador do TeX
Em 1962, uma editora pediu a Donald Knuth um livro sobre compiladores. Mais de seis décadas depois, a obra que nasceu desse pedido, The Art of Computer Programming, ainda está sendo escrita. No caminho, Knuth ajudou a fundar a análise de algoritmos e, insatisfeito com a qualidade da impressão dos próprios livros, criou o próprio sistema de tipografia, o TeX.
Atualizado em · 1 fontes públicas citadas
Donald Ervin Knuth, nascido em Milwaukee em 10 de janeiro de 1938, é um cientista da computação e matemático americano chamado de “pai da análise de algoritmos” [1]. É autor de The Art of Computer Programming e criador do sistema de tipografia TeX [1].
Knuth recebeu o Prêmio Turing de 1974 e é professor emérito da Universidade Stanford [1]. Este dossiê reúne apenas informações públicas e com fonte, listadas ao final.
4.500 palavras e um IBM 650
Na escola luterana de Milwaukee, Knuth venceu um concurso da oitava série ao encontrar mais de 4.500 palavras com as letras de “Ziegler's Giant Bar”; os jurados tinham chegado a 2.500 [1].
Em 1956, entrou no Case Institute of Technology, em Cleveland, com bolsa para estudar física [1]. Lá conheceu o computador IBM 650 e decidiu reescrever o código de assembly e do compilador da máquina da escola [1].
Em 1958, criou um programa para ajudar o time de basquete da escola, atribuindo valores às chances de cada jogador marcar; a Newsweek e a CBS noticiaram o caso [1].
Da física à matemática
Knuth trocou a física pela matemática e, em 1960, recebeu do Case o bacharelado e, por decisão especial do corpo docente, também o mestrado [1].
Em 1963, concluiu o doutorado em matemática no Caltech com a tese “Finite Semifields and Projective Planes”, orientada por Marshall Hall, e entrou no corpo docente da instituição como professor assistente [1].
Donald Knuth: marcos da carreira
Ano de cada marco, segundo a Wikipédia.
Fonte: Wikipédia.
Compiladores e Burroughs
Em 1960, Knuth propôs à Burroughs escrever um compilador ALGOL para o computador B205 por US$ 5.500, e a proposta foi aceita [1]. Foi consultor da empresa de 1960 a 1968 [1].
No verão de 1962, escreveu um compilador FORTRAN para a Univac, trabalho que descreveu como ter “vendido a alma ao diabo”, em tradução livre [1]. Ele recusou um contrato de US$ 100 mil para compiladores e bolsas que proibiam consultorias externas [1].
The Art of Computer Programming
Em 1962, a editora Addison-Wesley encomendou a Knuth um livro sobre compiladores. Ao perceber que precisava antes de uma teoria fundamental, ele começou The Art of Computer Programming, e o plano cresceu de um livro para seis volumes e depois sete [1].
O primeiro volume saiu em 1968 [1]. O terceiro foi escrito durante um ano na Universidade de Oslo e saiu logo depois da volta de Knuth a Stanford, em 1973 [1]. O volume 4A foi publicado até 2011 e o 4B em outubro de 2022 [1].
Em abril de 2020, Knuth disse que o volume 4 teria pelo menos as partes A a F [1]. Em 1990, ele recebeu o título de “Professor of The Art of Computer Programming” em Stanford [1].
O pai da análise de algoritmos
Knuth ajudou a desenvolver a análise rigorosa da complexidade computacional dos algoritmos, sistematizou técnicas formais e popularizou a notação assintótica [1]. Numa conferência da SIAM em 1967, decidiu responder “análise de algoritmos” quando lhe perguntassem o que fazia [1].
Entre os trabalhos que levam seu nome estão o algoritmo de Knuth–Morris–Pratt, o algoritmo de completamento de Knuth–Bendix e a notação de setas de Knuth [1].
TeX e METAFONT
Nos anos 1970, os editores de The Art of Computer Programming trocaram a composição em Monotype pela fototipia, e a qualidade ficou abaixo dos volumes anteriores [1]. Knuth parou para trabalhar com tipografia digital e criou o TeX, a linguagem de fontes METAFONT e a família de fontes Computer Modern [1].
Os livros “TeX: The Program” e “METAFONT: The Program” saíram em 1986 [1]. O LaTeX, pacote de macros baseado no TeX, foi criado por Leslie Lamport, que publicou o primeiro manual em 1986 [1].
Programação literária
Ao desenvolver o TeX, Knuth criou a programação literária, a ideia de tratar programas como literatura [1].
O sistema WEB gera, a partir de uma mesma fonte, um arquivo TeX com a documentação e um arquivo Pascal com o código; o CWEB depois trocou o Pascal por C, C++ e Java [1]. Knuth escreveu o TeX e o METAFONT em WEB e publicou os dois programas como livros [1].
Os cheques de US$ 2,56
Knuth paga US$ 2,56 por erro encontrado em seus livros, porque “256 centavos é um dólar hexadecimal”, e US$ 0,32 por sugestões valiosas [1]. A Technology Review chamou os cheques de um dos troféus mais cobiçados da computação [1].
Em 2008, por causa de fraudes bancárias, ele parou de enviar cheques reais e passou a dar um “certificado de depósito” do fictício Bank of San Serriffe [1].
Stanford
Knuth deixou um cargo no Institute for Defense Analyses, em Princeton, e entrou em Stanford em 1969 [1]. Tornou-se Fletcher Jones Professor of Computer Science em 1977 e é professor emérito desde 1993; segundo o artigo, deixou a pesquisa e o ensino regulares em 1992 para terminar The Art of Computer Programming [1].
O curso Concrete Mathematics, criado em Stanford em 1970, virou livro em 1988, com Ronald Graham e Oren Patashnik [1]. Algumas vezes por ano, ele dá palestras informais em Stanford que chama de “Computer Musings” [1].
Prêmios
Em 1971, Knuth recebeu o primeiro ACM Grace Murray Hopper Award, e em 1974 o Prêmio Turing [1]. Ganhou a Medalha Nacional de Ciência dos EUA em 1979, a Medalha John von Neumann e o Prêmio Harvey em 1995 e o Prêmio Kyoto em 1996 [1].
Foi eleito para a National Academy of Sciences em 1975 e para a National Academy of Engineering em 1981, e tornou-se membro estrangeiro da Royal Society em 2003 [1]. Em 2001, o asteroide 21656 Knuth recebeu seu nome [1].
Órgão, fé e números surreais
Knuth é organista e compositor. A peça para órgão Fantasia Apocalyptica, de 2016, estreou na Suécia em 10 de janeiro de 2018 [1].
Luterano, escreveu “3:16 Bible Texts Illuminated” e “Things a Computer Scientist Rarely Talks About” [1]. Também escreveu “Surreal Numbers”, uma novela matemática sobre o sistema de números criado por John Horton Conway [1].
Ele se opõe a patentes de software para soluções triviais e óbvias, e já escreveu para os escritórios de patentes dos EUA e da Europa sobre o tema [1].
Frases e declarações públicas
“Cuidado com bugs no código acima; eu só provei que está correto, não testei.”
“A melhor maneira de um ser humano se comunicar com outro é por meio de histórias.”
Linha do tempo
-
1938
Nasce em Milwaukee
-
1956
Entra no Case Institute of Technology
-
1960
Bacharelado e mestrado; compilador ALGOL para a Burroughs
-
1962
Começa The Art of Computer Programming
-
1963
Doutorado em matemática no Caltech
-
1968
Publica o volume 1 de TAOCP
-
1969
Entra em Stanford
-
1974
Recebe o Prêmio Turing
-
1979
Medalha Nacional de Ciência
-
1986
Publica TeX: The Program e METAFONT: The Program
-
1993
Torna-se professor emérito
-
1996
Prêmio Kyoto
-
2008
Troca os cheques reais pelo Bank of San Serriffe
-
2022
Publica o volume 4B de TAOCP
Empresas ligadas a Donald Knuth
Empresas desta coleção em que a pessoa trabalhou, fundou, investiu ou com que teve relação direta. Os nomes com link já têm dossiê publicado.
Ver a rede de Donald Knuth no grafo 3D
- IBM Fabricante do IBM 650, o primeiro computador que Knuth programou
Veja também: outras pessoas
- Grace Hopper Dá nome ao prêmio da ACM que Knuth recebeu primeiro, em 1971
- John von Neumann Dá nome à medalha que Knuth recebeu em 1995
Sumário de siglas usadas
- TAOCP
- The Art of Computer Programming, a obra em vários volumes de Knuth.
- TeX
- Sistema de tipografia digital criado por Knuth.
- METAFONT
- Linguagem e sistema de Knuth para definir e desenhar fontes.
- Notação assintótica
- Forma de descrever como o custo de um algoritmo cresce com o tamanho da entrada, como O(n).
- WEB
- Sistema de programação literária criado por Knuth.
Perguntas frequentes
Quem é Donald Knuth?+
Por que Knuth criou o TeX?+
Quanto vale um cheque de Knuth?+
The Art of Computer Programming está completo?+
Referências
Livros
The Art of Computer Programming
Obra de Knuth iniciada em 1962, com o primeiro volume em 1968 e o 4B em 2022.
Concrete Mathematics (1988)
Livro com Ronald Graham e Oren Patashnik, nascido de um curso em Stanford.
Surreal Numbers
Novela matemática sobre os números de John Horton Conway.
Fontes consultadas
- Donald Knuth · Wikipédia
Este dossiê usa apenas informações públicas e com fonte. Não publicamos dados pessoais privados, como endereço, documentos ou informações de saúde. Encontrou um erro? Escreva para [email protected].
Conclusão
Donald Knuth transformou um pedido de livro sobre compiladores num projeto de vida, The Art of Computer Programming, e no caminho deu bases rigorosas à análise de algoritmos. Quando a impressão dos próprios livros o decepcionou, criou o TeX e o METAFONT. Professor emérito de Stanford, ele segue escrevendo a obra e pagando, em certificados, por cada erro encontrado.