Revisão sobre teoria da complexidade. Estudo de alguns problemas clássicos de otimização combinatória NP-Completos ou NP-Difíceis, tais como, por exemplo, satisfatibilidade, caixeiro viajante, agrupamento de módulos de software, recobrimento de conjuntos, empacotamento de objetos, entre outros. Estudo de métodos heurísticos para problemas de otimização combinatória difíceis, como, por exemplo, métodos construtivos, algoritmos aproximativos, busca local e metaheurísticas. Aplicações. Experimento computacional com heurísticas.