PT | EN

MINISTÉRIO DA EDUCAÇÃO

UNIVERSIDADE FEDERAL DE SANTA CATARINA

CENTRO TECNOLÓGICO

DEPARTAMENTO DE INFORMÁTICA E ESTATÍSTICA

PROGRAMA DE ENSINO

1. Identificação

Disciplina:INE5451 - Tópicos Especiais em Algoritmos I
Nível:Graduação
Carga Horária:72 horas-aula (Prática: 72)
Vigência:De 2024-1 até a presente data

2. Ementa

-Ementa livre para assuntos relevantes na área de Algoritmos.

3. Cursos Relacionados

4. Objetivos

4.1 Objetivo Geral:

Resolver problemas computacionais avançados, semelhantes aos encontrados nas Maratonas de Programação realizadas anualmente pela Sociedade Brasileira de Computação (SBC) e International Collegiate Programming Contest (ICPC), especialmente com foco em finais sulamericanas e latino-americanas.

4.2 Objetivos Específicos:

  1. Escolher o algoritmo adequado à resolução de cada problema (de maratona) proposto
  2. Justificar a escolha com base na corretude e na eficiência da solução encontrada
  3. Implementar a solução (em C ou C++) e submeter a um juiz online
  4. Discutir possíveis alternativas algorítmicas para o mesmo problema

5. Conteúdo Programático

  1. Problemas ad-hoc e de ordenação [8 horas-aula]
  2. Problemas que dependem de estruturas de dados [8 horas-aula]
  3. Problemas associados a paradigmas de resolução: Backtracking e Divisão e conquista [8 horas-aula]
  4. Problemas associados a paradigmas de resolução: Programação dinâmica e Algoritmos gulosos [8 horas-aula]
  5. Problemas associados a processamento de strings [8 horas-aula]
  6. Problemas que envolvem diretamente a matemática [8 horas-aula]
    1. Sobre teoria de números
    2. Combinatoriais
    3. Com probabilidade
  7. Problemas que envolvem grafos: Busca em grafos [8 horas-aula]
  8. Problemas que envolvem grafos: Árvores geradoras de custo mínimo e Caminhos de custo mínimo [8 horas-aula]
  9. Problemas que envolvem Fluxo em grafos e problemas de Geometria Computacional [8 horas-aula]

6. Bibliografia Básica

  1. Erickson, Jeff. Algorithms. Illinois: Independently published, 2019. ISBN: 978-1-792-64483-2.
  2. Feofiloff, P., Algoritmos em linguagem C, Elsevier, 2009.
  3. Halim, Steven; Halim, Felix. Competitive Programming: Increasing the Lower Bound of Programming Contests. Morrisville: Lulu Press. 2010.
  4. HALIM, Steven; HALIM, Felix. Competitive Programming 2: This increases the lower bound of programming contests. Again. 2011.
  5. Halim, Steven; Halim, Felix. Competitive Programming 3: The New Lower Bound of Programming Contests. Morrisville: Lulu Press. 2013.
  6. Mehlhorn K. Data Structure and Algorithms 1: Sorting and Search, Elsevier, 1984.
  7. Mehlhorn K., Sanders P. Algorithms and Data Structures. The Basic Toolbox, Elsevier, 2008.

7. Bibliografia Complementar

  1. Cormen, T., Leiserson, C., Rivest, R., Stein, R., Introduction to Algorithms, 2nd ed., MIT Press, 2001.
  2. Skiena, S., Revilla, M., ""Programming Challenges: The Programming Contest Training Manual'', Springer-Verlag, New York, 2003.
  3. Kleinberg, Jon; Tardos, Éva. Algorithm Design. Boston: Addison-Wesley Longman Publishing Co. 2005.
  4. Mehlhorn K. Data Structure and Algorithms 2: Graph Algorihtms and NP-Completeness, Elsevier, 1984.
  5. Mehlhorn K. Data Structure and Algorithms 3: Multi-dimentional Searching and Computational Geometry, Elsevier, 1984.
  6. Tutoriais do TopCoder: https://www.topcoder.com/community/competitive-programming/tutorials