Donald Knuth

Donald Ervin Knuth
Donald Knuth em uma recepção para o Aliança de Conteúdo Aberto, 25 de outubro de 2005
Nascido	(1938/01/10) 10 de janeiro de 1938 De Milwaukee, Wisconsin, EUA
Residência	EU
Nacionalidade	Americana
Campos	Matemática Ciência da Computação
Instituições	Universidade de Stanford
Alma mater	Caso Institute of Technology California Institute of Technology
Conselheiro doutoral	Marshall Hall, Jr.
Os estudantes de doutorado	Leonidas J. Guibas Michael Fredman Scott Kim Vaughan Pratt Robert Sedgewick Jeffrey Vitter Andrei Broder
Conhecido por	The Art of Computer Programming TeX , METAFONT Algoritmo Knuth-Morris-Pratt Algoritmo Knuth-Bendix conclusão MMIX
Prêmios Notáveis	Turing Award (1974) John von Neumann Medal (1995) Prêmio Harvey (1995) Prêmio Kyoto (1996)
Site
Donald E. Knuth

Donald Ervin Knuth (pron .: / k ə n u θ / NOOTH kə-; nascido 10 de janeiro de 1938) é um cientista da computação e Professor Emérito Universidade de Stanford.

Ele é o autor da obra multi-volume seminal The Art of Computer Programming. Knuth tem sido chamado de "pai" da análise de algoritmos. Ele contribuiu para o desenvolvimento da análise rigorosa da complexidade computacional de algoritmos e técnicas matemáticas formais sistematizadas para ele. No processo, ele também popularizou o notação assintótica.

Além das contribuições fundamentais em vários ramos da ciência da computação teórica, Knuth é o criador do TeX sistema de composição no computador, o relacionado METAFONT linguagem de definição de fonte e sistema de renderização, eo Computer Modern família de tipos de letra.

Como escritor e estudioso, Knuth criou o REDE / Sistemas de programação de computador CWEB projetado para incentivar e facilitar programação letrada, e projetou o MIX / MMIX arquiteturas de conjunto de instruções.

Infância

Knuth nasceu em Milwaukee, Wisconsin, onde seu pai era dono de um negócio de impressão pequenos e ensinou na contabilidade Milwaukee Lutheran High School, onde ele se matriculou, ganhando prémios de mérito. Ele aplicou sua inteligência em formas não convencionais, de vencer um concurso quando estava na oitava série, encontrando mais de 4.500 palavras que poderiam ser formados a partir das letras em "Gigante Bar de Ziegler"; os juízes tiveram apenas cerca de 2.500 palavras na sua lista de mestre. Isso lhe rendeu um aparelho de televisão para a sua escola e uma barra de chocolate para todos em sua classe.

Educação

Knuth tinha um momento difícil escolher física sobre a música como seu principal em Caso Institute of Technology (agora parte da Case Western Reserve University). Ele também se juntou Beta Nu capítulo da Theta Chi fraternidade. Enquanto estudava física no Instituto de Tecnologia de Processo, Knuth foi apresentado ao IBM 650, um dos primeiros mainframes. Depois de ler o manual do computador, Knuth decidiu reescrever a montagem e código do compilador para a máquina usada em sua escola, porque ele acreditava que poderia fazê-lo melhor. Em 1958, Knuth construiu um programa com base no valor de cada jogador que poderia ajudar a sua equipe de basquete da escola ganhar o campeonato. Este era tão novo uma proposta no momento em que ele foi pego e publicado pela Newsweek e também coberto por Walter Cronkite na CBS Evening News. Knuth foi um dos editores fundadores da Engenharia e Ciência Review, que ganhou um prêmio nacional como melhor revista técnica em 1959. Ele depois passou da física à matemática, e em 1960 ele recebeu seu título de bacharel, recebendo simultaneamente seu mestre de grau de ciência por um prêmio especial da faculdade que considerou seu excelente trabalho.

