EMENTA

Problemas de escalonamento de tarefas. Algoritmos gulosos exatos. Complexidade de algoritmos e problemas. Conjuntos P e NP. Reduções e Teorema de Cook. Algoritmos de Branch-and-Bound. Parte I. Introdução I.1. Considerações sobre a descrição matemática de problemas de otimização. I.2. Classificação dos modelos de escalonamento de tarefas determinísticos. Parte II: Algoritmos Eficientes II.1. Algoritmos gulosos exatos II.2. Noções de eficiência computacional Parte III: Teoria da Complexidade III.1. Conjuntos P e NP III.2. Reduções e o Teorema de Cook Parte IV: Algoritmos de branch-and-bound IV.1. Problemas relaxados e Programação linear IV.2. Árvore de branch-and-bound

BIBLIOGRAFIA

Pinedo, M. Scheduling: Theory, Algorithms and Systems. Prentice Hall, 2002. Cormem, T. H.; Leiserson, C. E. e Rivest, R. L. Introduction to Algorithms. McGraw Hill, 1997.