Donald Knuth - Donald Knuth

Donald Knuth
KnuthAtOpenContentAlliance.jpg
Knuth em 2005
Nascer
Donald Ervin Knuth

( 1938-01-10 )10 de janeiro de 1938 (idade 83)
Nacionalidade americano
Educação
Conhecido por
Cônjuge (s) Nancy Jill Carter
Crianças 2
Prêmios
Carreira científica
Campos
Instituições Stanford University ,
University of Oslo
Tese Finite Semifields and Projective Planes  (1963)
Orientador de doutorado Marshall Hall, Jr.
Alunos de doutorado
Local na rede Internet cs .stanford .edu / ~ knuth

Donald Ervin Knuth ( / k ə n u θ / kə- NOOTH , nascido 10 de janeiro de 1938) é um americano computador cientista , matemático e professor emérito na Universidade de Stanford . Ele recebeu o prêmio ACM Turing em 1974 , considerado informalmente o Prêmio Nobel de ciência da computação. Knuth foi chamado de "pai da análise de algoritmos ".

Ele é o autor da obra em vários volumes The Art of Computer Programming . Ele contribuiu para o desenvolvimento da análise rigorosa da complexidade computacional de algoritmos e técnicas matemáticas formais sistematizadas para isso. No processo, ele 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 de composição de computador TeX , a linguagem de definição de fonte METAFONT relacionada e sistema de renderização, e a família de fontes Computer Modern .

Como escritor e estudioso, Knuth criou os sistemas de programação de computador WEB e CWEB projetados para encorajar e facilitar a programação letrada e projetou as arquiteturas de conjunto de instruções MIX / MMIX . Knuth se opõe veementemente à concessão de patentes de software , tendo expressado sua opinião junto ao Escritório de Marcas e Patentes dos Estados Unidos e à Organização Europeia de Patentes .

Biografia

Vida pregressa

Knuth nasceu em Milwaukee , Wisconsin , filho de Ervin Henry Knuth e Louise Marie Bohning. Ele descreve sua herança como "alemão luterano do meio-oeste". Seu pai era dono de uma pequena gráfica e ensinava contabilidade. Donald, um estudante da Milwaukee Lutheran High School , pensou 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 "Barra Gigante de Ziegler" poderiam ser reorganizadas para criar; os juízes identificaram 2.500 dessas palavras. Com o tempo perdido longe da escola devido a uma fingida dor de estômago, e resolvendo o problema de outra maneira, Knuth usou um dicionário completo e determinou se cada entrada do dicionário poderia ser formada usando as letras da frase. Usando esse 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 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 ingressou no capítulo Beta Nu da fraternidade Theta Chi . Enquanto estudava física na Case, Knuth conheceu o IBM 650 , um dos primeiros computadores comerciais . Depois de ler o manual do computador, Knuth decidiu reescrever o código de montagem e compilador da máquina usada em sua escola, porque acreditava que poderia 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 a fim de avaliar sua probabilidade de ganhar pontos, uma abordagem inovadora que a Newsweek e o CBS Evening News relataram mais tarde.

Knuth foi um dos editores fundadores da Engineering and Science Review do Case Institute , que ganhou um prêmio nacional de melhor revista técnica em 1959. Ele então mudou da física para a matemática e recebeu dois diplomas da Case em 1960: seu diploma de bacharel em ciências, e simultaneamente um mestre em ciências por um prêmio especial do corpo docente, que considerou seu trabalho excepcionalmente notável.

Em 1963, com o matemático Marshall Hall como seu conselheiro, ele obteve o título de PhD em matemática pelo California Institute of Technology .

Trabalho cedo

Após receber seu PhD, Knuth ingressou no corpo docente da Caltech como professor assistente.

Ele aceitou a comissão para escrever um livro sobre compiladores de linguagens de programação de computador . Enquanto trabalhava neste projeto, Knuth decidiu que não poderia tratar adequadamente o tópico sem primeiro desenvolver uma teoria fundamental da programação de computadores, que se tornou A Arte da Programação de Computadores . Ele planejou publicá-lo originalmente como um único livro. Enquanto Knuth desenvolvia 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 a Caltech para aceitar um emprego na Divisão de Pesquisa de Comunicações do Institute for Defense Analyzes , então situada no campus da Universidade de Princeton , que estava realizando pesquisas matemáticas em criptografia para apoiar a Segurança Nacional Agência .

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 seu cargo para ingressar no corpo docente da Universidade de Stanford em 1969, onde agora é Fletcher Jones Professor de Ciência da Computação, Emérito.

