Projeto e Análise de Algoritmos (2025-2)

Compreender os fundamentos teóricos para a análise de algoritmos por meio de ferramentas matemáticas que permitam a construção de soluções eficientes para problemas usuais nas aplicações computacionais. Ao final do curso o aluno dever ser capaz de:

1. Analisar a complexidade, quanto aos recursos de tempo e espaço, de algoritmos utilizando a análise assintótica;
   
2. Provar a correção de algoritmos;
   
3. Conhecer os paradigmas de divisão e conquista, algoritmos gulosos e programação dinâmica para projetos de algoritmos;
   
4. Compreender os fundamentos da teoria de NP-completude.
   

• Fundamentos matemáticos para a análise de algoritmos;
  
  • Indução;
    
  • Crescimento de funções;
    
  • Notação assintótica;
    
  • Relações de recorrência.
    
• Análise assintótica de algoritmos;
  
• Paradigmas de projeto de algoritmos;
  
  • Projeto por indução;
    
  • Divisão e conquista;
    
  • Programação dinâmica;
    
  • Algoritmos gulosos.
    
• Fundamentos de complexidade computacional.
  
  • Redução entre problemas;
    
  • As classes P e NP;
    
  • Problemas NP-completos.
    

O conteúdo será abordado por meio de aulas expositivas estruturadas da seguinte forma:

1. Leituras dirigidas;
   
2. Exercícios semanais (via Teams);
   
3. Avaliações escritas.
   

• Na medida do possível as aulas serão gravadas e estarão disponíveis no Teams.
  
• Todo o material do curso estará disponível em https://flaviomoura.info/paa-2025-2.html.
  

A avaliação será composta das seguintes partes:

1. Duas provas escritas individuais e sem consulta:
   
   1. Prova 1 (01/out/2025) - 40 pontos;
      
   2. Prova 2 (03/dez/2025) - 40 pontos;
      
2. Exercícios semanais - 20 pontos;
   
3. Projeto (opcional) - 20 pontos .
   

Para ser aprovado o aluno deve cumprir simultaneamente os seguintes itens:

• Frequência maior ou igual a 75%;
  
• Obter pelo menos 50 pontos no total.
  

A menção final é definida como a seguir:

1. Referência principal: cite:&cormenIntroductionAlgorithms2022.
   
2. Referências complementares: cite:&baaseComputerAlgorithmsIntroduction1999;&levitinIntroductionDesignAnalysis2012;&manberIntroductionAlgorithmsCreative1989;&roughgardenAlgorithmsIlluminatedPart2017;&roughgardenAlgorithmsIlluminatedPart2018;&roughgardenAlgorithmsIlluminatedPart2019;&toscani2012algoritmos;&sipserIntroductionTheoryComputation1996;&brassard.
   

bibliographystyle:plain
bibliography:zotLib.bib