Palestra do Jubileu de Donald Knuth "Na árvore de Natal"

Por um quarto de século, o grande professor emérito de Stanford realiza uma palestra especial em dezembro, "Na Árvore de Natal". Com quase 82 anos, Donald Knut realizou novamente a palestra de 25 anos em 5 de dezembro. Ele lembrou à platéia que ainda estava trabalhando diligentemente no livro que escrevia nos últimos 57 anos.

O livro "The Art of Programming" entre programadores é considerado uma das pesquisas mais abrangentes sobre algoritmos. Segundo o site da Universidade de Stanford , este livro é um dos melhores trabalhos científicos do século. "Por causa da minha agenda lotada de escritos, tenho que levar uma vida eremita", escreve Knut em seu site pessoal .

Portanto, é duplamente incomum ver esse grande homem viver.

Nosso site tem sua própria tradição natalina : publicamos resenhas e capturas de tela das recentes palestras de Knuth. Em 2017, eu a descrevi como "conhecer meu amado parente durante as férias" e "uma chance de ver uma ótima mente ao vivo".

A palestra deste ano não foi exceção.

Assim como pi

A palestra de Knut foi realizada em 5 de dezembro, mas foi publicada apenas no sábado, 21 de dezembro. (Na segunda-feira, ela já havia conquistado mais de 2.000 visualizações.)


Knuth tinha outro motivo de orgulho - ele concluiu a palestra, segurando nas mãos uma cópia do suplemento recém-publicado da "Arte da Programação" . Ele disse que neste livro "muitas coisas interessantes e, entre outras coisas, permitem que você aprenda vários algoritmos".


A quinta edição do quarto volume foi lançada no mês passado.

Knut também gostou muito da palestra. "Obrigado a todos por terem vindo", disse Knut à platéia. "Parece que você ainda não está cansado de mim", brincou, acrescentando: "vamos ver se alguém vem no próximo ano ..."

Mas Knut preparou algo especial para a palestra deste ano. Ele mostrou à platéia como, por meio século, incorporou bizarramente dígitos pi em diferentes exercícios de seu livro, de novo e de novo e de novo. Knut disse a seus ouvintes que ele pesquisou o texto inteiro de seu livro "The Art of Programming" usando a ferramenta egrep do Linux e encontrou até 1.700 ocorrências da palavra "pi", ou seja, desde que apareça aproximadamente duas vezes a cada cinco páginas do livro. Ele acredita que o uso de pi nos exemplos permite aos leitores garantir que os algoritmos realmente funcionem mesmo para um conjunto de dígitos escolhido arbitrariamente.

Logo, seu discurso se transformou em uma espécie de atração intelectual - ele compartilhou outros fatos relacionados ao pi, que muitas vezes surpreendiam e às vezes surpreendiam.

Ele começou mostrando a capa de The Numerology of Dr. Martin Gardner, matemático da matriz , e mostrou sua tabela dos 32 primeiros dígitos decimais pi. Knut lembrou como o incluiu em um dos primeiros volumes de "A arte da programação" e citou a afirmação de Gardner de que a interpretação correta dos dígitos pi transmite toda a história da humanidade. "De certa forma, pode-se dizer que o principal objetivo da minha vida é interpretar corretamente os sinais de pi", disse Knut à platéia. "O que de mais importante pode ser feito em sua vida?"

No entanto, a descrição do vídeo diz que "a palestra fala sobre as muitas interpretações desses sinais, tanto certas quanto erradas".

Knut então compartilhou uma regra mnemônica para lembrar os primeiros dígitos de pi. Você pode obter cada um dos seus primeiros dígitos - 3,14159265358979 - contando o número de letras em cada palavra da frase:

"Como eu preciso de uma bebida - alcoólica, é claro - depois das pesadas palestras envolvendo mecânica quântica". [aprox. trad .: analogue in Russian - “Como eu quero e desejo sair de mim depois desses relatos estúpidos que levam à depressão grave”.]

Em seguida, ele demonstrou um livro que chamou de "uma das maiores realizações da literatura ULIPO " - um tipo de literatura em que os escritores seguem restrições estritas (e às vezes matemáticas). Como se chama?

Not A Wake: Um Sonho Incorporando os Dígitos de Pi Totalmente para 10000 Decimais


O número de letras em cada palavra desse nome também corresponde exatamente à sequência dos dígitos pi. Knut citou a contracapa: "É uma peça, uma história, fantasias em versos modernos e outros escritos, seguindo, sem exceção, os motivos matemáticos dos livros didáticos". Essa frase também consiste em palavras cujo comprimento corresponde aos dígitos de pi. "O autor do livro", acrescenta Knut, "alcança até 10.000 dígitos nele". Então ele leu a primeira página poética do livro:

"Agora eu caio, um subúrbio cansado em um líquido debaixo das árvores
À deriva ao lado de florestas fervendo de vermelho no crepúsculo sobre a Europa ... "


