Projeto e Análise de Algoritmos (2021-2)

Table of Contents

Plano de Ensino

pdf

Calendário Acadêmico

Cronograma de aulas

DONE Aula 01 - Introdução e motivação

<2022-01-18 ter 19:00>

Material da aula:

DONE Aula 02 - Ordenação por inserção

<2022-01-20 qui 19:00>

Material da aula:

  • Leitura: Capítulos 1 e 2 (Seções 2.1 e 2.2), cite:cormenIntroductionAlgorithmsThird2009

DONE Aula 03 - Ordenação por inserção recursivo

<2022-01-25 ter 19:00>

Material da aula:

  • Leitura: páginas 36-62 das notas de aula (pdf)
  • Gabarito da atividade de frequência (pdf)

DONE Aula 04 - Formalização em Coq da ordenação por inserção

<2022-01-27 qui 19:00>

Material da aula:

DONE Aula 05 - Formalização da ordenação por inserção

<2022-02-01 ter 19:00>

Material da aula:

DONE Aula 06 - Formalização da ordenação por inserção

<2022-02-03 qui 19:00>

Material da aula:

DONE Aula 07 - Complexidade da ordenação por inserção em Coq

<2022-02-08 ter 19:00>

Material da aula:

DONE Aula 08 - Notação assintótica

<2022-02-10 qui 19:00>

Material da aula:

  • Notação assintótica (pdf)
  • Gabarito da atividade de frequência (pdf)

DONE Aula 09 - Equivalência entre noções de permutação

<2022-02-15 ter 19:00>

Material da aula:

  • Gabarito da atividade de frequência (pdf)

DONE Aula 10 - O algoritmo mergesort

<2022-02-17 qui 19:00>

Material da aula:

  • A correção do algoritmo mergesort (pdf)
  • Seções 4.3 e 4.4, cite:cormenIntroductionAlgorithmsThird2009
  • Gabarito da atividade de frequência (pdf)

DONE Aula 11 - Equações de recorrência

<2022-02-22 ter 19:00>

Material da aula:

  • Leitura: O teorema mestre (pdf)
  • Lista de exercícios (pdf)
  • Anotações de aula (pdf)
  • Gabarito da atividade de frequência (pdf)

DONE Aula 12 - O Teorema Mestre

<2022-02-24 qui 19:00>

Material da aula:

  • Gabarito da atividade de frequência (pdf)

Carnaval

<2022-03-01 ter>

DONE Aula 13 - Apresentação do projeto

<2022-03-03 qui 19:00>

Material da aula:

  • Gabarito da atividade de frequência (pdf)

DONE Aula 14 - Heapsort

<2022-03-08 ter 19:00>

Material da aula:

  • Leituras: pdf, Capítulo 6 cite:cormenIntroductionAlgorithmsThird2009
  • Gabarito da atividade de frequência (pdf)
  • Gabarito da atividade 03 (pdf)

DONE Aula 15 - Quicksort

<2022-03-10 qui 19:00>

Material da aula:

  • Leituras: pdf, Capítulo 7 cite:cormenIntroductionAlgorithmsThird2009
  • Gabarito da atividade de frequência (pdf)

DONE Aula 16 - Ordenação em tempo linear

<2022-03-15 ter 19:00>

Material da aula:

  • Leituras: pdf, Capítulo 8 cite:cormenIntroductionAlgorithmsThird2009
  • Gabarito da atividade de frequência (pdf)

DONE Aula 17 - Programação dinâmica

<2022-03-17 qui 19:00>

Material da aula:

  • Leituras: pdf, Capítulo 15 cite:cormenIntroductionAlgorithmsThird2009
  • Gabarito da atividade 04 (pdf)

DONE Aula 18 - Discussão sobre o projeto

<2022-03-22 ter 19:00>

Material da aula:

DONE Aula 19 - Busca em Largura - BFS

