Programação Competitiva

Código:

CC3036

Sigla:

CC3036

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

Ocorrência: 2018/2019 - 1S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~pribeiro/aulas/pc1819/
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Mestrado Integrado em Engenharia de Redes e Sistemas Informáticos

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	16	Plano de estudos a partir de 2014	3	-	6	42	162
MI:ERS	10	Plano Oficial desde ano letivo 2014	2	-	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órica 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)
- Geometrica 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 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 nas aulas partes selecionadas das suas soluções e será promovida uma wiki colaborativa onde irão ser colocadas ligações relevantes e explicações de vários soluções e estratégias

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	30,00
Trabalho prático ou de projeto	70,00
Total:	100,00

Componentes de Ocupação

Designação	Tempo (Horas)
Apresentação/discussão de um trabalho científico
Estudo autónomo
Frequência das aulas
Trabalho escrito
Trabalho laboratorial
Total:	0,00

Obtenção de frequência

Não aplicável.

Fórmula de cálculo da classificação final

- Apresentações e explicações dos algoritmos e problemas nas aulas e wiki: 30%
- Implementações submetidas: 30% a 60%
- Participação em eventos competitivos: 10% a 40%

A ponderação da participação em eventos competitivos depende do sucesso obtido e da dificuldade do evento (ex: uma ronda de Div. 1 de Codeforces é mais valiosa e complicada do que uma ronda de Div. 2)

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.