Sumários
Introdução à teoria da complexidade computacional
21 Fevereiro 2025, 15:30 • Pedro Martins Pereira Serrão de Moura
Problemas de Sequenciamento. Variante P e regra EDD. Exemplo.
Variante NP. Utilização da heurísitca de Schrage para obter uma sequência de tarefas admissível para um problema de sequenciamento 1 / rj / L'max.
Introdução à teoria da complexidade algorítmica
21 Fevereiro 2025, 13:30 • Pedro Martins Pereira Serrão de Moura
Motivação.
Noção de transformação polinomial entre dois problemas. Exemplos
Problema de decisão associado a um problema de otimização.
As classes P, NP, NP-complete. Problemas NP-difícil.
Alguns problemas NP-Hard: discussão e obtenção de soluções admissíveis.