Projeto e Análise de Algoritmos (2021-2)
Table of Contents
- Plano de Ensino
- Calendário Acadêmico
- Cronograma de aulas
- DONE Aula 01 - Introdução e motivação
- DONE Aula 02 - Ordenação por inserção
- DONE Aula 03 - Ordenação por inserção recursivo
- DONE Aula 04 - Formalização em Coq da ordenação por inserção
- DONE Aula 05 - Formalização da ordenação por inserção
- DONE Aula 06 - Formalização da ordenação por inserção
- DONE Aula 07 - Complexidade da ordenação por inserção em Coq
- DONE Aula 08 - Notação assintótica
- DONE Aula 09 - Equivalência entre noções de permutação
- DONE Aula 10 - O algoritmo mergesort
- DONE Aula 11 - Equações de recorrência
- DONE Aula 12 - O Teorema Mestre
- Carnaval
- DONE Aula 13 - Apresentação do projeto
- DONE Aula 14 - Heapsort
- DONE Aula 15 - Quicksort
- DONE Aula 16 - Ordenação em tempo linear
- DONE Aula 17 - Programação dinâmica
- DONE Aula 18 - Discussão sobre o projeto
- DONE Aula 19 - Busca em Largura - BFS
- DONE Aula 20 - Busca em Profundidade - DFS
- DONE Aula 21 - Componentes fortemente conexas
- DONE Aula 22 - Árvores geradoras mínimas
- Aula 23 - Aula cancelada
- DONE Aula 24 - Caminhos Mínimos
- DONE Aula 25 - NP-completude: A classe P
- DONE Aula 26 - As classes NP e NPC
- Feriado de Tiradentes
- DONE Aula 27 - Problemas NP-completos
- TODO Aula 28 - Mais problemas NP-completos
- TODO Aula 29 -
- TODO Aula 30 -
- Quadro de frequência
- Quadros de Notas
Cronograma de aulas
DONE Aula 01 - Introdução e motivação
Material da aula:
- O projeto será feito em Coq
- Notas de aula (introdução ao Coq): pdf
- Notas de aula (introdução ao Coq): pdf
- GitHub Classroom (link para a criação dos grupos do projeto): https://classroom.github.com/a/JkJbX0Zp
- Playlist sobre indução (inclusive com exercícios): Canal Ad infinitum
- Leitura: indução
DONE Aula 02 - Ordenação por inserção
DONE Aula 03 - Ordenação por inserção recursivo
DONE Aula 04 - Formalização em Coq da ordenação por inserção
Material da aula:
- Consultar repositório do projeto (público)
- Gabarito da atividade de frequência (pdf)
DONE Aula 05 - Formalização da ordenação por inserção
DONE Aula 06 - Formalização da ordenação por inserção
Material da aula:
- Consultar repositório do projeto (público)
- Gabarito da atividade de frequência (pdf)
DONE Aula 07 - Complexidade da ordenação por inserção em Coq
Material da aula:
- Consultar repositório do projeto (público)
- Gabarito da atividade de frequência (pdf)
DONE Aula 08 - Notação assintótica
DONE Aula 09 - Equivalência entre noções de permutação
DONE Aula 10 - O algoritmo mergesort
DONE Aula 11 - Equações de recorrência
Carnaval
DONE Aula 14 - Heapsort
DONE Aula 15 - Quicksort
DONE Aula 16 - Ordenação em tempo linear
DONE Aula 17 - Programação dinâmica
DONE Aula 18 - Discussão sobre o projeto
DONE Aula 19 - Busca em Largura - BFS
DONE Aula 20 - Busca em Profundidade - DFS
DONE Aula 21 - Componentes fortemente conexas
DONE Aula 22 - Árvores geradoras mínimas
Aula 23 - Aula cancelada
DONE Aula 24 - Caminhos Mínimos
DONE Aula 25 - NP-completude: A classe P
DONE Aula 26 - As classes NP e NPC
Feriado de Tiradentes
DONE Aula 27 - Problemas NP-completos
TODO Aula 28 - Mais problemas NP-completos
TODO Aula 29 -
TODO Aula 30 -
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 |