Em 1963, ele obteve um Ph.D. em matemática (conselheiro: Marshall Hall) do California Institute of Technology, e começou a trabalhar lá como professor associado e começou a trabalhar em The Art of Computer Programming. Ele havia inicialmente aceite uma comissão para escrever um livro sobre compiladores, que mais tarde se tornaria o multi-volume The Art of Computer Programming. Este trabalho foi originalmente planejado para ser um único livro, e, em seguida, em seguida, planejado como um série de sete volumes e seis. Em 1968, pouco antes de ele publicou o primeiro volume, Knuth aceitou um emprego trabalhando em problemas para a Agência de Segurança Nacional ( NSA) através da sua FFRDC do Instituto de Análises de Defesa ( IDA) Divisão de Pesquisa Communications situado no momento no campus da Princeton no edifício Von Neumann como afirmou em sua vitae cumulae. Parece provável Knuth deixou o cargo e se juntou a faculdade de Stanford University por causa de suas crenças políticas eo clima político volátil no campus no momento.

Escritos

The Art of Computer Programming (TAOCP)

Ciência da computação foi, então, a dar os primeiros passos hesitantes. "Foi um campo totalmente novo," Knuth recorda, "sem identidade real. E o padrão de publicações disponíveis não era tão alto. Um monte de papéis que saem foram pura e simplesmente errado. (...) Assim, uma das minhas motivações era para colocar em linha reta uma história que tinha sido muito mal contada ".

Depois de produzir o terceiro volume de sua série em 1976, ele expressou tal frustração com o estado nascente das ferramentas de edição electrónica então recém-desenvolvidos (especialmente aqueles que contribuiu para fotocompositoras) que ele tirou um tempo para trabalhar em diagramação e criou o TeX e Ferramentas MetaFont.

A partir de 2012, os três primeiros volumes e uma parte do volume de quatro de suas séries foram publicados.

Outros trabalhos

Ele também é o autor de Números Surreal, uma novela sobre matemática De John Conway teoria dos conjuntos de construção de um sistema alternativo de números. Em vez de simplesmente explicar o assunto, o livro procura mostrar o desenvolvimento da matemática. Knuth queria o livro para preparar os estudantes para fazer a pesquisa original, criativo.

Em 1995 , Knuth escreveu o prefácio para o livro A = B por Marko Petkovsek, Herbert Wilf e Doron Zeilberger.

As crenças religiosas e trabalho

Além de seus escritos sobre a ciência da computação, Knuth, um luterano, é também o autor de 03:16 Bíblia Textos Iluminado, em que 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 versículo é acompanhado por uma prestação em arte caligráfica, contribuiu por um grupo de calígrafos sob a liderança do Hermann Zapf.

Preocupações com a saúde

Em 2006, Knuth foi diagnosticado com cancro da próstata. Ele passou por uma cirurgia em dezembro daquele ano e começou a "um pouco de terapia de radiação ... como medida de precaução, mas o prognóstico parece muito bom", como relatou em sua autobiografia vídeo.

Reflexões de computador

Knuth dá palestras informais algumas vezes por ano em Universidade de Stanford, que ele chamou de Computador reflexões. Ele também foi professor visitante na Laboratório de Computação da Universidade de Oxford, no Reino Unido e um membro honorário de Faculdade Magdalen.

Humor

Knuth é conhecido por seu "humor profissional".

Um de Cheques de recompensa de Knuth

"Nested parens "- Donald Knuth e Jacob Appelbaum

• Ele usado para pagar taxa de corretagem de 2,56 dólares por quaisquer erros tipográficos ou erros descobertos em seus livros, porque "256 moedas de um centavo é um hexadecimal dólar ", e $ 0,32 para" sugestões valiosas ". De acordo com um artigo no Instituto de Tecnologia de Avaliação de Tecnologia de Massachusetts, estes Cheques de recompensa Knuth estão "entre os troféus mais valiosos do computerdom". Knuth tinha que parar de enviar cheques reais em 2008 devido a fraudes bancárias, e em vez disso agora dá a cada um localizador de erro "certificado de depósito" de um saldo de capital aberto em sua fictícia "Bank of São Serriffe ".
• Certa vez, ele advertiu o correspondente, "Cuidado com os erros no código acima, eu só provaram correto, não tentou fazê-lo."
• O prefácio de Betão Matemática inclui a seguinte anedota: "Quando Knuth ensinou Matemática concretas 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 foi duro em vez de suave. Ele anunciou que, ao contrário das expectativas de alguns de seus colegas, ele não estava indo para ensinar a Teoria da Agregados, nem de Stone Embedding Teorema, nem mesmo o Pedra-Čech compactification teorema. (Vários alunos da engenharia civil departamento levantou-se e saiu da sala em silêncio.) "

