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

Table of Contents

1. Plano de Ensino

2. Calendário SAA

3. Cronograma de Aulas

3.1. DONE Aula 01 - Introdução e motivação <2023-03-28 ter 19:00>

3.1.1. Material da aula:

  1. pdf
  2. Arquivo Coq (elementomaximo.v)
  3. Orientações para gerar um pdf a partir do seu arquivo do Coq: link

3.2. DONE Aula 02 - A correção de algoritmos <2023-03-30 qui 19:00>

3.2.1. Resumo da aula (pdf)

3.3. DONE Aula 03 - A correção do algoritmo do elemento máximo <2023-04-04 ter 19:00>

3.4. DONE Aula 04 - A correção do algoritmo do elemento máximo em Coq <2023-04-06 qui 19:00>

3.4.1. Material da aula (pdf)

3.5. DONE Aula 05 - A complexidade de algoritmos <2023-04-11 ter 19:00>

3.5.1. Material da aula (pdf)

3.5.2. Apresentação da primeira atividade em Coq: Completar a formalização da correção do algoritmo que retorna o maior elemento de uma lista.

  • Prazo [2023-04-30 dom].
  • Link para criação dos grupos (a serem utilizados durante todo o semestre): GitHub classroom
  • Pontuação: 5 pontos (parte dos 30 pontos destinados ao projeto)
  • Descrição (pdf)

3.6. DONE Aula 06 - Notação assintótica <2023-04-13 qui 19:00>

3.7. DONE Aula 07 - A correção de algoritmos recursivos <2023-04-18 ter 19:00>

3.8. DONE Aula 08 - A busca binária <2023-04-20 qui 19:00>

3.8.1. Material da aula (pdf)

3.9. DONE Aula 09 - Regra da suavização <2023-04-25 ter 19:00>

3.9.1. Resumo da aula:

  • Fizemos o gabarito da atividade 1 (pdf)
  • Apresentamos a prova de uma versão simplificada do Teorema Mestre (pdf)
  • pdf (anotações)
  • pdf (anotações)

3.10. DONE Aula 10 - O Teorema Mestre <2023-04-27 qui 19:00>

3.10.1. Material de aula

3.11. DONE Aula 11 - Equações de recorrência <2023-05-02 ter 19:00>

3.11.1. Material da aula

3.11.2. TODO Correção da atividade 3

3.12. DONE Aula 12 - Quicksort <2023-05-04 qui 19:00>

3.12.1. Material da aula

3.13. DONE Aula 13 - Heapsort <2023-05-09 ter 19:00>

3.13.1. Material da aula

3.14. DONE Aula 14 - Cota inferior para algoritmos baseados na comparação de chaves <2023-05-11 qui 19:00>

3.14.1. Material da aula:

3.15. DONE Aula 15 - Aula de exercícios <2023-05-16 ter 19:00>

3.15.1. Material da aula:

3.16. DONE Aula 16 - Avaliação escrita <2023-05-18 qui 19:00>

3.16.1. Gabarito da prova: pdf

3.17. DONE Aula 17 - Mergesort em Coq <2023-05-23 ter 19:00>

3.17.1. Material da aula:

3.18. DONE Aula 18 - Mergesort em Coq <2023-05-25 qui 19:00>

3.18.1. Nesta aula definimos a data de [2023-06-18 dom] como prazo para finalização da formalização da correção do algoritmo mergesort. O trabalho pode ser feito no mesmo grupo que foi utilizado para fazer a tarefa sobre o elemento máximo (GitHub classroom), e para isto basta incluir o arquivo coq e o relatório em formato pdf no repositório. Também é possível a reorganização em outros grupos: neste caso, envie uma mensagem pelo chat do Teams informando o link para o repositório, e o nome e matrícula dos participantes.

3.18.2. Material da aula:

3.19. DONE Aula 19 - Ordenação em tempo linear <2023-05-30 ter 19:00>

3.19.1. Material da aula:

3.20. DONE Aula 20 - Algoritmos em grafos <2023-06-01 qui 19:00>

3.20.1. Material da aula:

3.21. DONE Aula 21 - Aplicação de BFS: caminho mínimo <2023-06-06 ter 19:00>

3.22. Feriado <2023-06-08 qui 19:00>

3.23. DONE Aula 22 - Atividade BST <2023-06-13 ter 19:00>

3.23.1. Material da aula:

  • bst.v (prazo 16/07/2023)

3.24. DONE Aula 23 - Atividade BST <2023-06-15 qui 19:00>

3.25. DONE Aula 24 - Busca em profundidade <2023-06-20 ter 19:00>

3.25.1. Material da aula:

3.26. DONE Aula 25 - Atividade BST <2023-06-22 qui 19:00>

