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:

  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.

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.
  • 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.

Metodologia de ensino

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.

Avaliação

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:

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: [2025-11-13 qui 11:42]

Cronograma

Aula Data Assunto Arquivos
1 [2025-08-18 seg] Introdução e Motivação  
2 [2025-08-20 qua] A correção de algoritmos  
3 [2025-08-25 seg] Invariantes de laço  
4 [2025-08-27 qua] Notação assintótica  
5 [2025-09-01 seg] Exercícios  
6 [2025-09-03 qua] Equações de recorrência pdf
7 [2025-09-08 seg] A Torre de Hanoi hanoi.v
8 [2025-09-10 qua] O Teorema Mestre (parte 1)  
9 [2025-09-15 seg] O Teorema Mestre (parte 2)  
10 [2025-09-17 qua] O Teorema Mestre (parte 3)  
11 [2025-09-22 seg] Quicksort  
12 [2025-09-24 qua] Exercícios  
13 [2025-09-29 seg] Revisão para a Prova 1 pdf, gabarito
14 [2025-10-01 qua] Prova 1 gabarito
15 [2025-10-06 seg] Heapsort (parte 1) pdf
16 [2025-10-08 qua] Heapsort (parte 2)  
17 [2025-10-13 seg] Proposta do projeto pdf
18 [2025-10-15 qua] Ordenação em Tempo Linear  
19 [2025-10-20 seg] Programação Dinâmica (parte 1)  
20 [2025-10-22 qua] Programação Dinâmica (parte 2)  
--- [2025-10-27 seg] Ponto facultativo  
--- [2025-10-29 qua] Paralisação docente  
--- [2025-11-03 seg] Semana Universitária  
--- [2025-11-05 qua] Semana Universitária  
21 [2025-11-10 seg] NP-completude  
22 [2025-11-12 qua] NP-completude  
23 [2025-11-17 seg] NP-completude  
24 [2025-11-19 qua] NP-completude  
25 [2025-11-24 seg] NP-completude  
26 [2025-11-26 qua] NP-completude pdf
27 [2025-12-01 seg] Revisão para a Prova 2  
28 [2025-12-03 qua] Prova 2  

Quadro de Notas

Atividades complementares

  Matrícula 1(4) 2(3) 3(3) 4(3) 5(3) 6(4) Total(20)
1 170100332 4.0 3.0 0.0 0.0 3.0   10.0
2 180136780 3.0 0.0 0.0 0.0 0.0   3.0
3 190025069 3.0 2.7 0.0 3.0 3.0 4.0 15.7
4 190030526 3.0 3.0 2.5 0.0 0.0   8.5
5 190095229 0.0 0.0 0.0 0.0 0.0   0.0
6 190108665 4.0 3.0 3.0 3.0 3.0   16.0
7 200016997 0.0 0.0 0.0 0.0 0.0   0.0
8 200025937 2.0 2.2 0.0 0.0 3.0 2.0 9.2
9 200040979 3.0 0.0 3.0 3.0 3.0 2.0 14.0
10 202037622 4.0 3.0 3.0 3.0 3.0 4.0 20.0
11 202042829 3.0 2.2 0.0 3.0 0.0 4.0 12.2
12 211042701 0.0 2.2 3.0 3.0 3.0   11.2
13 211066196 4.0 3.0 3.0 3.0 3.0   16.0
14 212005220 4.0 2.7 0.0 3.0 0.0   9.7
15 221001972 4.0 3.0 3.0 3.0 3.0 4.0 20.0
16 221002049 0.0 0.0 3.0 0.0 0.0 4.0 7.0
17 221002067 3.0 2.2 0.6 1.0 0.0 4.0 10.8
18 221002100 3.0 3.0 2.0 3.0 3.0   14.0
19 221003968 4.0 3.0 0.0 3.0 3.0 4.0 17.0
20 221017023 4.0 3.0 3.0 3.0 3.0 4.0 20.0
21 221017060 4.0 3.0 3.0 0.0 3.0 1.0 14.0
22 221017079 4.0 0.0 0.0 3.0 0.0 1.5 8.5
23 221017088 4.0 3.0 3.0 3.0 0.0   13.0
24 221030007 1.0 3.0 3.0 2.0 0.0 4.0 13.0
25 221030016 3.0 2.7 2.0 3.0 0.0 4.0 14.7
26 221030034 3.0 2.2 3.0 3.0 3.0 4.0 18.2
27 221038005 4.0 2.2 0.0 3.0 2.2 1.0 12.4
28 222001387 3.0 2.7 3.0 0.0 0.0 4.0 12.7
29 222031116 3.0 3.0 3.0 3.0 0.0   12.0
30 231003380 4.0 3.0 3.0 3.0 3.0 4.0 20.0
31 231003513 4.0 2.2 3.0 3.0 0.0 4.0 16.2
32 231006239 3.0 2.2 2.5 3.0 3.0 4.0 17.7
33 231006248 0.0 0.0 0.0 0.0 0.0   0.0
34 231006257 3.0 2.2 1.0 0.0 0.0 2.0 8.2
35 231011650 3.0 2.2 2.0 0.0 3.0 1.0 11.2
36 231013529 4.0 2.2 2.5 3.0 3.0 4.0 18.7
37 231013547 4.0 3.0 3.0 3.0 3.0 4.0 20.0
38 231018884 4.0 3.0 3.0 3.0 3.0   16.0
39 231021496 3.0 2.1 3.0 3.0 3.0 4.0 18.1
40 231025190 0.0 0.0 0.0 2.0 0.0 1.0 3.0
41 231025216 3.0 2.2 3.0 3.0 0.0 2.0 13.2
42 232007830 4.0 3.0 3.0 3.0 3.0 4.0 20.0
43 232012974 0.0 3.0 3.0 0.0 0.0   6.0
44 232029274 0.0 0.0 3.0 0.0 0.0 2.0 5.0
45 242037814 3.0 2.2 3.0 3.0 3.0 4.0 18.2

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 9.0 7.5
2 180136780    
3 190025069 1.0 7.5
4 190030526 7.0 5.0
5 190095229    
6 190108665 6.0 10.0
7 200016997 1.5 1.0
8 200025937 4.0 7.0
9 200040979 4.0 5.0
10 202037622 7.0 10.0
11 202042829 4.0 0.0
12 211042701 2.0  
13 211066196 4.0 3.0
14 212005220 4.0  
15 221001972 8.0 10.0
16 221002049 2.5 9.5
17 221002067 1.0 3.0
18 221002100 10.0 10.0
19 221003968 4.5 4.5
20 221017023 9.5 10.0
21 221017060 9.0 10.0
22 221017079 1.0 2.0
23 221017088 9.5 10.0
24 221030007 10.0 9.0
25 221030016 10.0 6.5
26 221030034 7.5 3.0
27 221038005 9.0 5.5
28 222001387 7.5 3.5
29 222031116    
30 231003380 8.0 10.0
31 231003513 10.0 8.0
32 231006239 9.5 7.0
33 231006248    
34 231006257 2.0  
35 231011650 3.5 7.5
36 231013529 7.0 10.0
37 231013547 7.0 9.0
38 231018884 10.0 10.0
39 231021496 6.0 8.0
40 231025190 5.0 5.5
41 231025216 7.0 5.0
42 232007830 7.0 5.0
43 232012974 4.0  
44 232029274 6.0 8.5
45 242037814 9.5 9.5

