Flávio L. C. de Moura

Home / Research / Events / Teaching (Portuguese)

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

Plano de Ensino

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:

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

Avaliação

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:

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 [2025-03-24 Mon]   Introdução e motivação pdf
2 [2025-03-26 Wed] 1 (1 ponto) Exercícios pdf, coq
3 [2025-03-31 Mon]   Correção de algoritmos pdf, pdf
4 [2025-04-02 Wed] 2 (2 pontos) Notação assintótica  
5 [2025-04-07 Mon]   A complexidade de algoritmos  
6 [2025-04-09 Wed] 3 (2 pontos) Exercícios  
7 [2025-04-14 Mon]   Equações de recorrência  
8 [2025-04-16 Wed] 4 (2 pontos) Exercícios  
--- [2025-04-21 Mon]   Feriado  
9 [2025-04-23 Wed] 5 (2 pontos) Merge sort  
10 [2025-04-28 Mon]   Teorema Mestre (parte 1)  
11 [2025-04-30 Wed] 6 (2 pontos) Teorema Mestre (parte 2)  
12 [2025-05-05 Mon]   Exercícios  
13 [2025-05-07 Wed] 7 (2 pontos) Quicksort  
14 [2025-05-12 Mon]   Exercícios  
15 [2025-05-14 Wed] 8 (2 pontos) Heapsort  
16 [2025-05-19 Mon]   Exercícios  
17 [2025-05-21 Wed] 9 (2 pontos) Prova 1  
18 [2025-05-26 Mon]   Ordenação em tempo linear  
19 [2025-05-28 Wed] 10 (2 pontos) Exercícios  
20 [2025-06-02 Mon]   Programação Dinâmica (parte 1)  
21 [2025-06-04 Wed] 11 (2 pontos) Programação Dinâmica (parte 2)  
22 [2025-06-09 Mon]   Programação Dinâmica (parte 3)  
23 [2025-06-11 Wed] 12 (2 pontos) Algoritmos Gulosos (parte 1)  
24 [2025-06-16 Mon]   Algoritmos Gulosos (parte 2)  
25 [2025-06-18 Wed] 13 (2 pontos) Exercícios  
26 [2025-06-23 Mon]   NP-completude - A classe P  
27 [2025-06-25 Wed]   NP-completude - A classe NP  
28 [2025-06-30 Mon]   NP-completude - A classe NPC  
29 [2025-07-02 Wed]   NP-completude - Problemas NP-completos (parte 1)  
30 [2025-07-07 Mon]   NP-completude - Problemas NP-completos (parte 2)  
31 [2025-07-09 Wed]   NP-completude - Problemas NP-completos (parte 3)  
32 [2025-07-14 Mon]   Revisão para a prova 2  
33 [2025-07-16 Wed]   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        

Author: Flávio L. C. de Moura

Email: flaviomoura@unb.br

Created: 2025-04-01 Tue 09:33