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. TODO Aula 20 - Algoritmos em grafos <2023-06-01 qui 19:00>

3.20.1. Material da aula:

3.21. TODO Aula 21 - <2023-06-06 ter 19:00>

3.21.1. TODO Resumo da aula:

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

3.23. TODO Aula 22 - <2023-06-13 ter 19:00>

3.23.1. TODO Resumo da aula:

3.24. TODO Aula 23 - <2023-06-15 qui 19:00>

3.24.1. TODO Resumo da aula:

3.25. TODO Aula 24 - <2023-06-20 ter 19:00>

3.25.1. TODO Resumo da aula:

3.26. TODO Aula 25 - <2023-06-22 qui 19:00>

3.26.1. TODO Resumo da aula:

3.27. TODO Aula 26 - <2023-06-27 ter 19:00>

3.27.1. TODO Resumo da aula:

3.28. TODO Aula 27 - <2023-06-29 qui 19:00>

3.28.1. TODO Resumo da aula:

3.29. TODO Aula 28 - <2023-07-04 ter 19:00>

3.29.1. TODO Resumo da aula:

3.30. TODO Aula 29 - <2023-07-06 qui 19:00>

3.30.1. TODO Resumo da aula:

3.31. TODO Aula 30 - <2023-07-11 ter 19:00>

3.31.1. TODO Resumo da aula:

3.32. TODO Aula 31 - <2023-07-13 qui 19:00>

3.32.1. TODO Resumo da aula:

3.33. TODO Aula 32 - <2023-07-18 ter 19:00>

3.33.1. TODO Resumo da aula:

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

3.34.1. TODO Gabarito:

4. Gabaritos

4.1. Atividade 1 (pdf)

4.2. Atividade 2 (pdf)

4.3. Atividade 3 (pdf)

4.4. Atividade 4 (pdf)

4.5. Prova 1 (pdf)

5. Quadro de Notas

5.1. Atividades (Teams)

  Matrícula 1(2) 2 3 4 5 6 7 8 9 10 Total (30)
1 150140801 2                   2.0
2 160125073 2                   2.0
3 160137705 2                   2.0
4 160139180                     0.0
5 170110940                     0.0
6 170112624 2                   2.0
7 170138585                     0.0
9 180035096                     0.0
10 180043358                     0.0
12 180116207 1.5                   1.5
13 180131699                     0.0
14 190037351 1                   1.0
15 190043318                     0.0
16 190086530 2                   2.0
18 190094087 0.5                   0.5
19 190096063 1                   1.0
20 190098660 1                   1.0
21 190105526 2                   2.0
22 200017969                     0.0
23 200020960 2                   2.0
24 200022610 1.5                   1.5
25 200022857 0.5                   0.5
26 200044494 2                   2.0
27 200053680 2                   2.0
28 200057677                     0.0
29 200060295 1                   1.0
30 201000136                     0.0
31 202021767 1                   1.0
32 202033427 2                   2.0
33 202033580 1.5                   1.5
34 211010299 2                   2.0
35 211036123 2                   2.0
36 211038191 2                   2.0
37 211043342 2                   2.0
38 222011543 2                   2.0

5.2. Avaliações escritas

  Matrícula 1 (20) 2 (20) Total (40)
1 150140801 8.0   8.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   12.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   11.0
13 190043318 4.0   4.0
14 190086530 11.0   11.0
15 190094087 1.0   1.0
16 190096063 13.0   13.0
17 190098660     0.0
18 190105526 12.0   12.0
19 200017969     0.0
20 200020960 9.0   9.0
21 200022610 6.0   6.0
22 200022857 7.0   7.0
23 200044494 13.0   13.0
24 200053680 11.0   11.0
25 200057677     0.0
26 200060295     0.0
27 201000136     0.0
28 202021767 11.0   11.0
29 202033427 14.0   14.0
30 202033580 13.0   13.0
31 211010299 20.0   20.0
32 211036123 12.0   12.0
33 211038191 11.0   11.0
34 211043342 7.0   7.0
35 222011543 19.0   19.0

5.3. Projeto

  Matrícula Elem Max (5) Mergesort (10) ?? (15) Total (30)
1 150140801 3.5     3.5
2 160125073 5.0     5.0
3 160137705 5.0     5.0
4 160139180       0.0
5 170110940       0.0
6 170112624       0.0
7 170138585 3.5     3.5
8 180035096       0.0
9 180043358       0.0
10 180116207       0.0
11 180131699       0.0
12 190037351       0.0
13 190043318       0.0
14 190086530 5.0     5.0
15 190094087 5.0     5.0
16 190096063 5.0     5.0
17 190098660       0.0
18 190105526 5.0     5.0
19 200017969 5.0     5.0
20 200020960       0.0
21 200022610 5.0     5.0
22 200022857 5.0     5.0
23 200044494       0.0
24 200053680 5.0     5.0
25 200057677 4.0     4.0
26 200060295 5.0     5.0
27 201000136       0.0
28 202021767       0.0
29 202033427 5.0     5.0
30 202033580 5.0     5.0
31 211010299 5.0     5.0
32 211036123 4.0     4.0
33 211038191 5.0     5.0
34 211043342 5.0     5.0
35 222011543 5.0     5.0

5.4. Tabela de menções

  Matrícula Atividades Projeto Provas Total Menção
1 150140801 2.0 3.5 8.0 13.5  
2 160125073 2.0 5.0 4.0 11.0  
3 160137705 2.0 5.0 8.0 15.0  
4 160139180 0.0 0.0 0.0 0.0  
5 170110940 0.0 0.0 0.0 0.0  
6 170112624 2.0 0.0 12.0 14.0  
7 170138585 0.0 3.5 4.0 7.5  
8 180035096 0.0 0.0 0.0 0.0  
9 180043358 0.0 0.0 2.0 2.0  
10 180116207 1.5 0.0 0.0 1.5  
11 180131699 0.0 0.0 0.0 0.0  
12 190037351 1.0 0.0 11.0 12.0  
13 190043318 0.0 0.0 4.0 4.0  
14 190086530 2.0 5.0 11.0 18.0  
15 190094087 0.5 5.0 1.0 6.5  
16 190096063 1.0 5.0 13.0 19.0  
17 190098660 1.0 0.0 0.0 1.0  
18 190105526 2.0 5.0 12.0 19.0  
19 200017969 0.0 5.0 0.0 5.0  
20 200020960 2.0 0.0 9.0 11.0  
21 200022610 1.5 5.0 6.0 12.5  
22 200022857 0.5 5.0 7.0 12.5  
23 200044494 2.0 0.0 13.0 15.0  
24 200053680 2.0 5.0 11.0 18.0  
25 200057677 0.0 4.0 0.0 4.0  
26 200060295 1.0 5.0 0.0 6.0  
27 201000136 0.0 0.0 0.0 0.0  
28 202021767 1.0 0.0 11.0 12.0  
29 202033427 2.0 5.0 14.0 21.0  
30 202033580 1.5 5.0 13.0 19.5  
31 211010299 2.0 5.0 20.0 27.0  
32 211036123 2.0 4.0 12.0 18.0  
33 211038191 2.0 5.0 11.0 18.0  
34 211043342 2.0 5.0 7.0 14.0  
35 222011543 2.0 5.0 19.0 26.0  

Author: Flávio L. C. de Moura

Created: 2023-06-01 qui 22:19