<2022-03-24 qui 19:00>

Material da aula:

  • Leituras: pdf, Seções 22.1 e 22.2 cite:cormenIntroductionAlgorithmsThird2009
  • Gabarito da atividade 05 (pdf)

DONE Aula 20 - Busca em Profundidade - DFS

<2022-03-29 ter 19:00>

Material da aula:

  • Leituras: pdf, Seção 22.3 cite:cormenIntroductionAlgorithmsThird2009
  • Gabarito da atividade 06 (pdf)

DONE Aula 21 - Componentes fortemente conexas

<2022-03-31 qui 19:00>

Material da aula:

  • Leitura: pdf, Seção 22.5 cite:cormenIntroductionAlgorithmsThird2009

DONE Aula 22 - Árvores geradoras mínimas

<2022-04-05 ter 19:00>

Material da aula:

  • Leituras: pdf, Capítulo 23 cite:cormenIntroductionAlgorithmsThird2009

Aula 23 - Aula cancelada

<2022-04-07 qui 19:00>

DONE Aula 24 - Caminhos Mínimos

<2022-04-12 ter 19:00>

Material da aula:

  • Leituras: pdf, Capítulo 24 cite:cormenIntroductionAlgorithmsThird2009
  • Gabarito da atividade 07 (pdf)

DONE Aula 25 - NP-completude: A classe P

<2022-04-14 qui 19:00>

Material da aula:

  • Leitura: pdf, Capítulo 34 cite:cormenIntroductionAlgorithmsThird2009

DONE Aula 26 - As classes NP e NPC

<2022-04-19 ter 19:00>

Material da aula:

  • Leitura: pdf, Capítulo 34 cite:cormenIntroductionAlgorithmsThird2009

Feriado de Tiradentes

<2022-04-21 qui>

DONE Aula 27 - Problemas NP-completos

<2022-04-26 ter 19:00>

TODO Aula 28 - Mais problemas NP-completos

<2022-04-28 qui 19:00>

TODO Aula 29 -

<2022-05-03 ter 19:00>

TODO Aula 30 -

<2022-05-05 qui 19:00>

Quadro de frequência

