Projeto e An\'alise de Algoritmos (2004/2)
Raul H.C. Lopes
Programa
O objetivo final do curso consiste em estudar os fundamentos da deriva\c c\~ao
formal de algoritmos e da an\'alise de sua complexidade. O curso ter\'a
como foco principal os fundamentos da l\'ogica e matem\'atica. Heur\'isticas
do TSP e algoritmos para processamento de strings
ser\~ao usados como aplica\c c\~oes.Uma tentativa
de plano detalhado segue.
- Deriva\c c\~ao formal de programas
- Indu\c c\~ao Matem\'atica
- Fundamentos de An\'alise combinat\'oria
- Permuta\c c\~oes e combina\c c\~oes
- Teorema binomial
- Princ\'ipios de Inclus\~ao-Exclus\~ao e de Dirichlet
- Recorr\^encias e somas
- Fun\c c\~oes geradores
- Probabilidades
Ordena\c c\~ao
Algoritmos em grafos
- \'Arvore geradoras
- Caminhos mais curtos
- TSP
Processamento de String
- Ordena\c c\~ao
- Casamento de padr\~oes
- Indexa\c c\~ao
Algoritmos probabil\'isticos
- M\'etodo Probabil\'istico
- Monte Carlo
- Las Vegas
- Algoritmos geom\'etricos
Intratabilidade
Refer\^encias b\'asicas
- The Science of Programming
David Gries
- Basic Combinatorial Techniques
Daniel I.A. Cohen
- Concrete Mathematics
R. L. Graham, D. E. Knuth, O. Patashnik
- Computers and Intractability
M. R. Garey, D. S. Johnson
Refer\^encias Complementares
- The Art of Computer Programming: Vo.I and Vol.III
D.E. Knuth
- Introduction to Algorithms
Cormen, Rivest, Leiserson, Stein
- Randomized Algorithms
R. Motwani, R. Raghavan
- Discrete Mathematics and its applications
K. H. Rosen
- The Traveling Salesman Problem and Its Variations
G. Gutin, A.P. Punnen
Ferramentas
Listas de Exerc\'icios e semin\'arios
Provas