Ferramentas do usuário

Ferramentas do site


d:donald_knuth

Donald Knuth

Biografia

Nome completo:

Donald Ervin Knuth.

Data de nascimento:

10 de janeiro de 1938.

Local de nascimento:

Milwaukee, a cidade mais populosa do estado norte-americano Wisconsin.

Educação:

Em 1956, Knuth recebeu uma bolsa para estudar física em Case Institute of Technology (Ohio, Cleveland). Enquanto estudava em Ohio, Knuth entrou em contato com o computador comercial IBM 650. Depois de ler o manual do computador, ele decidiu reescrever o assembly e o compilador da máquina que ele usava em sua escola, pois acreditava que conseguia fazer algo melhor.

Durante a sua estadia em Case, Knuth migrou de física para matemática. Naturalmente, em 1960, ele recebeu seu diploma de bacharel em matemática. O que não foi natural é o fato de que seu desempenho durante a faculdade foi tão impressionante que o norte-americano ganhou dois diplomas ao mesmo tempo: além do de bacharel, o de mestre em matemática, ambos pela Case Institue of Technology.

Por fim, em 1963, com o matemático Marshall Hall como seu orientador, Knuth foi premiado com o título de doutor em matemática pela California Institute of Technology (Caltech), defendendo a tese entitulada Finite Semifields and Projective Planes.

Áreas de atuação:

Matemática e Ciência da computação.

Instituições de trabalho/atuação:

No começo de sua carreira, Knuth foi professor assistente na Caltech e, depois, professor associado, durante 5 anos (1963-1968), também na Caltech.

Por um curto período, o matemático trabalhou com o Institute for Defense Analyses Communications Research Division, situado no campus da universidade de Princenton. Nesse local, Knuth trabalhou com criptografia, a fim de ajudar a Agência de Segurança Nacional Norte-Americana (NSA).

Em 1969, Knuth largou o cargo de professor na Caltech para virar professor de ciência da computação na Stanford, onde ele está trabalhando até hoje.

Principal razão ou feito pelo qual Knuth é conhecido:

Knuth é muito conhecido pela sua série de livros “The Art of Computer Programming”. Essa série de livros tem o simples objetivo de englobar a área da ciência da computação inteira.

Donald, também é super famoso pela sua contribuição na análise de algoritmos e pela invenção do sistema tipográfico TEX e o sistema de criação de fontes METAFONT, a invenção do TEX por Knuth, uma linguagem para composição de artigos matemáticos e científicos, mudou totalmente a forma como a matemática é impressa e comunicada, criando um sistema de software de computador para o design do alfabeto.

Principais Contribuições

Ele praticamente criou o campo de análise de algoritmos e fez muitas das principais contribuições a vários ramos da teoria da computação. Ele também criou o sistema tipográfico TEX, o sistema de criação de fontes METAFONT, além de ser pioneiro do conceito de programação literária com seu livro “The Art of Computer Programming”.

Prêmios e Distinções

  • First ACM Grace Murray Hopper Award, 1971
  • Turing Award, 1974
  • Lester R. Ford Award, 1975[57] and 1993
  • Josiah Willard Gibbs Lecturer, 1978
  • National Medal of Science, 1979
  • Golden Plate Award of the American Academy of Achievement, 1985
  • Franklin Medal, 1988
  • John von Neumann Medal, 1995
  • Harvey Prize from the Technion, 1995
  • Kyoto Prize, 1996
  • Fellow do Computer History Museum, 1998
  • Asteroid 21656 Knuth, nomeado em seu nome em Maio de 2001
  • Katayanagi Prize, 2010
  • BBVA Foundation Frontiers of Knowledge Award na categoria de Information e Communication Technologies, 2010
  • Turing Lecture, 2011
  • Stanford University School of Engineering Hero Award, 2011
  • Flajolet Lecture Prize, 2014

Produção Científica

Donald Knuth escreveu (ou é co-autor) de aproximadamente 23 livros. No entanto, a sua obra magna é, sem dúvida, o “The Art of Computer Programming”, que é considerada a blíbia da Ciência da Computação.

Segundo o entusiasta de tecnologia Fabio Akita:

“Se você acha que precisa ter o livro mais completo de todos, ele não existe mas o mais próximo não é um livro, mas uma coleção de livros, do lendário Donald Knuth, o famoso The Art of Computer Programming, o magnum opus da ciência da computação que ele começou a escrever em 1962 e até hoje não terminou. Eu já falei dele em outro video mas os livros que eu tenho são do 1 ao 3 mais o 4A. Segundo a Wikipedia ele tá escrevendo os fascículos 5 e 6 que são os primeiros dois terços do volume 4B.