Matrícula 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 faltas faltas(%)
130107590 x x x           x x     x x x x x x x x x x x x x x x x x x 7 23.3
130112267 x x x   x x x   x x x x x x x x x x x x x x x x x x x x x x 2 6.7
130143081                                                             30 100.0
150005491                                                             30 100.0
150140801 x   x x x x     x                                           24 80.0
160052289 x x                                                         28 93.3
160139180 x x x     x         x                                       25 83.3
170004601 x   x                                                       28 93.3
170040631 x x x x x x x x x x   x x   x x x x x x x x x x x x x x x x 2 6.7
170043827 x x x   x x x x x x x   x x x x x x x x x x x x x x x x x x 2 6.7
170043959 x x x   x             x x x x x x x x x x x x x x x x x x x 7 23.3
170045919 x x x   x x   x x     x x   x x x x x x x x x x x x x x x x 5 16.7
170061001 x x x   x x     x x   x       x x x x x x x x x x x x x x x 7 23.3
170079538   x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 1 3.3
170112624     x   x x     x                                           26 86.7
170114988 x x x   x x x x x x   x x x x x x x x x x x x x x x x x x x 2 6.7
170137058 x x x   x x x x x x x x x x x x x x x x x x x x x x x x x x 1 3.3
170138585 x       x                                                   28 93.3
170144631 x x x     x x x x x x x x x x x x x x x x x x x x x x x x x 2 6.7
170146804             x   x x x   x x x x                             22 73.3
170149374 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 0 0.0
170152294   x x                                                       28 93.3
170153959 x       x   x   x x x x x x x x x x x x x x x x x x x x x x 5 16.7
170157849 x x x   x     x x x x x x x x x x x x x x x x x x x x x x x 3 10.0
180019279 x x x x x x x x x x   x x x x x x x x x x x x x x x x x x x 1 3.3
180029274 x x x   x x                                                 25 83.3
180030329 x x x   x   x x x x x x x x x x x x x x x x x x x x x x x x 2 6.7
180034235   x x x x x x x x x x x x   x x x x x x x x x x x x x x x x 2 6.7
180043358 x   x                                                       28 93.3
180100700                                                             30 100.0
180108531 x x     x x                                                 26 86.7
180112333                                                             30 100.0
180122975                                                             30 100.0
180123301   x   x     x                                               27 90.0
180129040 x                                                           29 96.7
180132199 x x x x x x x x x x x x x   x x x x x x x x x x x x x x x x 1 3.3
180157418 x x x   x x x x x x x   x x x x x x x x x x x x x x x x x x 2 6.7
190014172 x x x   x x   x x x x x x x x x x x x x x x x x x x x x x x 2 6.7
190019611 x x x   x x x x x x x   x x x x x x x x x x x x x x x x x x 2 6.7
190019760     x x x x x     x   x x x x x x x x x x x x x x x x x x x 5 16.7
190023210                                                             30 100.0
190023546 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 0 0.0
190025930 x x x     x x x x x x x x   x x x x x x x x x x x x x x x x 3 10.0
190033240 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 0 0.0
190035072   x x   x x x x x   x   x   x x x x x x x x x x x x x x x x 5 16.7
190038489 x x x   x x   x         x x x x x x x x x x x x x x x x x x 6 20.0
190046953 x x                                                         28 93.3
190047101 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 0 0.0
190059273 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 0 0.0
190084502 x x x   x x x x x x     x x x x x x x x x x x x x x x x x x 3 10.0
190097621                                                             30 100.0
190099160 x   x x x   x x x x x   x x x x x x x x x x x x x x x x x x 3 10.0
190108274 x   x                                                       28 93.3
190110007 x x x   x     x x           x x                             22 73.3
190127465 x x x   x x x x x x   x x x x x x x x x x x x x x x x x x x 2 6.7
202042767                                                             30 100.0

Quadros de Notas

Atividades

Matrícula 01(4) 02(2) 03(8) 04(8) 05(8) 06(8) 07(8) 08(8) 09(8) 10(8) Total (70)
130107590     6 6 8 7 7   8 8 50
130112267 4 2 4 4 4 6 8 3 3 4 42
130143081                     0
150005491                     0
150140801                     0
160052289                     0
160139180 1                   1
170004601 4 2                 6
170040631 4 2 5 8 8 5 8 8 8 8 64
170043827 4 2 7 5 8           26
170043959 4 2 5 6 8 6 8 8 8 8 63
170045919 4 2 5 6 8 6 8 8 8 8 63
170061001 4 2 6 6 8 4   6 8 8 52
170079538 4 2 4 3 4 4 6   5 8 40
170112624 4 2                 6
170114988 4 2 4 3 7 8 8 6 5 4 51
170137058 4 2 7 4 4 4 8 8 3   44
170138585                     0
170144631 4 2 8 3   6         23
170146804 3 2 4 4             13
170149374 4 2 8 8 8 6 8 8 8 8 68
170152294                     0
170153959 4 2 5   8   8 8 8   43
170157849 4 2 4 8 4 8 7 6 2 5 50
180019279 4 2 7 5 4   7 8 8 8 53
180029274 4 2                 6
180030329 3 2 6 8 8 4 5 8 8   52
180034235 4 2 5 5 7 7 7 5 4   46
180043358                     0
180100700                     0
180108531 3 2                 5
180112333 1                   1
180122975                     0
180123301 4 2                 6
180129040                     0
180132199 4 2 6 8 4 4 8   7   43
180157418 3 2 5 4 4 8 6 6 1   39
190014172 1   4 1             6
190019611 1   7 7 7 5 6 2     35
190019760 4 2 7 4 5 6 5     8 41
190023210 3 2                 5
190023546 4 2 4 4 7 4 5 6 3 5 44
190025930 4 2 8 5   4 8 8 8 6 53
190033240 4 2 4 4 7 4 6 3 7 8 49
190035072 4 2   6 8 4     5   29
190038489     6 7 4 4 6 2     29
190046953                     0
190047101 4 2 7 6 4 5 8 8 8   52
190059273 4 2 5 5 6 4 5 5 5 4 45
190084502 4 2 7 4 8 4 5 3 4 4 45
190097621                     0
190099160 4 2 5 4 8 4 7 2 4 4 44
190108274                     0
190110007 4 2 2               8
190127465 4 2 3 4 8   8 8 8   45
202042767                     0