3.26.1. Material da aula:

  • pdf
  • Arquivo coq discutido durante a aula: bst.v (prazo 16/07/2023)

3.27. CANCELLED Aula cancelada <2023-06-27 ter 19:00>

3.28. DONE Aula 26 - Árvores geradoras mínimas <2023-06-29 qui 19:00>

3.28.1. Material da aula:

3.29. DONE Aula 27 - As classes P e NP <2023-07-04 ter 19:00>

3.29.1. Material da aula:

3.30. DONE Aula 28 - A classe NPC <2023-07-06 qui 19:00>

3.30.1. Material da aula:

3.31. DONE Aula 29 - Atividade BST <2023-07-11 ter 19:00>

3.31.1. Material da aula:

  • bst.v (prazo 16/07/2023)

3.32. DONE Aula 30 - Atividade BST <2023-07-13 qui 19:00>

3.32.1. Material da aula:

  • bst.v (prazo 19/07/2023). Este é o novo prazo para completar as provas apenas. O relatório não é mais necessário.

3.33. DONE Aula 31 - Aula de revisão <2023-07-18 ter 19:00>

3.34. DONE Aula 32 - Avaliação escrita <2023-07-20 qui 19:00>

3.34.1. DONE Gabarito (pdf)

4. Gabaritos

4.1. Atividade 1 (pdf)

4.2. Atividade 2 (pdf)

4.3. Atividade 3 (pdf)

4.4. Atividade 4 (pdf)

4.5. Atividade 5 (pdf)

4.6. Atividade 6 (pdf)

4.7. Atividade 7 (pdf)

4.8. Atividade 8 (pdf)

4.9. Atividade 9 (pdf)

4.10. Prova 1 (pdf)

4.11. Prova 2 (pdf)

5. Quadro de Notas

5.1. Atividades (Teams)

  Matrícula 1(2) 2(2) 3(1) 4(2) 5(2) 6(1) 7(2) 8(2) 9(2) 10(2) Total (18)
1 150140801 2   1 1 1 0.5 1.5 1 1 1 10.0
2 160125073 2 2     1 0.5         5.5
3 160137705 2       2           4.0
4 160139180                     0.0
5 170110940                     0.0
6 170112624 2 2     0.5 0.5 2     2 9.0
7 170138585                     0.0
8 180035096                     0.0
9 180043358                     0.0
10 180116207 1.5 1 0.5 1.5 1.5           6.0
11 180131699     0.5               0.5
12 190037351 1 1 0.5 2 0.5 1 2 1 2 2 13.0
13 190043318                     0.0
14 190086530 2 1 0.5 1.5   0.5 2 1.5   2 11.0
15 190094087 0.5 1.5   1 1           4.0
16 190096063 1 1.5 0.5 2 1 1   1 1.5 2 11.5
17 190098660 1 1 1               3.0
18 190105526 2 2 1 2 2 1 2 2 2 2 18.0
19 200017969                     0.0
20 200020960 2 1.5 0.6 1 1 0.5 2 2 1.5 2 14.1
21 200022610 1.5 1   0.5 1.5           4.5
22 200022857 0.5 1     2 0.5     2   6.0
23 200044494 2 2 0.7 0.5 2 1 2 1     11.2
24 200053680 2 2   1 1   2   2 2 12.0
25 200057677                     0.0
26 200060295 1 1.5 0.5 1 1.5 1 1.5 1 1 2 12.0
27 202021767 1 1 0.7 1 0.5 0.5 2 1 1.5 2 11.2
28 202033427 2 2 0.6 2 1 1 2 1.5 2 2 16.1
29 202033580 1.5 1.5     1.5 0.5 2   1.5   8.5
30 211010299 2 2 1 2 2 1 2 2 2 2 18.0
31 211036123 2 1.5 0.8 0.5 1 0.5 2 1 1 1 11.3
32 211038191 2 1 1   1 0.5 2 1.5 1.5 1.5 12.0
33 211043342 2 1   1 2 1 1 1 2   11.0
34 222011543 2 2 1 2   1 2 1.5   2 13.5

5.2. Avaliações escritas

  Matrícula 1 (20) 2 (20) Total (40)
