Programação Competitiva
Áreas Científicas |
Classificação |
Área Científica |
OFICIAL |
Ciência de Computadores |
Ocorrência: 2024/2025 - 1S ![Requerida a integração com o Moodle Ícone do Moodle](/fcup/pt/imagens/MoodleIcon)
Ciclos de Estudo/Cursos
Docência - Responsabilidades
Língua de trabalho
Português - Suitable for English-speaking students
Objetivos
Os principais objectivos são a consolidação e aquisição de novos conhecimentos de algoritmia e estruturas de dados e do seu eficiente desenho e implementação através da realização de desafios de programação no estilo de concursos de programação e de entrevistas de emprego.
Resultados de aprendizagem e competências
Ao terminar esta unidade curricular os alunos deverão:
- Ter demonstrado capacidades de resolução criativa de problemas de carácter algorítmico;
- Conhecer um leque variado de ideias algoritmicas e estruturas de dados e como os adaptar/aumentar para os aplicar a problemas concretos;
- Ter criado um portfolio pessoal de código com soluções para múltiplos problemas, incluindo implementações eficientes e reutilizáveis dos algoritmos e estruturas de dados subjacentes;
- Ter demonstrado capacidade de discutir a alto nível os problemas e possíveis variantes, percebendo as implicações ao nível da eficiência dessas variações
Modo de trabalho
Presencial
Programa
Ao resolverem os problemas, múltiplas áreas irão ser abordadas e combinadas, incluindo tópicos em (entre parenteses exemplos de sub-tópicos dentro das áreas):
- Estratégias gerais de resolução de problemas (ex: “understand/plan/do/check”, generalizações e especializações, separação de conceitos)
- Estruturas de Dados (ex: aŕvores binárias de pesquisa, segment trees, interval trees, fenwick trees, range trees, quadtrees, kd-trees, union-find, decomposição sqrt, sparse tables)
- Estratégias algorítmicas (ex: pesquisa exaustiva, “backtracking”, pesquisa com cortes e “meet-in-the-middle”, dividir para conquistar e variantes, pesquisa binária da resposta, algoritmos “greedy”, programação dinâmica, lazy propagation em árvores, sliding windows)
- Matemática (ex: tópicos em teoria de números como geração de números primos, aritmética modular e resolução de equações ; combinatória como permutações, combinações, coeficientes binomiais, princípio de inclusão-exclusão; cálculo de probabilidades; teoria de jogos incluindo jogos como o nim e teorema de Sprague-Grundy)
- Programação Dinâmica Avançada (ex: desenho de novas recorrências com várias dimensões, optimizações como “Knuth” ou “convex hull” optimization)
- Grafos (ex: dfs e bfs com aplicações como pontos de articulação ou ssc; árvores de suporte; distâncias mínimas e variantes; algoritmos em árvores como diâmetro e LCA; fluxos, matchings e min-cuts incluindo algoritmos como Hopcroft-Karp ou Dinic)
- Geometria Computacional (ex: representação de objectos geométricos, primitivas robustas tais como ccw, interseções, invólucro convexo, compressão de coordenadas, line sweep)
- Strings (ex: hash tables, KMP, Aho-Corasick, suffix arrays)
É também expectável que para resolverem os problemas os alunos ganhem um conhecimento aprofundado de toda a biblioteca disponível na sua linguagem de eleição (ex: STL em C++, API de Java)
Bibliografia Obrigatória
Steven Halim and Felix Halim; Competitive Programming, 3rd Edition, 2013
Bibliografia Complementar
Cormen Thomas H. 070;
Introduction to algorithms. ISBN: 978-0-262-03384-8
Skiena Steven S.;
Programming challenges. ISBN: 0-387-00163-8
Skiena Steven S.;
The algorithm design manual. ISBN: 978-1-84800-069-8
Antti Laaksonen; Competitive Programmer's Handbook
Métodos de ensino e atividades de aprendizagem
As aulas teórico-práticas incluem a apresentação de teórica de alguns dos tópicos abordados, bem como a apresentação e discussão de problemas selecionados. É esperado dos alunos que implementem soluções para um leque alargado de problemas (a submeter para avaliação automátíca não só no avaliador Mooshak da própria UC, mas também em múltiplas plataformas como o UVA Online Judge, Codeforces, Kattis ou SPOJ). Será também promovida a participação e submissão de problemas em contexto competitivo, com tempo controlado, em provas variadas (ex: rondas de Codeforces). Os alunos irão também apresentar partes selecionadas das suas soluções e irão também criar um problema.
Tipo de avaliação
Avaliação distribuída sem exame final
Componentes de Avaliação
Designação |
Peso (%) |
Apresentação/discussão de um trabalho científico |
20,00 |
Trabalho prático ou de projeto |
80,00 |
Total: |
100,00 |
Componentes de Ocupação
Designação |
Tempo (Horas) |
Estudo autónomo |
60,00 |
Frequência das aulas |
42,00 |
Trabalho laboratorial |
60,00 |
Total: |
162,00 |
Obtenção de frequência
Não aplicável.
Fórmula de cálculo da classificação final
- Apresentações, discussão de soluções e criação de problema: 20%
- Implementações submetidas: 50%
- Participação em eventos competitivos: 30%
Observações
Necessário conhecimentos ministrados nas u.c. de Estruturas de Dados (CC1007) e de Desenho e Análise de Algoritmos (CC2001), ou em u.c. equivalentes.