Introdução à Complexidade Computacional de Problemas e Algoritmos: Conceitos de Problema e Instância; Conceitos de Algoritmo e (consumo de) Tempo Computacional; Definição de Problema de Decisão; Definição de Problema de Otimização; Algoritmos de Tempo Polinomial; Problemas Intratáveis; As Classes de Problemas P e NP; Problemas NP-Completos e Problemas NP-Difíceis. Parte II: Heurísticas e Meta-Heurísticas: Algoritmos Gulosos; Heurísticas específicas para problemas de Otimização Combinatória (O Problema da Mochila 0-1 e O Problema do Caixeiro Viajante); O conceito de Meta-heurística; Ótimos Locais e Estruturas de Vizinhança; Métodos Construtivos e Métodos de Busca Local. Classificação de Meta-heurísticas; Meta-Heurísticas Iterativas: Simulated Annealing, Iterated Local Search (ILS), Busca Tabu (Tabu Search), GRASP, Reconexão por Caminhos (Path-Relinking), Busca em Vizinhança Variável (Variable Neighborhood Search (VNS)); Meta-Heurísticas Populacionais: Algoritmos Genéticos (Genetic Algorithms), Colônias de Formigas (Ant Colony Optimization (ACO)), Enxame de Partículas (Particle Swarm Optimization (PSO)); Metodologias e Processos de Avaliação de Heurísticas. Como conduzir experimentos computacionais em meta-heurísticas.