Plano de Ensino

IDENTIFICAÇÃO

EMENTA

Conceitos de programação competitiva; ; Estruturas de dados lineares e não lineares; Algoritmos em grafos; Algoritmos matemáticos; Processamento de strings; Geometria computacional; Árvores de Fenwick; Árvores de segmentos; Menor ancestral comum.

JUSTIFICATIVA

Compreender os conceitos e técnicas envolvidos na resolução de problemas de característica algorítmica, passíveis de implementação em computadores.

OBJETIVO

PROGRAMA

1. Introdução à Programação Competitiva

   1. Sistemas de julgamento

   2. Formato das competições

   3. Linguagens de programação utilizadas nas maratonas de programação

2. Estruturas de Dados e bibliotecas:

   1. Estruturas de dados lineares e não lineares presentes nas bibliotecas padrões

   2. Representação de grafos

   3. Union-find

3. Grafos

   1. Busca em largura e busca em profundidade, componente conexo, ciclos

   2. Árvore geradora mínima

   3. Menor caminho, fluxo em grafos, algoritmos em classes especiais de grafos

4. Algoritmos matemáticos

   1. Aritmética básica e modular

   2. Teste de primalidade, divisores e fatoração

   3. Combinatória, técnicas de contagem e coeficientes binomiais

5. Processamento de strings

   1. Soluções presentes nas bibliotecas padrão

   2. Algoritmo KMP e variantes

   3. Distância de edição; Subsequência comum mais longa; Vetor de sufixos

6. Tópicos adicionais

   1. Geometria computacional: objetos básicos e operações elementares; polígonos; fecho convexo

   2. Árvores de segmentos e árvores Fenwick

   3. Menor ancestral comum

METODOLOGIA

Distribuição das atividades:

• Carga-horária de atividades presenciais (aulas): 45 horas-aula

• Carga-horária de atividades assíncronas (videoaulas, listas de exercícios): 9 horas-aulas

Moodle:

• Todas as informações relativas à disciplina estarão no Moodle.

• Página da disciplina: https://www.moodle.ufu.br/course/view.php?id=12075

• Os alunos matriculados receberão a senha de acesso à disciplina no Moodle por email na primeira semana de aula.

Cronograma:

• Serão realizadas aulas presenciais expositivas com uso de projetor, quadro negro, e demais materiais, conforme o cronograma apresentado na tabela a seguir.

Atendimento aos alunos:

• O atendimento aos alunos será realizado uma vez por semana na sala do professor na modalidade presencial, ou através do Fórum de Dúvidas no Moodle.

AVALIAÇÃO

Sistema de Avaliação

• A cada três aulas será realizado 1 torneio de programação competitiva na plataforma https://vjudge.net/

• A participação em cada torneio valerá 13 pontos na nota final (NF).

• Será feito um ranking dos alunos a partir do número de problemas resolvidos (nos torneios) ao longo do curso.

• A NF de cada aluno será acrescida da seguinte pontuação a partir de seu ranking:

Avaliação de recuperação:

• Será oferecida uma avaliação de recuperação para os discentes que não obtiverem o rendimento mínimo para aprovação e com frequência mínima de 75%. 

• A avaliação de recuperação será composta por uma prova que valerá 10 pontos. 

• A nota da recuperação será adicionada à NF obtida pelo estudante. 

• O estudante que realizar a atividade de recuperação e for aprovado terá limitada a sua nota final em 60 pontos. 

BIBLIOGRAFIA

Básica

1. CORMEN, Thomas H.; RIVEST, Ronald l.; LEISERSON, Charles E. e STEIN, Cliford. Algoritmos: teoria e prática. Rio de Janeiro: Campus, 2012. 926 p., il. Inclui bibliografia e índice. ISBN 9788535236996 (broch.).

2. HALIM, S. Competitive Programming. 3a ed. [S.I.]: Lulu, 2013.

3. SKIENA, S. S.; REVILLA, M. A.Programming Challenges: the programming contest training manual. New York: Springer, 2003.

Complementar

1. KNUTH, D. E. The art of computer programming. 3a ed. Reading, Massachusetts: Addison- Wesley, 1997.

2. MANBER, U. Introduction to Algoritms: a creative approach. [S.I.]: Addison-Wesley, 1989.

3. REVILLA, M. A., POUCHER, W. B. From Baylor to Baylor. [S.I.]: Lulu, 2009.

4. SEDGEWICK, R.; WAYNE, K. Algorithms. 4a ed. Upper Saddle River: Addison-Wesley Professional, 2011.

5. SKIENA, S. S. Algorithm Design Manual. 2a ed. London: Springer, 2008.

6. ETTER, D. M. Engineering problem solving with C. 4th ed. Boston: Pearson, c2013. xx, 460 p., ill., 23 cm. ISBN 9780136085317 (broch.).

APROVAÇÃO

Aprovado em reunião do Colegiado realizada em: ____/____/______

Coordenação do Curso de Graduação: _________________________

---

Documento assinado eletronicamente por Felipe Alves da Louza, Professor(a) do Magistério Superior, em 18/01/2024, às 23:51, conforme horário oficial de Brasília, com fundamento no art. 6º, § 1º, do Decreto nº 8.539, de 8 de outubro de 2015.

---

A autenticidade deste documento pode ser conferida no site https://www.sei.ufu.br/sei/controlador_externo.php?acao=documento_conferir&id_orgao_acesso_externo=0, informando o código verificador 5116648 e o código CRC 53246AAD.

---