Escritos

Knuth é escritor e também cientista da computação.

A Arte da Programação de Computadores ( TAOCP )

"A melhor maneira de se comunicar de um ser humano para outro é através da história."

-  Donald Knuth

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 de publicações disponíveis não era tão alto. Muitos dos artigos publicados estavam simplesmente errados. ... Então, uma das minhas motivações era endireitar uma história que havia sido muito mal contada. "

De 1972 a 1973, Knuth passou um ano na Universidade de Oslo entre pessoas como Ole-Johan Dahl . Aqui estava ele para realmente escrever o sétimo volume de sua série de livros, um volume que trataria de linguagens de programação. No entanto, Knuth só havia terminado os dois primeiros volumes quando veio para Oslo, e assim passou o ano no terceiro volume, próximo ao ensino. O terceiro volume da série foi lançado logo após Knuth retornar a Stanford em 1973.

Em 2011, os três primeiros volumes e a primeira parte do volume quatro de sua série foram publicados. Concrete Mathematics: A Foundation for Computer Science 2 ed., Que se originou com uma expansão da seção de preliminares matemáticas do Volume 1 do TAoCP , também foi publicada. Em abril de 2020, Knuth disse que está trabalhando arduamente na parte B do volume 4 e prevê que o livro terá pelo menos as partes de A a F.

Outros trabalhos

Knuth é também o autor de números surreais , uma novela matemática sobre John Conway 's teoria dos conjuntos de 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 uma 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 contribui ocasionalmente com quebra-cabeças de linguagem para Word Ways: The Journal of Recreational Linguistics .

Knuth também se dedicou à matemática recreativa . Ele contribuiu com artigos para o Journal of Mathematics recreativas começando na década de 1960, e foi reconhecido como um dos principais contribuintes em Joseph Madachy de Matemática em férias .

Knuth também apareceu em uma série de vídeos do Numberphile e Computerphile no YouTube, onde discutiu tópicos, desde escrever Surreal Numbers até por que ele não usa e-mail.

Trabalhos sobre suas crenças religiosas

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 por um processo de amostragem sistemática , ou seja, uma análise do capítulo 3, versículo 16 de cada livro. Cada verso é acompanhado por uma representaçã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 uma série de palestras no MIT sobre suas visões sobre 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 publicou as palestras "God and Computer Ciência " .

Opinião sobre patentes de software

Knuth se opõe fortemente à política de concessão de patentes de software para soluções triviais que deveriam ser óbvias, mas expressou pontos de vista mais diferenciados para soluções não triviais, como o método de ponto interior da programação linear . Ele expressou seu desacordo diretamente para tanto o United States Patent and Trademark Office e Organização Europeia de Patentes .

Reflexões sobre computador

Knuth dá palestras informais algumas vezes por ano na Universidade de Stanford , que intitula "Reflexões sobre o computador". Ele foi um professor visitante no Departamento de Ciência da Computação da Universidade de Oxford no Reino Unido até 2017 e um Honorary Fellow do Magdalen College .

Programação

Composição digital

Na década de 1970, os editores do TAOCP abandonaram a Monotype em favor da fotocomposição . Knuth ficou tão frustrado com a incapacidade do último sistema de se aproximar da qualidade dos volumes anteriores, que eram compostos usando o sistema mais antigo, que tirou um tempo para trabalhar na composição digital e criou TeX e Metafont .

Programação letrada

Enquanto desenvolvia o TeX, Knuth criou uma nova metodologia de programação, que chamou de programação literária , porque acreditava que os programadores deveriam pensar em programas como obras de literatura. "Em vez de imaginar que nossa principal tarefa é instruir um computador sobre 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 letrada no sistema WEB . O mesmo código-fonte da WEB é usado para tecer um arquivo TeX e para confundir 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 com C .

Knuth usou a WEB para programar TeX e METAFONT, e publicou ambos os programas como livros: The TeXbook , que foi publicado originalmente em 1984, e The METAFONTbook , que foi publicado originalmente em 1986. Mais ou menos na mesma época, LaTeX , a macro agora amplamente adotada pacote baseado em TeX, foi desenvolvido pela primeira vez por Leslie Lamport , que mais tarde 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 da Revelação de São João o Divino em música". Foi estreado na Suécia em 10 de janeiro de 2018.

Vida pessoal

