CCO - 00.2.01 - Projeto e Análise de Algoritmos

Quantidade de créditos: 8
Total de horas de aulas teóricas: 60
Total de horas de aulas de exercícios, seminários ou estudos dirigidos : 60

Objetivo

  • Tornar os alunos aptos a aplicar estratégias algorítmicas avançadas a seus projetos;
  • Capacitar os alunos a analisar a correção e o desempenho de algoritmos não-triviais;
  • Permitir aos alunos consolidar os paradigmas de projeto de algoritmos por meio de diversos exemplos e demonstrações;
  • Familiarizar os alunos com noções da teoria da complexidade computacional;
  • Estimular os alunos a avaliar quais técnicas de projeto, algoritmos e estruturas de dados se adequam melhor a cada situação, problema ou aplicação. 

Ementa

  • Análise assintótica: notação O, Omega e Theta
  • Paradigmas de projeto de algoritmos: princípios, algoritmos e aplicações de divisão-e-conquista, algoritmos gulosos e programação dinâmica
  • Grafos: percursos, caminhos mínimos, fluxo e contração
  • NP-Completude: completude, definição e interpretação (questão P vs NP)
  • Abordagens para tratar problemas NP-Completos e NP-Difíceis

Bibliografia Principal

  1. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., McGraw-Hill, 2009. (T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., McGraw-Hill, 2009.).
  2. Sedgewick, K. Wayne. Algorithms, 4th. ed., Addison-Wesley, 2011. (R. Sedgewick, K. Wayne. Algorithms, 4th. ed., Addison-Wesley, 2011.).
  3. Nivio Ziviani. Projeto de algoritmos: com implementações em Java e C++. 2. ed. São Paulo: Cengage Learning, 2011. (Nivio Ziviani. Projeto de algoritmos: com implementações em Java e C++. 2. ed. São Paulo: Cengage Learning, 2011.).