Vale do Silício Yoda

Donald Knuth, um mestre em algoritmos, pondera mais de 50 anos de trabalho em sua criação principal, o livro "The Art of Programming", que ele continua a complementar

Donald Knut em sua casa em Stanford, Califórnia. Um perfeccionista assustador, nomeou uma recompensa por encontrar erros em seus livros.

Por meio século, o cientista da computação de Stanford Donald Knuth, um pouco remanescente de Yoda - apesar de ter 193 cm de altura e usar óculos - ocupou uma posição dominante como professor espiritual no campo de algoritmos.

Ele é o autor de The Art of Programming, uma monografia que ele continua escrevendo até hoje, alcançando 4 volumes e que é o trabalho de sua vida. O primeiro volume foi publicado em 1968 e todos os volumes juntos (vendidos em um conjunto por US $ 250 [ou 12.500 ₽ / aprox. Transl.]). Em 2013, foram incluídos na lista de livros que formaram o último século da ciência, compilado pela American Scientist. Também inclui a edição especial da Autobiografia de Charles Darwin, o livro de Tom Wolf " Guys What You Need! ", O livro de Rachel Carson " Silent Spring " e as monografias de Albert Einstein, John von Neumann e Richard Feynman.

A "Arte da Programação", impressa em mais de um milhão de cópias, é uma Bíblia em seu campo. “Parece uma Bíblia real - é muito longa e abrangente; não há outros livros abrangentes ”, diz Peter Norvig, diretor de pesquisa do Google. Após 652 páginas, o volume é fechado com uma citação na contracapa de um livro de Bill Gates: "Se você puder ler o livro inteiro, envie-me seu currículo".

Ele abre com uma passagem da coleção de receitas McCall:

Aqui está um livro que você pediu para publicar em milhares de suas cartas. Demoramos anos para testar e verificar inúmeras receitas para fornecer apenas o melhor, interessante e ideal.

O livro lista os algoritmos, receitas que alimentam a era digital - embora, como o Dr. Knut gosta de salientar, os algoritmos também possam ser encontrados em tablets babilônicos com 3800 anos de idade. Ele é um algoritmo profundamente respeitado; alguns dos padrões mais importantes são nomeados em homenagem a ele, por exemplo, o algoritmo Knut-Morris-Pratt para encontrar uma substring em uma string. Foi cunhado em 1970 e encontra todas as ocorrências de uma determinada sequência de letras no texto - por exemplo, quando você pressiona Ctrl-F para procurar uma palavra em um documento.

Knut agora tem 80 anos, e ele geralmente se veste como quando era jovem, quando começou a odisséia: uma camiseta de mangas compridas pendurada em uma camiseta de mangas curtas e jeans - pelo menos nesta época do ano. Naquela época, ele escrevia programas em código de máquina, tocados com zeros e uns.

"Knut deixou claro que o sistema pode ser entendido até o nível dos códigos das máquinas", disse o Dr. Norvig. Hoje, quando os algoritmos controlam (e interferem) em nossas vidas, o programador médio não tem tempo para investigar a bagunça binária; ele trabalha com hierarquias de abstração, com camadas de código - e geralmente com cadeias de código emprestadas de bibliotecas. Mas a elite de programadores às vezes cai para os níveis mais baixos.

"No Google, às vezes apenas coletamos código do que temos", disse Norvig durante uma reunião da equipe do Google Trips em Mountain View. “E, às vezes, quando você precisa atender bilhões de usuários, precisa fazer isso com eficiência. Uma melhoria de 10% na eficiência pode se transformar em bilhões de dólares e, para atingir esse último nível de eficiência, você precisa entender o que está acontecendo com seus fundamentos. ”


Dr. Knut na California Tech, onde obteve seu doutorado em 1963.