E quanto ainda falta pra acabar? Bom, depois do 4B ainda vai ter os volumes 4C e 4D e depois os volumes 5, 6 e 7. Ou seja, o que eu tenho aqui ainda não é nem metade do que seria a obra completa. Essa coleção é o Game of Thrones da computação, e o Knuth é o George R R Martin da nossa área. Todos cruzando os dedos pra ele conseguir terminar tudo. Os livros do Wirth e do Cormen eu diria que são um resumão do que seria os livros de 1 a 4D do Knuth.

Ou seja, os temas dos primeiros 7 volumes do Knuth, que incluem os volumes 4B a 4D que ele ainda não escreveu são o que você encontra no sillabus dos primeiros anos de um curso de ciência da computação. Começa com coisas como matemática básica, números, potências, logaritmos, teoria dos números, permutações, fatoriais, coeficientes binomiais, ou seja, não só o assunto de algoritmos mas temas de matemática que você aprende nos primeiros 2 anos de ciências da computação em matérias como Álgebra, Estatística e probabilidade.

No primeiro volume do Knuth você tem coisas básicas como pilhas, filas, listas ligadas, listas circulares, arrays, árvores binárias, que foram assuntos que eu detalhei alguns videos atrás. Por isso o primeiro volume se chama Algoritmos Fundamentais. Já o segundo volume complica um pouco mais. Ele se chama Algoritmos Seminuméricos e logo de cara o primeiro assunto no livro é definir números aleatórios.

E sim, essa coleção inteira é bem pesada em notação matemática. Se você não tá acostumado é absolutamente intimidador. Entendida toda a base matemática fundamental, só no volume 3, que é chamado de Ordenação e Procura, é que vamos finalmente encontrar os algoritmos de ordenação como inserção, seleção e procura com temas como pesquisa binária e árvores balanceadas que eu também já mostrei alguns videos atrás.

Finalmente chegamos ao volume 4A que é chamado de Algoritmos de Combinatória Parte 1 que explica o básico de álgebra booleana, truques e técnicas de operações bitwise, diagramas de decisão binária e geração de todas as possibilidades onde entramos no assunto de n-tuplas, permutações, combinações, partições, conjuntos e muito mais. E isso é parte 1 porque o tema de Algoritmos de Combinatória vai se esticar nos próximos volumes ainda não escritos, do 4B ao 4D.

Só esses 4 volumes somam quase 3 mil páginas. Pra colocar em perspectiva, o livro do Cormen é menos da metade disso. Mas se prestou atenção vai notar que os livros do Knuth cobrem mais assuntos, em particular a base matemática. Livros mais focados só em algoritmos e estruturas de dados, como do Cormen, se preocupam menos com as provas matemáticas e mais em como cada elemento é implementado e funciona. Eu diria que é mais prático pra gente. Você só vai realmente ler página a página do Knuth se for se especializar em matemática aplicada ou algo assim.

Mas pra assuntos específicos, vale como referência se quiser descer a fundo. Por exemplo, como realmente números aleatórios são matematicamente definidos? Eu repito, a grande maioria de nós não tem o vocabulário de matemática teórica suficiente pra realmente conseguir absorver tudo do Knuth, por isso qualquer coisa perto do livro do Cormen é mais prático. Mesmo o Cormen é um pouco pesado em matemática, então qualquer livro de algoritmos e estruturas de dados é suficiente.

Mas e os livros de 5 a 7 que o Knuth ainda não escreveu? Os títulos parecem que vão ser Algoritmos Sintáticos, teoria de linguagens livres de contexto e técnicas de compiladores. Linguagens livres de contexto você vai cair no trabalho mais importante do Noam Chomsky - e na minha opinião, a única coisa que você precisa ler dele. Enfim, na realidade já existem livros que cobrem esses assuntos. Se você fez ciência da computação já sabe.”

Curiosidades

  • Na escola, os interesses de Knuth eram mais voltados para a música do que para a matemática. Knuth tocava saxofone e, mais tarde, tuba, na banda da escola. Embora passasse muito tempo dedicado à música, Knuth não negligenciou as outras matérias escolares e terminou o secundário em 1956 com a maior média de notas que alguém já havia alcançado na sua escola.
  • Knuth teve o primeiro encontro com computadores no primeiro ano na Case, antes de mudar para matemática. Ao usar o IBM 650 consultou o manual para descobrir como escrever programas e achou que podia fazer melhor:

“… the manual we got from IBM would show examples of programs and I knew I could do … better than that. So I thought I might have some talent.”

  • Em 1958 escreveu um programa de computador para analisar o desempenho da equipe de basquete da faculdade e a IBM usou uma fotografia sua no seu anúncio e publicidade.
  • Foi graças ao seu pai que Donald adquiriu interesses pela educação, matemática e música.

Referências

d/donald_knuth.txt · Última modificação: 2022/09/02 23:04 por Mateus Herbele