Exemplos

3 Março 2022, 18:00 • Luis Eduardo Neves Gouveia

Exemplos de aplicação dos algorimos estudados

Introdução e heurísticas construtivas para o TSP

3 Março 2022, 16:00 • Luis Eduardo Neves Gouveia

Conceito de Heurística. Introdução e motivação. Análise: i) garantias de qualidade; ii) análise probabilística; iii) análise empírica.

Heurísticas para o problema do caixeiro viajante (como exemplo de vários temas):

     Instâncias com desigualdade triangular

      Heurística do Vizinho Mais Próximo.  

      Heurísticas de Inserção.  

Not Taught.

24 Fevereiro 2022, 18:00 • Francisco Saldanha da Gama

Não houve aula por a matéria lecionada ainda não o permitir.

Apresentação e Noçĩes de Complexidade algorítmica.

24 Fevereiro 2022, 16:00 • Francisco Saldanha da Gama

Apresentação da UC.
Complexidade algorítmica: breve introdução. Problemas de decisão associados a um problema de otimização.
Redução de problemas, transformação polinomial. Classes P, NP, NP-completo, NP-difícil.