Ou, como Andrei Broder, um famoso cientista do Google e um dos ex-alunos de Knuth, explicou durante a reunião: "Precisamos de alguma base teórica para o nosso trabalho. Não precisamos de algoritmos frívolos, estranhos e de segunda ordem. Não queremos que outros algoritmos digam: "Sim, vocês são idiotas".

Lançado em 2016, o aplicativo Google Trips é um algoritmo de viagem para entretenimento turístico o dia todo. A equipe trabalhou em " maximizar a qualidade dos piores dias " - por exemplo, o algoritmo deve evitar enviar o usuário várias vezes para os mesmos locais para explorar atrações diferentes. Eles foram inspirados em um algoritmo de 300 anos inventado pelo matemático suíço [e alemão e russo] Leonhard Euler, que queria traçar um caminho através da cidade prussiana de Königsberg [atual Kaliningrado], atravessando todas as suas sete pontes apenas uma vez. Knut aborda o problema clássico de Euler no primeiro volume de seu tratado. Uma vez, ele aplicou o método Euler para programar uma máquina de costura controlada por computador.


Seguir a doutrina de Knut ajuda a evitar a idiotice. Ele é conhecido por introduzir o conceito de "programação literária", enfatizando a importância de escrever código que não apenas os computadores possam ler, mas também as pessoas - um conceito que hoje parece algo antiquado. Knut chegou a afirmar que alguns programas de computador podem ser considerados obras literárias, juntamente com os poemas de Elizabeth Bishop e o romance American Pastoral, de Philip Roth, digno do Prêmio Pulitzer.

Ele também é notório por seu perfeccionismo. Randal Munroe, autor dos desenhos animados xkcd e Thing Explainer, aprendeu sobre Knut com os programadores que mencionaram o prêmio que ele prometeu pagar a quem encontrasse um erro em qualquer um de seus livros. Como Monroe lembra, "as pessoas falavam em receber tal cheque como se fosse um Nobel em ciência da computação".

Os exigentes padrões de Knut, tanto literários quanto os demais, podem explicar por que o trabalho de toda a sua vida está longe de estar completo. Ele discutiu com Sergey Brin, co-fundador do Google e seu ex-aluno, se Brin terminaria seu doutorado antes que Knut terminasse sua monografia.

Algoritmo do amanhecer

Aos 19 anos, Knut publicou seu primeiro trabalho sobre um assunto técnico, "O Sistema Potencial de Pesos e Medidas " na revista Mad [Era uma revista humorística, e potrebibi é a palavra polonesa usada em inglês para denotar absurdo. Por exemplo, em seu trabalho, Knut introduziu uma nova medida de comprimento de um potrecybi, igual à espessura da 26ª edição do diário / aprox. transl.]. Ele se tornou um especialista em ciência da computação mesmo antes do advento da ciência da computação, estudando matemática na instituição educacional, que agora é chamada Universidade Keyes da Região da Reserva Ocidental. Ele estudou programas selecionados criados para o mainframe da escola IBM 650, um computador decimal e, encontrando imprecisões, reescrevendo-os e o livro usado na sala de aula. Como hobby, ele calculou estatísticas para um time de basquete e escreveu um programa que os ajudou a vencer em sua liga, graças ao qual o renomado jornalista de televisão Walter Cronkite chegou a gravar uma história na televisão sobre ele chamada "Electronic Trainer".


Durante as férias de verão, Knut ganhou mais dinheiro do que seus professores no ano criando compiladores. O compilador é como um tradutor, transforma uma linguagem de programação de alto nível (reminiscente de álgebra) em uma linguagem de baixo nível (às vezes é um código binário misterioso) e, idealmente, melhora o programa no processo. Na ciência da computação, a otimização é uma arte, refletida em outro ditado de Knuth: "A otimização prematura é a raiz de todos os males".

Como resultado, o próprio Knut se tornou um compilador, descobrindo acidentalmente uma nova área, que mais tarde chamou de "análise de algoritmos". O editor o contratou para escrever um livro sobre compiladores, mas o projeto se transformou em um livro que reúne tudo o que sabia sobre como escrever programas para computadores - em um livro sobre algoritmos.