O número 0 é indicado por palavras de dez letras e 11 pode ser representado por palavras de onze letras. "O autor chamou essa linguagem de pi-lish " , disse Knuth com uma risada. E a famosa sequência de seis noves seguidos? O poeta escreveu:

"Sem culpa, sem sangue, sem culpa, incessante, sem limites, sem limites."

A platéia aplaudiu e Knut continuou lendo o livro. Possui ensaios, poemas curtos, epigramas e até um roteiro com diálogos para um filme épico de ficção científica chamado Zompyr Chronicle . Cada palavra tem um comprimento exatamente igual ao sinal correspondente pi.

"No entanto, as palavras cruzadas tornaram-se verdadeiras acrobacias."

Espere um minuto, o que? Sim, aderindo estritamente ao comprimento das palavras dadas por cada pi, uma das páginas do livro de repente se transforma em uma dica para palavras cruzadas. Isso é seguido pelas próprias palavras cruzadas, nas quais você precisa inserir as respostas. Seu nome deixa claro que as palavras-resposta são os nomes dos livros com as primeiras letras das palavras reorganizadas. De fato, as dicas e respostas são criptografadas com o livro clássico de Walt Whitman, Greaves of Lass, e o romance revolucionário de James Joyce, Fake de Winnegan.

E no final do livro há até o soneto shakespeariano perfeito ...

Então Knuth admitiu que no índice do volume 4A de seu próprio livro há uma referência particularmente complicada ao número pi: "você precisa entender como é a página 382 pi" ...

Resposta correta: +00 ++ - +++ - 000-

Isso é pi em "um dos sistemas de números mais surpreendentes" - um sistema de números ternário balanceado, no qual os caracteres 0, + e - são usados ​​para representar números em um sistema base 3.

Enigmas com pi

Knuth voltou-se para as galés preliminares da quinta edição recém-publicada do quarto volume. Ele disse que em qualquer página é provável que você encontre um quebra-cabeça porque "descobriu-se que os tipos de algoritmos descritos aqui são melhor ilustrados por sua relação com os quebra-cabeças". E a ênfase no livro não está em como resolver quebra-cabeças, mas em como criá- los. Como exemplo, ele mostrou ao público seu quebra-cabeça Sudoku, no qual os números finalizados eram 3, 1, 4, 1, 5, 9 ...

"Consegui encaixar os primeiros 32 caracteres pi aqui."


É possível criar sudoku mais do que um ches com 32 dígitos pi? Não, e há uma razão simples - o 33º símbolo pi é zero, o único dígito não usado no sudoku.

Em seguida, Donald mostrou a capa do Exotische Sudoku , onde não apenas as descargas de pi foram usadas para o sudoku, mas também foram organizadas em círculo . Este livro consiste inteiramente de quebra-cabeças de sudoku, onde os sinais pi são usados ​​como pistas, sujeitos a uma condição adicional - duas linhas diagonais de nove quadrados da solução também devem conter cada dígito uma vez.


Knut também mostrou exemplos de dois quebra-cabeças envolvendo peças de xadrez. Na solução Knight Sudoko, cada linha, coluna e quadrado contém exatamente três cavaleiros de xadrez. As dicas mostram apenas alguns dos cavalos, juntamente com um número indicando quantos outros cavalos eles podem atacar. Obviamente, Knut criou um quebra-cabeça em que esses números são 3, 1, 4, 1, 5 ...

Há também um quebra-cabeça semelhante usando elefantes , é claro, as pistas nele também compõem o número pi.

Knut voltou-se para os quebra-cabeças KenKen, nos quais os números de cada conjunto de quadrados conectados são combinados, fornecendo a solução desejada (usando um operador matemático). Na versão de Knuth, os números das pistas são 3, 14, 15, 9, 2 e 6 ... Há também o quebra-cabeça de Kakuro - uma espécie de palavras cruzadas com números; Knut sugeriu que os leitores criassem uma tarefa em que as respostas seriam 31, 41, 59, 26, 53, 58, 97. No quebra-cabeça Hidato, números consecutivos estão localizados na grade, mas apenas em quadrados adjacentes (horizontal, vertical ou diagonal). Knut sugeriu que os leitores criassem exatamente o mesmo quebra-cabeça com dígitos de pi.

Essa é uma ótima maneira de demonstrar que os algoritmos realmente funcionam com qualquer conjunto de números, mesmo 3.141592. Como uma conclusão grandiosa, Knut provavelmente falou sobre o quebra-cabeça mais interessante de todos - o “muro chinês” (slitherlink). Os solventes devem desenhar uma linha contínua conectando os pontos da grade, tocando o número de lados do "quadrado" dos pontos especificados pelo número quadrado. O livro de Knut faz uma pergunta aos leitores - qual é a surpresa em uma solução específica para o “muro chinês”?

Quando Knut falou sobre a incrível solução para o quebra-cabeça, ele ganhou muitos aplausos.


"Muito obrigado", disse ele solenemente à platéia, "e feliz Natal".