Donald Knuth casou-se com Nancy Jill Carter em 24 de junho de 1961, enquanto ele era um estudante de graduação no Instituto de Tecnologia da Califórnia. Eles têm dois filhos: John Martin Knuth e Jennifer Sierra Knuth.

nome chinês

O nome chinês de Knuth é Gao Dena ( chinês simplificado :高 德纳; chinês tradicional :高 德納; pinyin : Gāo Dénà ). Em 1977, ele recebeu esse nome de Frances Yao , pouco antes de fazer uma viagem de três semanas à China . Na tradução chinesa de 1980 do Volume 1 de The Art of Computer Programming ( chinês simplificado :计算机 程序 设计 艺术; chinês tradicional :電腦 程式 設計 藝術; pinyin : Jìsuànjī chéngxù shèjì yìshù ), Knuth explica que abraçou seu nome chinês porque queria a ser conhecido pelo número crescente de programadores de computador na China na época. Em 1989, seu nome chinês foi colocado no topo do Jornal de Ciência da Computação e Tecnologia de cabeçalho, que Knuth diz 'me faz sentir perto de todo o povo chinês, embora eu não posso falar o idioma'.

Preocupações com a saúde

Em 2006, Knuth foi diagnosticado com câncer de próstata . Ele foi submetido a uma cirurgia em dezembro daquele ano e afirmou, "um pouco de radioterapia ... por precaução, mas o prognóstico parece muito bom", como relatou em sua autobiografia em vídeo.

Humor

Knuth costumava pagar uma taxa de descoberta de $ 2,56 por quaisquer erros tipográficos 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 Massachusetts Institute of Technology 's Technology Review , esses cheques de recompensa Knuth estão "entre os troféus mais valiosos do mundo da informática". Knuth teve que parar de enviar cheques reais em 2008 devido a fraude bancária e, em vez disso, agora dá a cada localizador de erros um "certificado de depósito" de um saldo listado publicamente em seu fictício "Banco de San Serriffe ".

Certa vez, ele avisou um correspondente: "Cuidado com os 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 "O Sistema Potrzebie de Pesos e Medidas". Nele, ele definiu a unidade fundamental de comprimento como a espessura do Mad No. 26 e chamou a unidade de força fundamental de "whatmeworry". Mad publicou o artigo no número 33 (junho de 1957).

Para demonstrar o conceito de recursão , Knuth intencionalmente referiu "Definição circular" e "Definição circular" uma à outra no índice de The Art of Computer Programming , Volume 1 .

O prefácio da matemática concreta tem o seguinte parágrafo:

Quando DEK ensinou matemática concreta 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 suave. Ele anunciou que, ao contrário das expectativas de seus colegas, não iria ensinar a Teoria dos Agregados, nem o Teorema de Incorporação de Stone , nem mesmo a compactação Stone-Čech . (Vários alunos do departamento de engenharia civil levantaram-se e deixaram a sala silenciosamente.)

Na Conferência TUG 2010, Knuth anunciou um sucessor satírico baseado em XML para TeX, intitulado "iTeX" ( pronunciado  [iː˨˩˦tɛks˧˥] , executado com um toque de sino), que suportaria recursos como unidades irracionais escalonadas arbitrariamente , Impressão 3D , entrada de sismógrafos e monitores cardíacos, animação e som estereofônico.

Premios e honras

Em 1971, Knuth recebeu o primeiro prêmio ACM Grace Murray Hopper . Ele recebeu vários outros prêmios, incluindo o Prêmio Turing , a Medalha Nacional de Ciência , a Medalha John von Neumann e o Prêmio Kyoto .

Knuth foi eleito Membro Distinto da British Computer Society (DFBCS) em 1980 em reconhecimento às contribuições de Knuth para o campo da ciência da computação.

Em 1990, ele recebeu o título acadêmico único de Professor de The Art of Computer Programming , que desde então foi revisado para Professor Emérito de The Art of Computer Programming .

Knuth foi eleito para a Academia Nacional de Ciências em 1975. Ele também foi eleito membro da Academia Nacional de Engenharia em 1981 por organizar vastas áreas de conhecimento da ciência da computação para que fossem acessíveis a todos os segmentos da comunidade da computação. Em 1992, tornou-se associado da Academia Francesa de Ciências . Também naquele ano, ele se aposentou da pesquisa regular e do ensino na Universidade de Stanford para terminar A Arte da Programação de Computadores . Ele foi eleito membro estrangeiro da Royal Society (ForMemRS) em 2003 .

