Acabei de assistir à primeira aula de Análise de Algoritmos! E por primeira aula eu quero dizer a primeirona mesmo!
O Knuth inventou o termo "análise de algoritmos" em 1969 quando virou professor em Stanford e deu sua aula inaugural. Na época ninguém pensou que seria algo histórico, então ninguém filmou. Aí, para remediar esse erro histórico, esse ano o Knuth fez um remake da aula: juntou o que tinha de anotações da época e recriou a palestra tal como ela tinha sido feita originalmente. Para ficar mais fiel, até colocou uma peruca ridícula haha.
A aula em si é animal, ele pega um algoritmo bobo (calcular o máximo de uma sequência), e faz a análise completa. Povo hoje em dia segue a cartilha do Cormen e fala "ah isso aí é O(n)". Mas o Knuth não quer saber só o pior caso, ele quer saber a média e o desvio padrão. Aí ele passa por stirling numbers, funções geradoras e chega no resultado final (a média é o harmônico menos um, ou seja, praticamente logarítmico).
A parte bacana é que ele diz que a matemática que ensinam tradicionalmente não serve para analisar algoritmos, então ele vai criar um curso novo de "concrete mathematics" só para isso; e abre vagas para orientados que estejam dispostos a ir na lixeira do prédio de computação pegar todas as saídas dos compiladores, para fazer um mutirão e descobrir se conseguiam usar as técnicas novas de análise para melhorar programas da vida real. ("ir na lixeira pegar programas" parece estranho, mas é que na época os programas eram em fita perfurada que iam para a lixeira).
Achei animal, vale a pena assistir!
Nenhum comentário:
Postar um comentário