1 150140801 8.0 14.0 22.0
2 160125073 4.0   4.0
3 160137705 8.0   8.0
4 160139180     0.0
5 170110940     0.0
6 170112624 12.0 14.0 26.0
7 170138585 4.0   4.0
8 180035096     0.0
9 180043358 2.0   2.0
10 180116207 0.0   0.0
11 180131699     0.0
12 190037351 11.0 7.0 18.0
13 190043318 4.0   4.0
14 190086530 11.0 13.0 24.0
15 190094087 1.0   1.0
16 190096063 13.0 14.0 27.0
17 190098660     0.0
18 190105526 12.0 20.0 32.0
19 200017969     0.0
20 200020960 9.0 9.0 18.0
21 200022610 6.0   6.0
22 200022857 7.0   7.0
23 200044494 13.0   13.0
24 200053680 11.0 14.0 25.0
25 200057677     0.0
26 200060295 15.0 15.0 30.0
27 202021767 11.0 12.0 23.0
28 202033427 14.0 11.0 25.0
29 202033580 13.0   13.0
30 211010299 20.0 20.0 40.0
31 211036123 12.0 19.0 31.0
32 211038191 11.0 14.0 25.0
33 211043342 7.0   7.0
34 222011543 19.0 20.0 39.0

5.3. Projeto

  Matrícula Elem Max (5) Mergesort (10) BST (15) Total (30)
1 150140801 3.5 3.0 6.0 12.5
2 160125073 5.0 9.0 12.0 26.0
3 160137705 5.0 9.0 12.0 26.0
4 160139180       0.0
5 170110940       0.0
6 170112624     9.0 9.0
7 170138585 3.5 3.0 6.0 12.5
8 180035096       0.0
9 180043358       0.0
10 180116207       0.0
11 180131699       0.0
12 190037351     11.0 11.0
13 190043318       0.0
14 190086530 5.0 7.0 10.0 22.0
15 190094087 5.0     5.0
16 190096063 5.0 7.0 10.0 22.0
17 190098660       0.0
18 190105526 5.0 10.0 15.0 30.0
19 200017969 5.0     5.0
20 200020960   7.0 10.0 17.0
21 200022610 5.0     5.0
22 200022857 5.0 6.0   11.0
23 200044494       0.0
24 200053680 5.0 9.0 12.0 26.0
25 200057677 4.0     4.0
26 200060295 5.0 10.0 15.0 30.0
27 202021767 5.0 10.0 15.0 30.0
28 202033427 5.0 8.0 7.0 20.0
29 202033580 5.0 10.0 15.0 30.0
30 211010299 5.0 10.0 15.0 30.0
31 211036123 4.0 8.0 12.0 24.0
32 211038191 5.0 9.0 13.0 27.0
33 211043342 5.0 9.0 13.0 27.0
34 222011543 5.0 7.0 10.0 22.0

5.4. Tabela de menções

  Matrícula Atividades(30) Projeto Provas Total(100) Menção
1 150140801 16.7 12.5 22.0 51.2 MM
2 160125073 9.2 26.0 4.0 39.2 MI
3 160137705 6.7 26.0 8.0 40.7 MI
4 160139180 0.0 0.0 0.0 0.0 SR
5 170110940 0.0 0.0 0.0 0.0 SR
6 170112624 15.0 9.0 26.0 50.0 MM
7 170138585 0.0 12.5 4.0 16.5 SR
8 180035096 0.0 0.0 0.0 0.0 SR
9 180043358 0.0 0.0 2.0 2.0 II
10 180116207 10.0 0.0 0.0 10.0 SR
11 180131699 0.8 0.0 0.0 0.8 SR
12 190037351 21.7 11.0 18.0 50.7 MM
13 190043318 0.0 0.0 4.0 4.0 II
14 190086530 18.3 22.0 24.0 64.3 MM
15 190094087 6.7 5.0 1.0 12.7 SR
16 190096063 19.2 22.0 27.0 68.2 MM
17 190098660 5.0 0.0 0.0 5.0 SR
18 190105526 30.0 30.0 32.0 92.0 SS
19 200017969 0.0 5.0 0.0 5.0 SR
20 200020960 23.5 17.0 18.0 58.5 MM
21 200022610 7.5 5.0 6.0 18.5 SR
22 200022857 10.0 11.0 7.0 28.0 II
23 200044494 18.7 0.0 13.0 31.7 MI
24 200053680 20.0 26.0 25.0 71.0 MS
25 200057677 0.0 4.0 0.0 4.0 SR
26 200060295 20.0 30.0 30.0 80.0 MS
27 202021767 18.7 30.0 23.0 71.7 MS
28 202033427 26.8 20.0 25.0 71.8 MS
29 202033580 14.2 30.0 13.0 57.2 MM
30 211010299 30.0 30.0 40.0 100.0 SS
31 211036123 18.8 24.0 31.0 73.8 MS
32 211038191 20.0 27.0 25.0 72.0 MS
33 211043342 18.3 27.0 7.0 52.3 MM
34 222011543 22.5 22.0 39.0 83.5 MS

Author: Flávio L. C. de Moura

Created: 2023-08-15 ter 09:39