Knuth foi eleito Fellow (primeira classe de Fellows) da Society for Industrial and Applied Mathematics em 2009 por suas excelentes contribuições para a matemática. Ele é membro da Academia Norueguesa de Ciências e Letras . Em 2012, tornou-se membro da American Mathematical Society e membro da American Philosophical Society . Outros prêmios e homenagens incluem:

Publicações

Uma pequena lista de suas publicações inclui:

A Arte da Programação de Computador :

  1. ——— (1997). The Art of Computer Programming . 1: Algoritmos Fundamentais (3ª ed.). Addison-Wesley Professional. ISBN 978-0-201-89683-1.
  2. ——— (1997). The Art of Computer Programming . 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley Professional. ISBN 978-0-201-89684-8.
  3. ——— (1998). The Art of Computer Programming . 3: Classificação e pesquisa (2ª ed.). Addison-Wesley Professional. ISBN 978-0-201-89685-5.
  4. ——— (2011). The Art of Computer Programming . 4A: Algoritmos Combinatórios. Addison-Wesley Professional. ISBN 978-0-201-03804-0.
  5. ——— (2005). MMIX — Um Computador RISC para o Novo Milênio . 1, fascículo 1. ISBN 978-0-201-85392-6.
  6. ——— (2008). The Art of Computer Programming . 4, Fascículo 0: Introdução a Algoritmos Combinatórios e Funções Booleanas. ISBN 978-0-321-53496-5.
  7. ——— (2009). The Art of Computer Programming . 4, Fascículo 1: Truques e técnicas bit a bit, diagramas de decisão binários. ISBN 978-0-321-58050-4.
  8. ——— (2005). The Art of Computer Programming . 4, Fascículo 2: Gerando todas as tuplas e permutações. ISBN 978-0-201-85393-3.
  9. ——— (2005). The Art of Computer Programming . 4, Fascículo 3: Gerando todas as combinações e partições. ISBN 978-0-201-85394-0.
  10. ——— (2006). The Art of Computer Programming . 4, Fascículo 4: Gerando Todas as Árvores - História da Geração Combinatória. ISBN 978-0-321-33570-8.
  11. ——— (2018). The Art of Computer Programming . 4, Fascículo 5: Preliminares matemáticos Redux, Backtracking, Dancing Links. ISBN 978-0-134-67179-6.
  12. ——— (2015). The Art of Computer Programming . 4, Fascículo 6: Satisfabilidade. ISBN 978-0-134-39760-3.

Computadores e fotocomposição (todos os livros são de capa dura, a menos que indicado de outra forma):

  1. ——— (1984). Computadores e fotocomposição . A, The TeXbook. Leitura, MA : Addison-Wesley. ISBN 978-0-201-13447-6., x + 483pp.
  2. ——— (1984). Computadores e fotocomposição . A, The TeXbook. Leitura, MA : Addison-Wesley. ISBN 978-0-201-13448-3. (capa mole).
  3. ——— (1986). Computadores e fotocomposição . B, TeX: o programa. Leitura, MA : Addison-Wesley. ISBN 978-0-201-13437-7., xviii + 600pp.
  4. ——— (1986). Computadores e fotocomposição . C, o livro METAFONT. Leitura, MA : Addison-Wesley. ISBN 978-0-201-13445-2., xii + 361pp.
  5. ——— (1986). Computadores e fotocomposição . C, o livro METAFONT. Leitura, MA : Addison-Wesley. ISBN 978-0-201-13444-5. (capa mole).
  6. ——— (1986). Computadores e fotocomposição . D, METAFONT: O Programa. Leitura, MA : Addison-Wesley. ISBN 978-0-201-13438-4., xviii + 566pp.
  7. ——— (1986). Computadores e fotocomposição . E, Tipos de letra modernos do computador. Leitura, MA : Addison-Wesley. ISBN 978-0-201-13446-9., xvi + 588pp.
  8. ——— (2000). Computadores e fotocomposição . Conjunto AE em caixa. Leitura, MA : Addison-Wesley. ISBN 978-0-201-73416-4.

