Concluindo esta UC, os estudantes deverão ser capazes de:
-
Identificar modelos genéricos de otimização e utilizar as técnicas algorítmicas a eles associadas.
-
Aplicar os modelos estudados a problemas concretos.
-
Analisar a complexidade espacial e temporal de algoritmos.
-
Demonstrar matematicamente a correção de um algoritmo.
-
Compreender e distinguir os diferentes paradigmas das técnicas algorítmicas: dividir e conquistar, algoritmos gananciosos e programação dinâmica.
-
Conhecer e compreender as várias variantes do problema do caminho ótimo.
-
Compreender, aplicar e implementar os algoritmos de Dijkstra, Bellman-Ford e Floyd-Warshal.
-
Compreender os problemas do fluxo máximo e do fluxo máximo de custo mínimo, numa rede e aplicar os algoritmos estudados.
-
Relacionar o fluxo máximo com o corte mínimo e com problemas de conectividade.
-
Identificar e relacionar os problemas de fluxos em redes com problemas de emparelhamento, roteamento, localização e robustez.