Vinicius Fernandes dos Santos  —   Competitive Programming

Vinicius Fernandes dos Santos  —   Programação Competitiva

Main page

Página principal

Disciplina: Programação Competitiva

Esta disciplina terá um enfoque prático, voltado a resolução de maneira ótima de problemas computacionais. O foco da disciplina será na resolução de problemas nos moldes daqueles utilizados em competições de programação.

Para cursar essa disciplina, é extremamente necessário o domínio de técnias de programação básica e que os alunos de tenham cursado a disciplina Algoritmos e Estruturas de Dados III, ou que já dominem seu conteúdo.


Professor:

• Vinicius dos Santos

Programa pretendido (a depender do andamento da disciplina):

• Revisão de algoritmos e estruturas de dados básicos;
• Bibliotecas de estruturas de dados do tipo dicionário;
• Teoria dos Números: aspectos de implementação de congruências, inverso multiplicativo, equações diofantinas, teorema chinês do resto e crivo de Eratóstenes;
• Algoritmos em grafos: componentes fortemente conexas e articulações, componentes biconexas, fluxo máximo de custo mínimo, emparelhamentos com pesos;
• Programação dinâmica: técnicas avançadas de programação dinâmica, máscara de bits, técnicas de fecho convexo para redução de complexidade, otimização de Knuth;
• Estruturas de dados avançadas: árvores de segmento, vetores de sufixo, hash polinomial de strings;
• Algoritmos avançados: decomposição SQRT, ancestral comum mais baixo, algoritmo de Aho–Corasick, meet-in-the-middle;
• Geometria computacional: primitivas geométricas, fecho convexo, algoritmos de varredura.

Bibliografia:

• Halim, Steven, et al. Competitive Programming 3. Lulu Independent Publish, 2013.
• Thomas H.. Cormen, et al. Introduction to algorithms. Cambridge: MIT press, Third Edition, 2009.
• De Berg, Mark, et al. Computational geometry. Springer Berlin Heidelberg, 2000.
• Manber, Udi. Introduction to algorithms: a creative approach. Addison-Wesley Longman Publishing Co., Inc., 1989.