Programação Competitiva II

Conhecimentos de Base Recomendados

Não aplicável.

Métodos de Ensino

As aulas teórico-práticas servem para introduzir os conceitos teóricos e para discutir abordagens a problemas particulares. As aulas laboratoriais consistem na resolução de problemas de programação, individualmente e em equipa, sendo dada especial atenção à interpretação de enunciados, modelação dos problemas, e questões de implementação. A avaliação tem em conta as classificações obtidas na resolução de vários problemas de programação e em defesas individuais.

Resultados de Aprendizagem

Desenvolver competências na resolução de problemas de programação baseados em desafios de engenharia em que não é normalmente possível encontrar soluções ótimas em tempo útil. Problemas deste tipo surgem regularmente no contexto de competições de programação e algoritmos tais como o Google Hash Code e os desafios ROADEF/EURO. A partir de uma descrição de um problema, o estudante bem sucedido deverá ser capaz de, individualmente e em grupo, o relacionar com outros problemas conhecidos, identificar abordagens heurísticas apropriadas para o resolver, desenvolver um modelo adequado, e implementar uma abordagem de resolução eficaz de forma eficiente.

Estágio(s)

Não

Programa

1. Introdução 1.1. Problemas de otimização em competições de programação 1.2. Heurísticas construtivas e de melhoramento 1.3. Princípios heurísticos 1.4. Estratégias de resolução de problemas de competição.

2. Modelação de problemas 2.1. Definição do espaço de decisão 2.2. Representação das soluções 2.3. Avaliação da qualidade das soluções 2.4. Regras de construção e estruturas de vizinhança 2.5. Tratamento de restrições.

3. Heurísticas e meta-heurísticas. 3.1. Métodos construtivos: construção gulosa, algoritmos de colónias de formigas, procura em feixe 3.2. Métodos de melhoramento: trepa colinas, procura local iterada, algoritmos evolutivos, procura tabu.

4. Questões de desempenho 4.1. Memorização, avaliação preguiçosa e avaliação incremental 4.2. Sintonização e adaptação de parâmetros.

Docente(s) responsável(eis)

Carlos Manuel Mira da Fonseca

Métodos de Avaliação

Avaliação
A avaliação tem em conta as classificações obtidas na resolução de vários problemas de programação e em defesas individuais: 100.0%

Bibliografia

George Polya, How to Solve It: A New Aspect of Mathematical Method. Princeton University Press, 1945. Reprinted by Penguin Books, 1990. Fred Glover and Manuel Laguna,Tabu Search, Kluwer, 1997. Thomas Bäck, David B Fogel, and Zbigniew Michalewicz (eds.), Evolutionary Computation 1 - Basic Algorithms and Operators, CRC Press, 2000. Thomas Bäck, David B Fogel, and Zbigniew Michalewicz (eds.), Evolutionary Computation 2 - Advanced Algorithms and Operators, CRC Press, 2000. Marco Dorigo and Thomas Stützle, Ant Colony Optimization, MIT Press, 2004. Holger H. Hoos and Thomas Stützle, Stochastic Local Search, Morgan Kaufmann, 2014. Mauricio G. C. Resende and Celso C. Ribeiro, Optimization by GRASP, Springer, 2016. Rafael Martí, Panos M. Pardalos, Mauricio G. C. Resende, Handbook of Heuristics, Springer, 2018.