Tabela de menções

  • O projeto (20 pontos) é uma atividade opcional.
  Matrícula Prova 1(40) Prova 2(40) AC(20) Proj(20) Total(120) Menção
1 170100332 36.0 30.0 10.0 0.0 76.0 MS
2 180136780 0.0 0.0 3.0 0.0 3.0 SR
3 190025069 4.0 30.0 15.7 15.0 64.7 MM
4 190030526 28.0 20.0 8.5 10.0 66.5 MM
5 190095229 0.0 0.0 0.0 0.0 0.0 SR
6 190108665 24.0 40.0 16.0 0.0 80.0 MS
7 200016997 6.0 4.0 0.0 0.0 10.0 II
8 200025937 16.0 28.0 9.2 0.0 53.2 MM
9 200040979 16.0 20.0 14.0 0.0 50.0 MM
10 202037622 28.0 40.0 20.0 20.0 108.0 SS
11 202042829 16.0 0.0 12.2 0.0 28.2 II
12 211042701 8.0 0.0 11.2 0.0 19.2 II
13 211066196 16.0 12.0 16.0 13.0 57.0 MM
14 212005220 16.0 0.0 9.7 0.0 25.7 II
15 221001972 32.0 40.0 20.0 15.0 107.0 SS
16 221002049 10.0 38.0 7.0 20.0 75.0 MS
17 221002067 4.0 12.0 10.8 15.0 41.8 MI
18 221002100 40.0 40.0 14.0 0.0 94.0 SS
19 221003968 18.0 18.0 17.0 10.0 63.0 MM
20 221017023 38.0 40.0 20.0 15.0 113.0 SS
21 221017060 36.0 40.0 14.0 20.0 110.0 SS
22 221017079 4.0 8.0 8.5 15.0 35.5 MI
23 221017088 38.0 40.0 13.0 0.0 91.0 SS
24 221030007 40.0 36.0 13.0 20.0 109.0 SS
25 221030016 40.0 26.0 14.7 15.0 95.7 SS
26 221030034 30.0 12.0 18.2 0.0 60.2 MM
27 221038005 36.0 22.0 12.4 0.0 70.4 MS
28 222001387 30.0 14.0 12.7 0.0 56.7 MM
29 222031116 0.0 0.0 12.0 0.0 12.0  
30 231003380 32.0 40.0 20.0 0.0 92.0 SS
31 231003513 40.0 32.0 16.2 20.0 108.2 SS
32 231006239 38.0 28.0 17.7 15.0 98.7 SS
33 231006248 0.0 0.0 0.0 0.0 0.0 SR
34 231006257 8.0 0.0 8.2 0.0 16.2 II
35 231011650 14.0 30.0 11.2 10.0 65.2 MM
36 231013529 28.0 40.0 18.7 12.0 98.7 SS
37 231013547 28.0 36.0 20.0 12.0 96.0 SS
38 231018884 40.0 40.0 16.0 0.0 96.0 SS
39 231021496 24.0 32.0 18.1 16.0 90.1 SS
40 231025190 20.0 22.0 3.0 12.0 57.0 MM
41 231025216 28.0 20.0 13.2 12.0 73.2 MS
42 232007830 28.0 20.0 20.0 15.0 83.0 MS
43 232012974 16.0 0.0 6.0 0.0 22.0 II
44 232029274 24.0 34.0 5.0 0.0 63.0 MM
45 242037814 38.0 38.0 18.2 0.0 94.2 SS

Date: \today

Author: Flávio L. C. de Moura

Email: flaviomoura@unb.br

Created: 2025-12-12 sex 00:34