Análise de Algoritmos

"Computer science is no more about computers
than astronomy is about telescopes."

A análise de algoritmos estuda a correção e o desempenho de algoritmos. Em outras palavras, a análise de algoritmos procura respostas para perguntas do seguinte tipo: "Este algoritmo resolve o meu problema? Quanto tempo o algoritmo consome para processar uma 'entrada' de tamanho n?". (A resposta à segunda pergunta é necessariamente um tanto grosseira, algo como "o consumo de tempo é proporcional a n² log n no pior caso".)

Além disso, a análise de algoritmos estuda certos paradigmas (como divisão-e-conquista, programação dinâmica, gula, busca local, aproximação, etc.) que se mostraram úteis na criação de algoritmos para vários problemas computacionais.

A análise de algoritmos foi inventada e difundida por D.E. Knuth (veja a série de livros The Art of Computer Programming). Knuth foi o pai da ideia de prever o tempo de execução e o consumo de espaço de um algoritmo.

Material didático

Material de apoio

Dicionário de termos técnicos
Índice remissivo
Alguns livros
Alguns recursos na rede WWW
O que é uma prova matemática?
O que eles dizem: citações relativas a algoritmos e sua análise
Exames de Qualificação em Análise de Algoritmos no IME-USP

Acredito que o material deste sítio pode ser útil nos cursos de graduação e pós-graduação em Ciência da Computação e Engenharia de Computação. Também pode ser usado por quem esteja se preparando para o POSCOMP (exame nacional para ingresso na pós-graduação em Computação).

Procuro fazer com que as páginas sejam legíveis em qualquer navegador, mas o Internet Explorer da Microsoft recusa-se a colaborar… Entre outros malfeitos, o IE quebra linhas nos lugares mais absurdos. Sugiro aposentar o IE e adotar outro navegador.