Knut, em 1981, estudava a edição de 1957 da Mad Magazine, que publicou seu primeiro artigo técnico.


The Art of Programming, volumes 1-4.

"Na época do início do Renascimento, já havia dúvidas sobre a origem dessa palavra", começa o livro. “Os primeiros linguistas tentaram entender sua origem criando combinações como algiros [mórbidos] + aritmos [número].” Na verdade, continua Knut, esse nome apareceu em homenagem ao autor persa do livro do século IX, Abu Abdullah Muhammad ibn Musa al-Khwarizmi, cujo nome no registro latino começou a soar como "Algoritmo". Knut, que nunca se contentou com meias medidas, fez uma peregrinação em 1979 à terra natal de al-Khwarizmi, ao Uzbequistão [ mais precisamente, ele participou de uma conferência em Urgench / aprox. perev. ]

Desde o início, Knut queria escrever um livro. Logo, o Big Bang aconteceu na ciência da computação, então ele revisou seu projeto, dividindo-o em sete volumes. Agora ele está liberando sub-volumes ou problemas. O próximo "Volume 4, Edição 5", que, entre outras coisas, descreve coisas como "backtracking" e "dancing links", deveria ser lançado em 2018. No entanto, ele foi adiado até abril, pois o autor encontra constantemente mais e mais novas tarefas que ele definitivamente deseja apresentar.

Para otimizar as chances de chegar ao fim do trabalho, Knut tem monitorado estritamente seu tempo. Ele se aposentou aos 55 anos, restringiu o discurso em público e recusou o e-mail (pelo menos oficialmente). Andrei Broder lembra que a gestão do tempo era uma característica definidora de seu professor nos anos 80.

Knut costumava encontrar estudantes às sextas-feiras de manhã até ele começar a passar a noite no laboratório de John McCarthy, um dos pioneiros em inteligência artificial, para acessar computadores quando estavam livres. Assustado com a forma como o livro querido pelo seu coração começou a cuidar do advento dos sistemas de publicação digital, Knut estabeleceu o objetivo de desenvolver um sistema de computador para o conjunto tipográfico TeX, que continua sendo o padrão-ouro para todas as formas de comunicação e publicação científica. Alguns consideram a maior contribuição de Knut e a maior contribuição para a gráfica desde a época de Gutenberg.

Esse atraso de dez anos ocorreu quando pessoas diferentes usavam computadores e quando trabalhavam mais rápido à noite, quando a maioria das pessoas dormia. Portanto, Knut mudou para um estilo de vida noturno, mudou o horário em 12 horas e mudou o horário das reuniões com os alunos das 8 para as 12 da noite na sexta-feira. Broder lembra: "Quando eu disse à minha namorada que não poderíamos fazer nada na sexta-feira à noite, porque eu tinha um compromisso com meu supervisor às 22 horas, ela pensou:" Parece tão estúpido que parece ser verdade " "

No entanto, quando Knut decide comparecer em algum lugar pessoalmente, ele dedica toda a sua atenção a este evento. "Estar com ele é um prazer", disse Jennifer Chase, diretora administrativa da Microsoft Research. “Ele está no máximo na comunidade. Se você tivesse uma função de otimização que representasse calor e profundidade, seria Don. ”


Knut discute fontes com Hermann Zapf, um desenvolvedor de fontes.

Domingo com um algoritmo

Knut vive em Stanford e se reúne com pessoas aos domingos. O que ele reservou para o dia inteiro foi excepcional - ele geralmente não está disponível durante o sono diurno, que é um ritual sagrado que dura de 13 a 16 horas. Ele começou o dia cedo, na Primeira Igreja Luterana de Palo Alto, onde deu uma lição para a escola dominical diante de uma multidão de pessoas reunidas em uma sala sem cadeiras. No caminho para casa, ele começa a filosofar sobre matemática.

