Projeto e Análise de Algoritmos (2004/2)
Raul H.C. Lopes
Programa
O objetivo final do curso consiste em estudar os fundamentos da derivação
formal de algoritmos e da análise de sua complexidade. O curso terá
como foco principal os fundamentos da lógica e matemática. Heurísticas
do TSP e algoritmos para processamento de strings
serão usados como aplicações.Uma tentativa
de plano detalhado segue.
- Derivação formal de programas
- Indução Matemática
- Fundamentos de Análise combinatória
- Permutações e combinações
- Teorema binomial
- Princípios de Inclusão-Exclusão e de Dirichlet
- Recorrências e somas
- Funções geradores
- Probabilidades
Ordenação
Algoritmos em grafos
- Árvore geradoras
- Caminhos mais curtos
- TSP
Processamento de String
- Ordenação
- Casamento de padrões
- Indexação
Algoritmos probabilísticos
- Método Probabilístico
- Monte Carlo
- Las Vegas
- Algoritmos geométricos
Intratabilidade
Referências básicas
- 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ências 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ícios e seminários
Provas