Problemas e algoritmos. Complexidade de problemas. Classes de complexidade. Reduções. Interpretação de uma redução no contexto da complexidade de problemas. Limites superiores e inferiores de complexidade. Problemas de decisão e problemas de otimização. Teoremas de Cook e Levin. Problemas NP-completos. Problemas NP-difíceis. Técnicas de projeto de algoritmos: algoritmos exatos, heurísticos e metaheurísticos. Subestrutura ótima de problemas.
- Professor(a): Ana Paula Ludtke Ferreira