"Eu nunca vou saber tudo", disse ele. "Minha vida seria muito pior se não houvesse perguntas para as quais eu saberia as respostas e se não houvesse perguntas para as quais eu não saberia as respostas." Ele então ofereceu um passeio pela casa “moderna da Califórnia” que ele e sua esposa construíram em 1970. Seu escritório está cheio de pilhas de pen drives e decorado com artesanato por Jill, uma designer gráfica, no Dia dos Namorados. O mais impressionante é a sala de música, construída em torno de um órgão feito sob medida com 812 tubos. O dia terminou em uma festa com cerveja e enigmas.

Enigmas, jogos, escrevendo um romance sobre números surreais , compondo uma composição musical multimídia de 90 minutos, Fantasia Apocalyptica - essas coisas começam . Uma seção de seu livro se chama Riddles Against the Real World. Ele enviou um trecho do livro para uma equipe de pai e filho, Martin Demein, um artista, e Eric Demein, especialista em TI que trabalha no MIT, porque Knut incluiu suas " fontes de quebra-cabeças algorítmicas " no livro.

"Fiquei agradavelmente surpreendido", disse Eric Demain. "Entrar neste livro é uma honra." Ele mencionou outra citação da Knut, uma conferência bienal inspiradora do Entertainment with Algorithms : "O objetivo principal provavelmente era sempre o prazer".

E então, disse Demane, essa área se tornou prática. Engenheiros, cientistas, artistas - todos se reúnem para resolver problemas reais, como dobrar proteínas, robótica, airbags, usando os métodos de origami desenvolvidos pelos dois Demane, dobrando papel e vinculando-o de várias formas.

Obviamente, toda essa confusão algorítmica causa problemas reais. Algoritmos escritos por pessoas - abordando tarefas cada vez mais complexas e emitindo código cheio de erros e preconceitos - já são algo bastante desagradável. Mas, pior ainda, esses são algoritmos escritos não por pessoas, mas por máquinas.

Os programadores ainda estão treinando máquinas e alimentando dados. Os dados são uma nova área para erros e preconceitos e é mais difícil de detectar e corrigir. No entanto, como Kevin Slavin, professor associado do MIT Media Lab, disse: “Agora estamos escrevendo algoritmos que não conseguem ler. Isso marca um momento histórico único, quando trabalhamos com idéias, ações e tentativas, causadas pela física, originárias das pessoas, mas não compreendidas pelas pessoas. ” Slavin frequentemente observa : "Você tem um futuro brilhante, se for um algoritmo".


Knut em sua mesa em casa, 1999.


Anotações

E será ainda mais maravilhoso se você for um algoritmo bem versado em Knut. "Hoje, os programadores usam o que Knut e outros usaram como componentes de seus algoritmos, e combinam isso com todo o tipo de outras coisas de que precisam", disse Norvig, do Google.

“Com a IA, fazemos a mesma coisa. Só que a etapa de combinação é automática, com base em dados e não no trabalho do programador. Precisamos que a IA seja capaz de combinar os componentes para obter a resposta certa com base nos dados. No entanto, você deve decidir quais são esses componentes. Pode acontecer que cada um dos componentes seja uma página ou capítulo de Knut, pois esta será a melhor maneira de realizar uma tarefa. ”

Portanto, temos sorte de Knut continuar fazendo isso. Ele acha que deve levar mais 25 anos para concluir a "Arte da Programação", embora essa avaliação não tenha mudado desde os anos 80. Os algoritmos que escrevem outros algoritmos receberão seu capítulo no livro ou a página no epílogo? "Definitivamente não", disse Knut.

"Estou preocupado com o efeito que os algoritmos têm no mundo", acrescentou. - Tudo começou com o fato de que os cientistas da computação estavam preocupados porque ninguém os ouvia. Agora estou preocupado que muitas pessoas estejam nos ouvindo. "

☃