Projeto e Análise de Algoritmos (2025-2)
Monitoria (Adrielly Vitória Costa de Lima)
- Entrar em contato diretamente com a monitora via Teams para fazer o agendamento de dúvidas.
Plano de Ensino (pdf)
Objetivos
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:
- Analisar a complexidade, quanto aos recursos de tempo e espaço, de algoritmos utilizando a análise assintótica;
- Provar a correção de algoritmos;
- Conhecer os paradigmas de divisão e conquista, algoritmos gulosos e programação dinâmica para projetos de algoritmos;
- Compreender os fundamentos da teoria de NP-completude.
Conteúdo programático
- Fundamentos matemáticos para a análise de algoritmos;
- Indução;
- Crescimento de funções;
- Notação assintótica;
- Relações de recorrência.
- Indução;
- 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.
- Projeto por indução;
- Fundamentos de complexidade computacional.
- Redução entre problemas;
- As classes P e NP;
- Problemas NP-completos.
- Redução entre problemas;
Metodologia de ensino
O conteúdo será abordado por meio de aulas expositivas estruturadas da seguinte forma:
- Leituras dirigidas;
- Exercícios semanais (via Teams);
- 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.
Avaliação
A avaliação será composta das seguintes partes:
- Duas provas escritas individuais e sem consulta:
- Prova 1 (01/out/2025) - 40 pontos;
- Prova 2 (03/dez/2025) - 40 pontos;
- Prova 1 (01/out/2025) - 40 pontos;
- Exercícios semanais - 20 pontos;
- 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:
| Menção | Pontos |
|---|---|
| SS (Superior) | 90 – 100 |
| MS (Médio Superior) | 70 – 89 |
| MM (Médio) | 50 – 69 |
| MI (Médio Inferior) | 30 – 49 |
| II (Inferior) | 01 – 29 |
| SR (Sem Rendimento) | 00 ou mais de 25% de faltas |
Notas de aulas (pdf) última atualização em
Cronograma
| Aula | Data | Assunto | Arquivos |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 | |||
| 7 | hanoi.v | ||
| 8 | |||
| 9 | |||
| 10 | |||
| 11 | |||
| 12 | |||
| 13 | pdf, gabarito | ||
| 14 | gabarito | ||
| 15 | |||
| 16 | |||
| 17 | |||
| 18 | |||
| 19 | Programação Dinâmica (parte 1) | ||
| 20 | Programação Dinâmica (parte 2) | ||
| --- | Ponto facultativo | ||
| 21 | Algoritmos Gulosos (parte 1) | ||
| --- | Semana Universitária | ||
| --- | Semana Universitária | ||
| 22 | Algoritmos Gulosos (parte 2) | ||
| 23 | Exercícios | ||
| 24 | NP-completude | ||
| 25 | NP-completude | ||
| 26 | NP-completude | ||
| 27 | NP-completude | ||
| 28 | Revisão para a Prova 2 | ||
| 29 | Prova 2 |
TODO Aula 19
Tema da aula: Programação Dinâmica
Material didático: Capítulo 9 das Notas de aulas
Resumo da aula:
Quadro de Notas
Notas das provas
A tabela a seguir contém as notas das provas (considerando a pontuação máxima de 10 pontos).
| Matrícula | Prova 1(10) | Prova 2(10) | |
|---|---|---|---|
| 1 | 170100332 | ||
| 2 | 180136780 | ||
| 3 | 190025069 | ||
| 4 | 190030526 | ||
| 5 | 190033967 | ||
| 6 | 190095229 | ||
| 7 | 190108665 | ||
| 8 | 190112735 | ||
| 9 | 200016997 | ||
| 10 | 200025937 | ||
| 11 | 200040979 | ||
| 12 | 202037622 | ||
| 13 | 202042829 | ||
| 14 | 211042701 | ||
| 15 | 211066196 | ||
| 16 | 212005220 | ||
| 17 | 221001972 | ||
| 18 | 221002049 | ||
| 19 | 221002067 | ||
| 20 | 221002100 | ||
| 21 | 221003968 | ||
| 22 | 221017023 | ||
| 23 | 221017060 | ||
| 24 | 221017079 | ||
| 25 | 221017088 | ||
| 26 | 221030007 | ||
| 27 | 221030016 | ||
| 28 | 221030034 | ||
| 29 | 221038005 | ||
| 30 | 222001387 | ||
| 31 | 222031116 | ||
| 32 | 231003380 | ||
| 33 | 231003513 | ||
| 34 | 231006239 | ||
| 35 | 231006248 | ||
| 36 | 231006257 | ||
| 37 | 231011650 | ||
| 38 | 231013529 | ||
| 39 | 231013547 | ||
| 40 | 231018884 | ||
| 41 | 231021496 | ||
| 42 | 231025190 | ||
| 43 | 231025216 | ||
| 44 | 232007830 | ||
| 45 | 232012974 | ||
| 46 | 232029274 | ||
| 47 | 242009918 |