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 que surgem no contexto das competições de programação International Collegiate Programming Contest (ICPC). A partir de uma descrição de um problema, o estudante deverá ser capaz, individualmente e em grupo, de o relacionar com outros problemas conhecidos, identificar a abordagem mais apropriada para o resolver tendo em conta a sua complexidade temporal e espacial, e implementá-la 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
              1. Divisão e conquista
              2. Backtracking
              3. Programação dinâmica
              4. Algoritmos gulosos
              5. Simulação
4. Aplicações
              1. Problemas de procura
              2. Problemas de grafos
              3. Geometria computacional
              4. Problemas de cadeias de carateres
              5. Problemas numéricos
              6. Criptografia/hashing
              7. Problemas ad-hoc
              8. Outros problemas.

Docente(s) responsável(eis)

Luís Filipe dos Santos Coelho Paquete

Métodos de Avaliação

Avaliação
Outra: 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.