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 | Correção de algoritmos | pdf, pdf | ||
4 | 2 (2 pontos) | Notação assintótica | ||
5 | A complexidade de algoritmos | |||
6 | 3 (2 pontos) | Exercícios | ||
7 | Equações de recorrência | |||
8 | 4 (2 pontos) | Exercícios | ||
--- | Feriado | |||
9 | 5 (2 pontos) | Merge sort | ||
10 | Teorema Mestre (parte 1) | |||
11 | 6 (2 pontos) | Teorema Mestre (parte 2) | ||
12 | Exercícios | |||
13 | 7 (2 pontos) | Quicksort | ||
14 | Exercícios | |||
15 | 8 (2 pontos) | Heapsort | ||
16 | Exercícios | |||
17 | 9 (2 pontos) | Prova 1 | ||
18 | Ordenação em tempo linear | |||
19 | 10 (2 pontos) | Exercícios | ||
20 | Programação Dinâmica (parte 1) | |||
21 | 11 (2 pontos) | Programação Dinâmica (parte 2) | ||
22 | Programação Dinâmica (parte 3) | |||
23 | 12 (2 pontos) | Algoritmos Gulosos (parte 1) | ||
24 | Algoritmos Gulosos (parte 2) | |||
25 | 13 (2 pontos) | Exercícios | ||
26 | NP-completude - A classe P | |||
27 | NP-completude - A classe NP | |||
28 | NP-completude - A classe NPC | |||
29 | NP-completude - Problemas NP-completos (parte 1) | |||
30 | NP-completude - Problemas NP-completos (parte 2) | |||
31 | NP-completude - Problemas NP-completos (parte 3) | |||
32 | Revisão para a prova 2 | |||
33 | Prova 2 | |||
Revisão de menção final |
Quadro de Notas
AC | Matrícula | 1(1) | 2(2) | 3(2) | 4(2) | 5(2) | 6(2) | 7(2) | 8(2) | 9(2) | 10(2) | 11(2) | 12(2) | 13(2) | Total (25) |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 130102482 | ||||||||||||||
2 | 130143081 | ||||||||||||||
3 | 160034078 | ||||||||||||||
4 | 160135974 | ||||||||||||||
5 | 170070794 | ||||||||||||||
6 | 170110940 | ||||||||||||||
7 | 180020439 | ||||||||||||||
8 | 180079239 | ||||||||||||||
9 | 190025671 | ||||||||||||||
10 | 190030526 | ||||||||||||||
11 | 190100087 | ||||||||||||||
12 | 190125616 | ||||||||||||||
13 | 200062875 | ||||||||||||||
14 | 202037622 | ||||||||||||||
15 | 211020885 | ||||||||||||||
16 | 211055281 | ||||||||||||||
17 | 211055540 | ||||||||||||||
18 | 211060586 | ||||||||||||||
19 | 211068350 | ||||||||||||||
20 | 221002011 | ||||||||||||||
21 | 221006324 | ||||||||||||||
22 | 221017032 | ||||||||||||||
23 | 221017130 | ||||||||||||||
24 | 221020889 | ||||||||||||||
25 | 221022239 | ||||||||||||||
26 | 221029310 | ||||||||||||||
27 | 221031120 | ||||||||||||||
28 | 221037376 | ||||||||||||||
29 | 221038364 | ||||||||||||||
30 | 222001369 | ||||||||||||||
31 | 222007086 | ||||||||||||||
32 | 222008252 | ||||||||||||||
33 | 222011570 | ||||||||||||||
34 | 222011623 | ||||||||||||||
35 | 222014062 | ||||||||||||||
36 | 222029172 | ||||||||||||||
37 | 222032982 | ||||||||||||||
38 | 222035741 | ||||||||||||||
39 | 231003362 | ||||||||||||||
40 | 231006186 | ||||||||||||||
41 | 231011650 | ||||||||||||||
42 | 231018900 | ||||||||||||||
43 | 231018973 | ||||||||||||||
44 | 232003008 | ||||||||||||||
45 | 232009549 | ||||||||||||||
46 | 232012956 | ||||||||||||||
47 | 232013031 | ||||||||||||||
48 | 232027411 | ||||||||||||||
49 | 232036466 | ||||||||||||||
50 | 232036958 |
Matrícula | Prova 1(50) | Prova 2(50) | Total Provas (100) | |
---|---|---|---|---|
1 | 130102482 | |||
2 | 130143081 | |||
3 | 160034078 | |||
4 | 160135974 | |||
5 | 170070794 | |||
6 | 170110940 | |||
7 | 180020439 | |||
8 | 180079239 | |||
9 | 190025671 | |||
10 | 190030526 | |||
11 | 190100087 | |||
12 | 190125616 | |||
13 | 200062875 | |||
14 | 202037622 | |||
15 | 211020885 | |||
16 | 211055281 | |||
17 | 211055540 | |||
18 | 211060586 | |||
19 | 211068350 | |||
20 | 221002011 | |||
21 | 221006324 | |||
22 | 221017032 | |||
23 | 221017130 | |||
24 | 221020889 | |||
25 | 221022239 | |||
26 | 221029310 | |||
27 | 221031120 | |||
28 | 221037376 | |||
29 | 221038364 | |||
30 | 222001369 | |||
31 | 222007086 | |||
32 | 222008252 | |||
33 | 222011570 | |||
34 | 222011623 | |||
35 | 222014062 | |||
36 | 222029172 | |||
37 | 222032982 | |||
38 | 222035741 | |||
39 | 231003362 | |||
40 | 231006186 | |||
41 | 231011650 | |||
42 | 231018900 | |||
43 | 231018973 | |||
44 | 232003008 | |||
45 | 232009549 | |||
46 | 232012956 | |||
47 | 232013031 | |||
48 | 232027411 | |||
49 | 232036466 | |||
50 | 232036958 |
Matrícula | Total Provas (>= 45) | AC(25) | Total (100) | Menção | |
---|---|---|---|---|---|
1 | 130102482 | ||||
2 | 130143081 | ||||
3 | 160034078 | ||||
4 | 160135974 | ||||
5 | 170070794 | ||||
6 | 170110940 | ||||
7 | 180020439 | ||||
8 | 180079239 | ||||
9 | 190025671 | ||||
10 | 190030526 | ||||
11 | 190100087 | ||||
12 | 190125616 | ||||
13 | 200062875 | ||||
14 | 202037622 | ||||
15 | 211020885 | ||||
16 | 211055281 | ||||
17 | 211055540 | ||||
18 | 211060586 | ||||
19 | 211068350 | ||||
20 | 221002011 | ||||
21 | 221006324 | ||||
22 | 221017032 | ||||
23 | 221017130 | ||||
24 | 221020889 | ||||
25 | 221022239 | ||||
26 | 221029310 | ||||
27 | 221031120 | ||||
28 | 221037376 | ||||
29 | 221038364 | ||||
30 | 222001369 | ||||
31 | 222007086 | ||||
32 | 222008252 | ||||
33 | 222011570 | ||||
34 | 222011623 | ||||
35 | 222014062 | ||||
36 | 222029172 | ||||
37 | 222032982 | ||||
38 | 222035741 | ||||
39 | 231003362 | ||||
40 | 231006186 | ||||
41 | 231011650 | ||||
42 | 231018900 | ||||
43 | 231018973 | ||||
44 | 232003008 | ||||
45 | 232009549 | ||||
46 | 232012956 | ||||
47 | 232013031 | ||||
48 | 232027411 | ||||
49 | 232036466 | ||||
50 | 232036958 |