• Knuth publicou seu primeiro artigo "científico" em uma revista da escola em 1957 sob o título " Potrzebie Sistema de Pesos e Medidas ". Nela, ele definiu o unidade fundamental da comprimento que a espessura de Mad # 26, e nomeou a unidade fundamental da força "whatmeworry." Mad publicou o artigo na edição # 33 (Junho de 1957).
• O artigo de Knuth sobre a complexidade computacional de canções, " A complexidade dos Cânticos ", foi reeditado duas vezes em revistas de ciência da computação.
• Para demonstrar o conceito, Knuth intencionalmente referido "definição circular" e "Definição, circular" entre si no índice de The Art of Computer Programming, Volume 1.
• No TUG Conference 2010, Knuth anunciou um XML-baseado sucessor para TeX, intitulado "Itex" (pronuncia- [Iː˨˩˦tɛks˧˥], com um toque de sino), que oferecem suporte a recursos tais como unidades irracionais arbitrariamente dimensionadas, Impressão em 3D, animação e som estereofônico.

Prêmios

Em 1971, Knuth foi o ganhador do primeiro ACM Graça Murray Hopper Award. Ele recebeu vários outros prêmios, incluindo o Turing Award, o Medalha Nacional de Ciência, a John von Neumann Medalha, ea Prêmio Kyoto.

Em reconhecimento das contribuições de Knuth para o campo da ciência da computação, em 1990 ele foi premiado com o título de formação one-of-a-kind of Professor de The Art of Computer Programming, que já foi revisto para Professor Emérito do The Art of Computer Programming.

Em 1992, ele tornou-se um associado da Academia Francesa de Ciências. Também nesse ano, ele se aposentou da pesquisa regular e ensino em Universidade de Stanford, a fim de terminar The Art of Computer Programming. Em 2003, foi eleito membro estrangeiro da Royal Society.

Knuth foi eleito Fellow (primeira turma de bolsistas) do Society for Industrial and Applied Mathematics, em 2009, por suas excelentes contribuições para a matemática . Ele é um membro da Academia Norueguesa de Ciências e Letras. Em 2012 ele se tornou um membro da American Mathematical Society.

Honras concedidas ao Knuth incluem:

• Primeiro ACM Graça Murray Hopper Award de 1971
• Turing Award de 1974
• Medalha Nacional de Ciência, 1979
• Medalha Franklin de 1988
• John von Neumann Medalha de 1995
• Harvey do Prémio Technion de 1995
• Prêmio Kyoto de 1996
• Fellow da Computer History Museum, 1998
• Prêmio Katayanagi de 2010
• Fundação BBVA Fronteiras do Conhecimento Award 2010
• Escola da Universidade de Stanford de Prêmio Herói Engenharia de 2011

Trabalho

Uma pequena lista de suas obras:

• Donald E. Knuth, The Art of Computer Programming, Volumes 1-4, Addison-Wesley Professional

1. Volume 1: Algoritmos Fundamentais (3ª edição), 1997 Addison-Wesley Professional, ISBN 0-201-89683-4
2. Volume 2: Seminumerical Algoritmos (3rd Edition), 1997. Addison-Wesley Professional, ISBN 0-201-89684-2
3. Volume 3: classificação e pesquisa (2nd Edition), de 1998. Addison-Wesley Professional, ISBN 0-201-89685-0
4. Volume 4A: Combinatória Algoritmos, Parte 1, 2011. Addison-Wesley Professional, ISBN 0-201-03804-8
5. Volume 4: Combinatória Algoritmos (restante), em preparação

• Donald E. Knuth, The Art of Computer Programming, fascículos:

1. Volume 1, Fascículo 1: MMIX-A RISC computador para o Novo Milênio de 2005. ISBN 0-201-85392-2
2. Volume 4, Fascicle 0: Introdução aos Algoritmos e Combinatória Funções booleanas. 2008. ISBN 0-321-53496-4
3. Volume 4, Fascicle 1: Truques bit a bit e técnicas; Diagramas de decisão binária. 2009. ISBN 0-321-58050-8
4. Volume 4, Fascicle 2: Gerando todas as tuplas e permutações de 2005. ISBN 0-201-85393-0
5. Volume 4, Fascicle 3: Gerando todas as combinações e partições de 2005. ISBN 0-201-85394-9
6. Volume 4, Fascicle 4: Geração de todas as árvores-História da Combinatória Geração de 2006. ISBN 0-321-33570-8

• Donald E. Knuth, Computadores & composição:

