Programação Competitiva I

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 a solução de problemas particulares. As aulas laboratoriais consistem na resolução de vários problemas de programação, individualmente e em equipa. A avaliação tem em conta as classificações obtidas na resolução de vários problemas de programação e em defesas individuais. O sistema Mooshak, habitualmente usado em competições de programação, é utilizado como uma ferramenta de avaliação automática para a resolução dos trabalhos de programação. Os casos de teste para cada problema são gerados de forma a testarem cenários distintos.

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 a algoritmos e estruturas de dados

2. Estratégias de resolução de problemas de competição

3. Paradigmas algorítmicos

3.1. Divisão e conquista

3.2. Backtracking

3.3. Programação dinâmica

3.4. Algoritmos gulosos

3.5. Simulação

4. Aplicações

4.1. Problemas de procura

4.2. Problemas de grafos

4.3. Geometria computacional

4.4. Problemas de cadeias de carateres

4.5. Problemas numéricos

4.6. Criptografia/hashing

4.7. Problemas ad-hoc

4.8. Outros problemas

Docente(s) responsável(eis)

Alexandre Daniel Borges de Jesus

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

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 3rd ed., 2009.
S.Skiena and M. Revilla, Progamming Challenges, Springer, 2003.
A. Laaksonen, Guide to Competitive Programming, Springer, 2nd ed., 2020
J. Erikson, Algorithms, 2019
S. Halim, F. Halim, Competitive programming 4 (books 1 and 2), 2020.