Livros de papéis coletados:

  1. ——— (1992). Literate Programming . Notas da aula. Stanford, CA : Centro para o Estudo da Linguagem e da Informação - CSLI. ISBN 978-0-937073-80-3.
  2. ——— (1996). Artigos Selecionados em Ciência da Computação . Notas da aula. Stanford, CA : Centro para o Estudo da Linguagem e da Informação - CSLI. ISBN 978-1-881526-91-9.
  3. ——— (1999). Tipografia digital . Notas da aula. Stanford, CA : Centro para o Estudo da Linguagem e da Informação - CSLI. ISBN 978-1-57586-010-7.
  4. ——— (2000). Artigos Selecionados sobre Análise de Algoritmos . Notas da aula. Stanford, CA : Centro para o Estudo da Linguagem e da Informação - CSLI. ISBN 978-1-57586-212-5.
  5. ——— (2003). Artigos Selecionados em Linguagens de Computação . Notas da aula. Stanford, CA : Centro para o Estudo da Linguagem e da Informação - CSLI. ISBN 978-1-57586-381-8., ISBN  1-57586-382-0 (brochura)
  6. ——— (2003). Artigos Selecionados em Matemática Discreta . Notas da aula. Stanford, CA : Centro para o Estudo da Linguagem e da Informação - CSLI. ISBN 978-1-57586-249-1., ISBN  1-57586-248-4 (brochura)
  7. Donald E. Knuth, Selected Papers on Design of Algorithms (Stanford, Califórnia: Centro para o Estudo da Linguagem e da Informação - CSLI Lecture Notes, no. 191), 2010. ISBN  1-57586-583-1 (tecido), ISBN  1 -57586-582-3 (brochura)
  8. Donald E. Knuth, Selected Papers on Fun and Games (Stanford, Califórnia: Center for the Study of Language and Information - CSLI Lecture Notes, no. 192), 2011. ISBN  978-1-57586-585-0 (tecido), ISBN  978-1-57586-584-3 (brochura)
  9. Donald E. Knuth, Companion to the Papers of Donald Knuth (Stanford, Califórnia: Center for the Study of Language and Information - CSLI Lecture Notes, no. 202), 2011. ISBN  978-1-57586-635-2 (tecido) , ISBN  978-1-57586-634-5 (brochura)

Outros livros:

  1. Graham, Ronald L ; Knuth, Donald E .; Patashnik, Oren (1994). Matemática concreta: Uma base para a ciência da computação (segunda edição). Leitura, MA: Addison-Wesley. ISBN 978-0-201-55802-9. MR  1397498 . xiv + 657 pp.
  2. Knuth, Donald Ervin (1974). Números surreais: como dois ex-alunos se voltaram para a matemática pura e encontraram a felicidade total: uma novela matemática . Addison-Wesley. ISBN 978-0-201-03812-5.
  3. Donald E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing (New York, ACM Press) 1993. segunda impressão de brochura 2009. ISBN  0-321-60632-9
  4. Donald E. Knuth, 3:16 Bible Texts Illuminated (Madison, Wisconsin: AR Editions), 1990. ISBN  0-89579-252-4
  5. Donald E. Knuth, Things a Computer Scientist Rarely Talks About (Centro para o Estudo da Linguagem e da Informação - CSLI Lecture Notes no 136), 2001. ISBN  1-57586-326-X
  6. Donald E. Knuth, MMIXware: A RISC Computer for the Third Millennium (Heidelberg: Springer-Verlag— Lecture Notes in Computer Science, no. 1750), 1999. viii + 550pp. ISBN  978-3-540-66938-8
  7. Donald E. Knuth e Silvio Levy, O Sistema CWEB de Documentação Estruturada (Reading, Massachusetts: Addison-Wesley), 1993. iv + 227pp. ISBN  0-201-57569-8 . Terceira impressão 2001 com suporte a hipertexto, ii + 237 pp.
  8. Donald E. Knuth, Tracy L. Larrabee e Paul M. Roberts, Mathematical Writing (Washington, DC: Mathematical Association of America), 1989. ii + 115pp
  9. Daniel H. Greene e Donald E. Knuth, Matemática para a Análise de Algoritmos (Boston: Birkhäuser), 1990. viii + 132pp.
  10. Donald E. Knuth, Mariages Stables: et leurs Relations avec d'autres problems combinatoires (Montreal: Les Presses de l'Université de Montréal) , 1976. 106pp.
  11. Donald E. Knuth, Axioms and Hulls (Heidelberg: Springer-Verlag — Lecture Notes in Computer Science, no. 606), 1992. ix + 109pp. ISBN  3-540-55611-7

Veja também

Referências

Bibliografia

links externos