1. Volume Um, O Livro Didático (Reading, Massachusetts: Addison-Wesley, 1984), x + 483pp. ISBN 0-201-13447-0
2. Volume B, TeX: O Programa (Reading, Massachusetts: Addison-Wesley, 1986), xviii + 600pp. ISBN 0-201-13437-3
3. Volume C, A METAFONTbook (Reading, Massachusetts: Addison-Wesley, 1986), xii + 361pp. ISBN 0-201-13445-4
4. Volume D, METAFONT: O Programa (Reading, Massachusetts: Addison-Wesley, 1986), xviii + 566pp. ISBN 0-201-13438-1
5. Volume E, Computador Fontes modernos (Reading, Massachusetts: Addison-Wesley, 1986), xvi + 588pp.

• Knuth, Donald E. Séries selecionadas papéis

1. Donald E. Knuth, Programação Alfabetizado (Stanford, Califórnia: Centro de Estudos de Linguagem e Informação - CSLI Lecture Notes, não. 27), 1992. ISBN 0-937073-80-6
2. Donald E. Knuth, trabalhos selecionados em Ciência da Computação (Stanford, Califórnia: Centro de Estudos da Linguagem e da Informação - CSLI Lecture Notes, não 59.), De 1996. ISBN 1-881526-91-7
3. Donald E. Knuth, Tipografia Digital (Stanford, Califórnia: Centro de Estudos da Linguagem e da Informação - CSLI Lecture Notes, 78 sem.), De 1999. ISBN 1-57586-010-4
4. Donald E. Knuth, trabalhos selecionados em Análise de Algoritmos (Stanford, Califórnia: Centro de Estudos da Linguagem e da Informação - CSLI Lecture Notes, nº 102.), 2000. ISBN 1-57586-212-3
5. Donald E. Knuth, trabalhos selecionados no computador de Línguas (Stanford, Califórnia: Centro de Estudos de Línguas e Informações - CSLI Lecture Notes, 139 sem.), De 2003. ISBN 1-57586-381-2 (de pano), ISBN 1-57586-382-0 (paperback)
6. Donald E. Knuth, trabalhos selecionados em Matemática Discreta (Stanford, Califórnia: Centro de Estudos de Linguagem e Informação - CSLI notas de aula, nº 106.), 2003. ISBN 1-57586-249-2 (de pano), ISBN 1-57586-248-4 (paperback)
7. Donald E. Knuth, trabalhos selecionados no Projeto de Algoritmos (Stanford, Califórnia: Centro de Estudos da Linguagem e da Informação - Notas CSLI palestra, no 191.), De 2010. ISBN 1-57586-583-1 (de pano), ISBN 1-57586-582-3 (paperback)
8. Donald E. Knuth, artigos selecionados sobre Fun and Games (Stanford, Califórnia: Centro de Estudos da Linguagem e da Informação - CSLI Lecture Notes, não 192.), 2011. ISBN 978-1-57586-585-0 (pano), ISBN 978-1-57586-584-3 (paperback)
9. Donald E. Knuth, Companion para os Documentos de Donald Knuth (Stanford, Califórnia: Centro de Estudos de Línguas e Informações - CSLI Lecture Notes, no 202.), 2011. ISBN 978-1-57586-635-2 (pano), ISBN 978-1-57586-634-5 (paperback)

• Graham, Ronald G .; Knuth, Donald E .; Patashnik, Oren (1994). Matemática concreta: Uma fundação para a ciência da computação (Segunda ed.). Leitura, MA: Addison-Wesley Publishing Company. pp. xiv + 657. ISBN 0-201-55802-5. MR 1.397.498.  
• Donald E. Knuth, números surreais: Como Dois Ex-Alunos ligado para Matemática Pura e felicidade total encontrado. 1974, ISBN 0-201-03812-9. Mais informações podem ser encontradas em site oficial do livro
• Donald E. Knuth, The Stanford GraphBase: Uma Plataforma para Combinatória Computing (New York, ACM Press) 1993. segunda paperback impressão de 2009. ISBN 0-321-60632-9
• Donald E. Knuth, 03:16 Bíblia Textos Iluminado (Madison, Wisconsin: Edições AR), de 1990. ISBN 0-89579-252-4
• Donald E. Knuth, Coisas um cientista da computação Raramente fala sobre (Centro de Estudos de Linguagem e Informação - CSLI Lecture Notes no 136), de 2001. ISBN 1-57586-326-X