Análise de Algoritmos

Livro digital

Título:
Análise de Algoritmos

Autor:
Paulo Feofiloff

Categoria:
Tecnologia > Dados

Doador:
Raffaello D. N.

Sinopse:
Você já se perguntou por que seu algoritmo roda em segundos num conjunto de dados e trava no próximo? Ou como provar que a solução que você encontrou é realmente a melhor possível? O minicurso do IME-USP responde exatamente isso: não basta escrever código que funciona — é preciso medir, comparar e demonstrar. Do conceito de notação assintótica (O, Ômega, Teta) até a análise fina de algoritmos recursivos, o material não deixa ponta solta. O percurso começa firme: recursão, recorrências, Mergesort e divisão e conquista. Depois avança por problemas clássicos resolvidos com estratégias diferentes — o segmento de soma máxima é atacado quatro vezes (força bruta, divisão e conquista, programação dinâmica), mostrando na prática como a mesma entrada pode gerar ordens de grandeza de diferença no desempenho. Aí vêm pérolas como Karatsuba (multiplicação de inteiros grandes), algoritmos gulosos aplicados a intervalos disjuntos, programação dinâmica para quebra de linhas em parágrafos — um problema surpreendentemente elegante — e o clássico problema da mochila com variação de aproximação. Não é só teoria: o material discute busca em largura e profundidade em grafos, cobertura por primal-dual e algoritmos probabilísticos para conjuntos independentes. Cada capítulo é autocontido, com definição formal do problema, estrutura recursiva ou gulosa, algoritmo passo a passo e demonstração de complexidade. Ideal para quem já programa e quer entender o que acontece antes do código compilar — e por que um algoritmo bem analisado é mais confiável que qualquer intuição.