Optimização Combinatória
0
2019-2020
01001401
Área Científica do Menor
Português
Presencial
Semestral
6.0
Opcional
1º Ciclo - Licenciatura
Conhecimentos de Base Recomendados
Programação Linear e Matemática Discreta.
Métodos de Ensino
Se o aluno não reúne condições então em lugar dos trabalhos para casa e das frequências deve realizar um exame que corresponde a 90% da nota final.
Resultados de Aprendizagem
Em Otimização Combinatória estudamos técnicas combinadas de combinatória, programação linear e algoritmos para resolver problemas de otimização em estruturas discretas ou mistas. Exemplos de problemas reais são a calendarização de exames e aulas numa escola, o sequenciamento de tarefas num processo industrial, o dimensionamento de pessoal num centro de atendimento e o dimensionamento de redes de telecomunicações. Grande parte dos problemas provém de áreas como a Investigação Operacional e as Ciências de Computação.
Competências genéricas:
Competência na utilização de ferramentas computacionais;
Conhecimento de resultados matemáticos;
Capacidade de generalização e abstração;
Capacidade de formular e resolver problemas;
Conceção ou utilização de modelos matemáticos para situações reais;
Expressões escrita e oral rigorosas e claras;
Capacidade de investigação;
Imaginação e criatividade;
Espírito crítico;
Capacidade de comunicação.
Estágio(s)
NãoPrograma
Árvore geradora mínima (Prim e Kruskal).
Caminhos mais curtos (Ford-Bellman e Dijkstra).
Fluxo Máximo e Corte Mínimo (Ford-Fulkerson).
Emparelhamentos em grafos bipartidos (Kuhn) e não bipartidos (Edmonds).
Unimodularidade Total (Hoffman-Kruskal e Ghouila-Houri).
Estrutura facial de poliedros (polar, pontos extremos, faces, facetas).
Planos cortantes (Gomory, lift-and-project, split, mir).
Um estudo computacional (e.g., o problema do caixeiro viajante).
Métodos de Avaliação
Avaliação
Apresentação de um trabalho (10%) + Trabalhos para casa e Duas frequências (90%) ou Exame (90%): 100.0%
Bibliografia
COOK, W.; CUNNINGHAM, W.; PULLEYBLANK W. [et.al.] (1998). Combinatorial Optimization, Wiley-Interscience. (Cota na Biblioteca: 90C/Com.Coo)