Sumários

T21: Completude NP

3 fevereiro 2022, 10:30 • José Fragoso Santos

Completude NP e redutibilidade.  
Exemplos de problemas NP-Completos: CNFSAT, 3CNFSAT, Clique, Vertex Cover. 

Programação linear

2 fevereiro 2022, 17:00 • Luís Guerra e Silva

Exercícios sobre modelação de problemas com programas lineares.

T20: Dualidade & Classes de Complexidade

2 fevereiro 2022, 16:00 • José Fragoso Santos

Dualidade em Programação Linear  

  - Programa Dual   
  - Resultados Teóricos: Lema da Dualidade Fraca  & Teorema da Dualidade Forte

Introdução à complexidade computacional: 
  - Problemas de decisão versus problemas de optimização.
  - Algoritmos de decisão versus algoritmos de verificação.
  - Classes P e NP.  

Algoritmo simplex

2 fevereiro 2022, 15:30 • Luís Manuel Silveira Russo

Forma slack, sistema dual e sistema auxiliar.

Algoritmo simplex

2 fevereiro 2022, 14:30 • Luís Manuel Silveira Russo

Forma slack, sistema dual e sistema auxiliar.