Sumários
AT24 Complexidade dos Problemas de Optimização
15 maio 2013, 10:00 • Maria Cristina De Sales Viana Serôdio Sernadas
Demonstração de que o algoritmo básico não é polinomial. Obtenção, como corolário, que o algoritmo do simplexo também não é polinomial.
Complexidade de problemas de otimização linear
15 maio 2013, 08:30 • João Rasga
Exercícios sobre análise da complexidade de operações básicas sobre naturais e racionais.
AT23 Complexidade dos Problemas de Optimização
13 maio 2013, 10:00 • Maria Cristina De Sales Viana Serôdio Sernadas
Problemas de computação e de verificação em optimização linear. Demonstração que o problema da verificação em optimização linear está em NP recorrendo à dualidade.
AT22 Complexidade computacional
8 maio 2013, 10:00 • Maria Cristina De Sales Viana Serôdio Sernadas
Noções básicas sobre complexidade computacional: tempo de execução na pior situação e notação assintótica. Classes P e NP.