Projeto e Análise de Algoritmos (2025-1)
Plano de Ensino
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;
- Avaliações escritas;
- 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.
Avaliação
A avaliação será composta por duas avaliações escritas individuais e sem consulta:
- Prova 1 (21/maio/2025) - 50 pontos
- Prova 2 (16/julho/2025) - 50 pontos
- 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:
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 |
Cronograma
Aula | Data | Ativ. Compl. (AC) | Assunto | Arquivos |
---|---|---|---|---|
1 | ||||
2 | pdf, coq | |||
3 | pdf, pdf | |||
4 | pdf, pdf, pdf (opcional) | |||
--- | Aula cancelada | |||
--- | Aula cancelada | |||
--- | Aula cancelada | |||
--- | Aula cancelada | |||
--- | Feriado | |||
5 | ||||
6 | ||||
7 | pdf, pdf | |||
8 | ||||
9 | ||||
10 | ||||
11 | ||||
12 | ||||
13 | ||||
14 | ||||
15 | pdf, pdf | |||
16 | ||||
17 | ||||
18 | ||||
19 | ||||
20 | ||||
21 | ||||
22 | ||||
23 | ||||
24 | ||||
25 | ||||
26 | ||||
27 | ||||
28 | Revisão para a prova 2 | pdf, gabarito-parcial | ||
29 | Prova 2 | |||
Revisão de menção final |
Quadro de Notas
Atividades complementares
As atividades complementares somam um total de 25 pontos.
Matrícula | 1(1) | 2(2) | 3(2) | 4(2) | 5(2) | 6(2) | 7(2) | 8(2) | 9(2) | 10(2) | 11(3) | 12(3) | Total(25) | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 130102482 | 1.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 11.0 | ||||||
2 | 130143081 | 0.0 | ||||||||||||
3 | 160034078 | 1.0 | 1.5 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 3.0 | 17.5 | |||
4 | 170110940 | 1.5 | 2.0 | 3.5 | ||||||||||
5 | 180020439 | 1.5 | 1.5 | |||||||||||
6 | 180047906 | 0.0 | ||||||||||||
7 | 190025671 | 1.0 | 2.0 | 2.0 | 2.0 | 2.0 | 0.5 | 2.0 | 2.0 | 2.0 | 1.0 | 16.5 | ||
8 | 190030526 | 2.0 | 2.0 | 2.0 | 0.5 | 2.0 | 8.5 | |||||||
9 | 211020885 | 1.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 1.5 | 1.0 | 2.0 | 15.5 | |||
10 | 211055281 | 1.0 | 2.0 | 1.5 | 2.0 | 1.5 | 2.0 | 2.0 | 2.0 | 14.0 | ||||
11 | 211055316 | 1.0 | 2.0 | 2.0 | 5.0 | |||||||||
12 | 211055540 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 0.5 | 2.0 | 12.5 | |||||
13 | 211068350 | 1.0 | 2.0 | 2.0 | 2.0 | 1.0 | 2.0 | 1.5 | 2.0 | 2.0 | 2.0 | 3.0 | 2.0 | 22.5 |
14 | 221006324 | 0.7 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 1.0 | 2.0 | 2.0 | 2.0 | 17.7 | ||
15 | 221006342 | 1.5 | 2.0 | 3.5 | ||||||||||
16 | 221007223 | 0.9 | 2.0 | 2.0 | 1.0 | 2.0 | 2.0 | 1.0 | 2.0 | 2.0 | 2.0 | 3.0 | 1.5 | 21.4 |
17 | 221017032 | 0.9 | 1.5 | 2.0 | 2.0 | 2.0 | 8.4 | |||||||
18 | 221020889 | 1.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 3.0 | 20.0 | ||
19 | 221022239 | 1.0 | 2.0 | 1.5 | 2.0 | 2.0 | 2.0 | 2.0 | 0.5 | 2.0 | 2.0 | 3.0 | 2.0 | 22.0 |
20 | 221029310 | 0.5 | 0.5 | |||||||||||
21 | 222001369 | 1.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 1.0 | 2.0 | 2.0 | 2.0 | 3.0 | 1.0 | 22.0 |
22 | 222007086 | 0.8 | 2.0 | 1.0 | 2.0 | 5.8 | ||||||||
23 | 222011570 | 0.0 | ||||||||||||
24 | 222014062 | 1.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 11.0 | ||||||
25 | 222032982 | 2.0 | 2.0 | |||||||||||
26 | 222035741 | 2.0 | 1.0 | 2.0 | 2.0 | 3.0 | 10.0 | |||||||
27 | 231003362 | 0.0 | ||||||||||||
28 | 231018900 | 1.0 | 2.0 | 2.0 | 2.0 | 2.0 | 9.0 | |||||||
29 | 231018973 | 1.0 | 2.0 | 2.0 | 2.0 | 1.5 | 1.5 | 2.0 | 12.0 | |||||
30 | 231037048 | 1.0 | 2.0 | 3.0 | 6.0 | |||||||||
31 | 232003008 | 1.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 2.0 | 1.0 | 2.0 | 2.0 | 3.0 | 3.0 | 24.0 |
32 | 232012956 | 1.0 | 0.0 | 2.0 | 1.0 | 0.0 | 1.0 | 5.0 | ||||||
33 | 232013031 | 1.0 | 2.0 | 1.0 | 2.0 | 2.0 | 2.0 | 1.0 | 1.0 | 2.0 | 2.0 | 3.0 | 3.0 | 22.0 |
34 | 232036466 | 0.6 | 2.0 | 1.5 | 1.5 | 2.0 | 2.0 | 1.0 | 2.0 | 12.6 | ||||
35 | 232036896 | 1.0 | 2.0 | 2.0 | 2.0 | 2.0 | 1.0 | 2.0 | 2.0 | 14.0 |
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 | 130102482 | 0.5 | |
2 | 130143081 | ||
3 | 160034078 | 10.0 | 10.0 |
4 | 170110940 | 4.5 | 7.5 |
5 | 180020439 | 3.5 | |
6 | 180047906 | ||
7 | 190025671 | 3.0 | 7.0 |
8 | 190030526 | 3.0 | |
9 | 211020885 | 8.5 | 7.0 |
10 | 211055281 | 7.5 | 8.0 |
11 | 211055316 | 8.5 | 5.0 |
12 | 211055540 | 3.5 | 6.0 |
13 | 211068350 | 8.0 | 9.0 |
14 | 221006324 | 7.0 | 8.0 |
15 | 221006342 | ||
16 | 221007223 | 3.5 | 5.5 |
17 | 221017032 | 8.0 | 8.5 |
18 | 221020889 | 9.0 | 10.0 |
19 | 221022239 | 7.5 | 7.5 |
20 | 221029310 | 3.5 | 5.0 |
21 | 222001369 | 10.0 | 7.5 |
22 | 222007086 | 7.5 | 3.0 |
23 | 222011570 | 4.5 | 5.0 |
24 | 222014062 | 10.0 | 3.0 |
25 | 222032982 | 6.5 | 8.5 |
26 | 222035741 | 5.0 | 5.5 |
27 | 231003362 | 7.5 | 10.0 |
28 | 231018900 | 6.0 | 4.5 |
29 | 231018973 | 7.5 | 9.5 |
30 | 231037048 | 3.0 | 9.0 |
31 | 232003008 | 10.0 | 9.5 |
32 | 232012956 | 6.5 | 3.0 |
33 | 232013031 | 9.5 | 9.5 |
34 | 232036466 | 6.0 | 5.0 |
35 | 232036896 | 7.5 | 6.0 |
Tabela de menções
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.
Matrícula | Prova 1(50) | Prova 2(50) | Total Provas (>=45) | AC(25) | Total Final (>=50) | Menção | |
---|---|---|---|---|---|---|---|
1 | 130102482 | 2.5 | 0.0 | 2.5 | 11.0 | 2.5 | SR |
2 | 130143081 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | SR |
3 | 160034078 | 50.0 | 50.0 | 100.0 | 17.5 | 117.5 | SS |
4 | 170110940 | 22.5 | 37.5 | 60.0 | 3.5 | 63.5 | MM |
5 | 180020439 | 17.5 | 0.0 | 17.5 | 1.5 | 17.5 | SR |
6 | 180047906 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | SR |
7 | 190025671 | 15.0 | 35.0 | 50.0 | 16.5 | 66.5 | MM |
8 | 190030526 | 15.0 | 0.0 | 15.0 | 8.5 | 15.0 | II |
9 | 211020885 | 42.5 | 35.0 | 77.5 | 15.5 | 93.0 | SS |
10 | 211055281 | 37.5 | 40.0 | 77.5 | 14.0 | 91.5 | SS |
11 | 211055316 | 42.5 | 25.0 | 67.5 | 5.0 | 72.5 | MS |
12 | 211055540 | 17.5 | 30.0 | 47.5 | 12.5 | 60.0 | MM |
13 | 211068350 | 40.0 | 45.0 | 85.0 | 22.5 | 107.5 | SS |
14 | 221006324 | 35.0 | 40.0 | 75.0 | 17.7 | 92.7 | SS |
15 | 221006342 | 0.0 | 0.0 | 0.0 | 3.5 | 0.0 | SR |
16 | 221007223 | 17.5 | 27.5 | 45.0 | 21.4 | 66.4 | MM |
17 | 221017032 | 40.0 | 42.5 | 82.5 | 8.4 | 90.9 | SS |
18 | 221020889 | 45.0 | 50.0 | 95.0 | 20.0 | 115.0 | SS |
19 | 221022239 | 37.5 | 37.5 | 75.0 | 22.0 | 97.0 | SS |
20 | 221029310 | 17.5 | 25.0 | 42.5 | 0.5 | 42.5 | MI |
21 | 222001369 | 50.0 | 37.5 | 87.5 | 22.0 | 109.5 | SS |
22 | 222007086 | 37.5 | 15.0 | 52.5 | 5.8 | 58.3 | MM |
23 | 222011570 | 22.5 | 25.0 | 47.5 | 0.0 | 47.5 | MI |
24 | 222014062 | 50.0 | 15.0 | 65.0 | 11.0 | 76.0 | MS |
25 | 222032982 | 32.5 | 42.5 | 75.0 | 2.0 | 77.0 | MS |
26 | 222035741 | 25.0 | 27.5 | 52.5 | 10.0 | 62.5 | MM |
27 | 231003362 | 37.5 | 50.0 | 87.5 | 0.0 | 87.5 | MS |
28 | 231018900 | 30.0 | 22.5 | 52.5 | 9.0 | 61.5 | MM |
29 | 231018973 | 37.5 | 47.5 | 85.0 | 12.0 | 97.0 | SS |
30 | 231037048 | 15.0 | 45.0 | 60.0 | 6.0 | 66.0 | MM |
31 | 232003008 | 50.0 | 47.5 | 97.5 | 24.0 | 121.5 | SS |
32 | 232012956 | 32.5 | 15.0 | 47.5 | 5.0 | 52.5 | MM |
33 | 232013031 | 47.5 | 47.5 | 95.0 | 22.0 | 117.0 | SS |
34 | 232036466 | 30.0 | 25.0 | 55.0 | 12.6 | 67.6 | MM |
35 | 232036896 | 37.5 | 30.0 | 67.5 | 14.0 | 81.5 | MS |