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

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. Avaliações escritas;
   
3. Atividades complementares (opcional).
   

Os estudantes são orientados a realizar leituras específicas com o objetivo de aprofundar o conhecimento teórico sobre os temas abordados. Essas leituras servem como base para discussões em sala de aula e reflexões individuais, promovendo o pensamento crítico e a compreensão aprofundada dos conteúdos.

A avaliação será composta por duas avaliações escritas individuais e sem consulta:

1. Prova 1 (21/maio/2025) - 50 pontos
   
2. Prova 2 (16/julho/2025) - 50 pontos
   
3. Atividades complementares - 25 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, sendo pelo menos 45 pontos nas provas.
  

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

As atividades complementares somam um total de 25 pontos.

A tabela a seguir contém as notas da prova 1 (considerando a pontuação máxima de 10 pontos).

Na tabela abaixo, as notas da prova 1 foram multiplicadas por 5. Para aprovação na disciplina, a pontuação mínima da coluna "Total Provas" é 45 pontos E, a pontuação mínima da coluna "Total Final" é de 50 pontos.