Sumários
Problemas NP completos em grafos
12 junho 2009, 14:30 • João Rasga
Motivação e definição do problema do circuito Hamiltoniano (C-HAMILTONIANO), cobertura por grafos e clique.
Teorema: C-HAMILTONIANO é NP-completo.
Enquadramento e consequências do teorema.
Demonstração do teorema.
Problema da paragem majorada em tempo por polinomio
9 junho 2009, 13:00 • João Rasga
Teorema: O problema da paragem majorada em tempo por polinomio é NP-completo.
Enquadramento e consequência do teorema.
Demonstração do teorema.
Aplicações do teorema.
Completude NP. Teorema de Cook-Levin
5 junho 2009, 14:30 • João Rasga
Introdução, motivação e definição de completude NP.
Teorema: CNF-SAT é NP-completo.
Enquadramento e consequência do teorema.
Demonstração do teorema.
Aplicações do teorema.
Completude NP
2 junho 2009, 14:30 • João Rasga
Exercícios sobre redutibilidade muitos para um em tempo polinomial.
Avaliação.