Projeto

Matrícula Provas(20) Relatório(10) Desafio Total (30)
130107590       0
130112267 15 5   20
130143081       0
150005491       0
150140801       0
160052289       0
160139180       0
170004601       0
170040631 20 9   29
170043827     10 10
170043959 20 9   29
170045919 20 9   29
170061001 20 9   29
170079538 15 8   23
170112624       0
170114988 15 8   23
170137058     10 10
170138585       0
170144631       0
170146804       0
170149374 18 7   25
170152294       0
170153959 15 8   23
170157849 15 6   21
180019279 20 8   28
180029274       0
180030329 5     5
180034235 15 5   20
180043358       0
180100700       0
180108531       0
180112333       0
180122975       0
180123301       0
180129040       0
180132199 18 7   25
180157418       0
190014172       0
190019611       0
190019760 20 7   27
190023210       0
190023546 15 6   21
190025930 15 6   21
190033240 15 6   21
190035072 20 7   27
190038489       0
190046953       0
190047101 20 7   27
190059273 15 5   20
190084502 20 8   28
190097621       0
190099160     10 10
190108274       0
190110007       0
190127465 20 8   28
202042767       0

Notas

Matrícula Atividades Projeto Total (100) Faltas(%) Menção
130107590 50.0 0.0 50.0 23.2 MM
130112267 42.0 20.0 62.0 6.7 MM
130143081 0.0 0.0 0.0 100.0 SR
170040631 64.0 29.0 93.0 6.7 SS
170043959 63.0 29.0 92.0 23.3 SS
170045919 63.0 29.0 92.0 16.7 SS
170061001 52.0 29.0 81.0 23.3 MS
170079538 40.0 23.0 63.0 3.3 MM
170114988 51.0 23.0 74.0 6.7 MS
170137058 44.0 10.0 54.0 3.3 MM
170138585 0.0 0.0 0.0 93.3 SR
170144631 23.0 0.0 23.0 6.7 II
170149374 68.0 25.0 93.0 0.0 SS
170153959 43.0 23.0 66.0 16.7 MM
170157849 50.0 21.0 71.0 10.0 MS
180019279 53.0 28.0 81.0 3.3 MS
180030329 52.0 5.0 57.0 6.7 MM
180034235 46.0 20.0 66.0 6.7 MM
180132199 43.0 25.0 68.0 3.3 MM
180157418 39.0 0.0 39.0 6.7 MI
190019760 41.0 27.0 68.0 16.7 MM
190023546 44.0 21.0 65.0 0.0 MM
190025930 53.0 21.0 74.0 10.0 MS
190033240 49.0 21.0 70.0 0.0 MS
190035072 29.0 27.0 56.0 16.7 MM
190047101 52.0 27.0 79.0 0.0 MS
190059273 45.0 20.0 65.0 0.0 MM
190084502 45.0 28.0 73.0 10.0 MS
190097621 0.0 0.0 0.0 100.0 SR
190099160 44.0 10.0 54.0 10.0 MM
190108274 0.0 0.0 0.0 93.3 SR
190127465 45.0 28.0 73.0 6.7 MS