Programação Competitiva

Código:

CC3032

Sigla:

CC3032

Áreas Científicas
Classificação	Área Científica
OFICIAL	Ciência de Computadores

Ocorrência: 2024/2025 - 1S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~pribeiro/aulas/pc2425/
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Licenciatura em Ciência de Computadores

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
L:CC	25	Plano estudos a partir do ano letivo 2021/22	2	-	6	42	162
			3
L:IACD	2	Plano Oficial a partir do ano letivo 2021/22	3	-	6	42	162

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.