Projeto e Análise de Algoritmos (2024-1)
Table of Contents
3. Cronograma
| Aula | Data | Assunto | Arquivos | Observações | |
|---|---|---|---|---|---|
| 1 | ✓ | Introdução e motivação | |||
| 2 | ✓ | Insertion sort recursivo | pdf, pdf | ||
| 3 | ✓ | Insertion sort recursivo no Coq | |||
| 4 | ✓ | A correção de algoritmos | pdf, pdf | ||
| 5 | ✓ | A complexidade de algoritmos | |||
| 6 | ✓ | Notação assintótica | |||
| 7 | ✓ | Merge sort | pdf, pdf | ||
| 8 | ✓ | Teorema Mestre | Anotações no caderno (OneNote) do Teams | ||
| Período de greve | |||||
| 9 | ✓ | Insertion sort (Correção em Coq) - parte 2 | |||
| 10 | ✓ | Insertion sort (Correção em Coq) - parte 3 | |||
| Aula cancelada | |||||
| Aula cancelada | |||||
| 11 | ✓ | Quicksort | |||
| 12 | ✓ | Exercícios | coq | Projeto - proposta 1 (orientações) e (link) | |
| 13 | ✓ | Heapsort | Resumo da aula (link) | ||
| 14 | ✓ | Exercícios | Resumo da aula (link) | ||
| 15 | ✓ | Ordenação em tempo linear | pdf, pdf | ||
| 16 | ✓ | Exercícios | Lista de exercícios | ||
| 17 | ✓ | Prova 1 | OneNote | Gabarito da prova | |
| 18 | ✓ | Ordenação por inserção em Coq | coq | Tema 2 do projeto: Inserção binária (coq) | |
| 19 | ✓ | Programação Dinâmica | |||
| 20 | ✓ | Exercícios | |||
| 21 | ✓ | Algoritmos gulosos | |||
| 22 | ✓ | Exercícios | |||
| 23 | ✓ | NP-completude (introdução) | |||
| 24 | ✓ | As classes P e NP | |||
| 25 | ✓ | A classe NPC | |||
| 26 | ✓ | Problemas NP-completos | |||
| 27 | ✓ | Mais problemas NP-completos | |||
| 28 | ✓ | Exercícios | Lista de exercícios (gabarito) | ||
| 29 | ✓ | Revisão para a prova 2 | Lista de exercícios (gabarito) | ||
| 30 | ✓ | Prova 2 | Gabarito da prova | ||
| Prova substitutiva (opcional) |
3.1. Aula de
- O algoritmo selection sort surgiu como solução natural ao problema proposto no início da aula: ordenar um vetor de inteiros a partir da seleção do seu maior elemento (pdf). Este algoritmo corresponde à abordagem força-bruta.
- Em seguida, o problema é resolvido de forma mais eficiente utilizando uma estrutura de dados adequada (heap binário). Atividades sugeridas:
- Resolver os exercícios propostos em pdf.
- Resolver os exercícios propostos em pdf.
3.2. Aula de
- Resolvemos o exercício 1.4 de pdf
- Revisamos alguns aspectos da formalização da correção do algoritmo de ordenação por inserção em Coq. Arquivo: paa_2024_1_insertion_sort.v
4. Quadro de Notas
| Matrícula | Prova 1 (10) | Prova 2 (10) | |
|---|---|---|---|
| 1 | 170141667 | 10.0 | |
| 2 | 170144631 | 8.0 | 8.5 |
| 3 | 180102141 | 9.0 | 8.5 |
| 4 | 180126890 | 7.0 | 5.5 |
| 5 | 190014351 | 2.0 | |
| 6 | 190021276 | 7.0 | 9.0 |
| 7 | 190029269 | 3.5 | 2.5 |
| 8 | 190126183 | 2.0 | 4.5 |
| 9 | 190131497 | 3.5 | 3.5 |
| 10 | 190134330 | 7.0 | 5.0 |
| 11 | 200014382 | 10.0 | 10.0 |
| 12 | 200014978 | 10.0 | 10.0 |
| 13 | 200044486 | 7.0 | 5.0 |
| 14 | 202006321 | 5.5 | 5.0 |
| 15 | 202006401 | 10.0 | 9.0 |
| 16 | 202021785 | 4.5 | 7.5 |
| 17 | 202037426 | 6.5 | 3.5 |
| 18 | 211010468 | 6.5 | 4.0 |
| 19 | 211010477 | 8.5 | 9.0 |
| 20 | 211055254 | 8.0 | 9.5 |
| 21 | 211055325 | 8.0 | 9.0 |
| 22 | 211055334 | 9.0 | 9.0 |
| 23 | 211055380 | 9.0 | 2.5 |
| 24 | 221003995 | 4.5 | 6.0 |
| 25 | 221018906 | 7.5 | 4.5 |
| Matrícula | Prova 1 (35) | Prova 2 (35) | Projeto (30) | Total (100) | Menção | |
|---|---|---|---|---|---|---|
| 1 | 170141667 | 35.0 | 0.0 | 30.00 | 65.0 | MM |
| 2 | 170144631 | 28.0 | 29.8 | 10.00 | 67.8 | MM |
| 3 | 180102141 | 31.5 | 29.8 | 20.00 | 81.3 | MS |
| 4 | 180126890 | 24.5 | 19.2 | 30.00 | 73.7 | MS |
| 5 | 190014351 | 7.0 | 0.0 | 7.0 | SR | |
| 6 | 190021276 | 24.5 | 31.5 | 56.0 | MM | |
| 7 | 190029269 | 12.2 | 8.8 | 10.00 | 31.0 | MI |
| 8 | 190126183 | 7.0 | 15.8 | 12.00 | 34.8 | MI |
| 9 | 190131497 | 12.2 | 12.2 | 30.00 | 54.4 | MM |
| 10 | 190134330 | 24.5 | 17.5 | 15.00 | 57.0 | MM |
| 11 | 200014382 | 35.0 | 35.0 | 20.00 | 90.0 | SS |
| 12 | 200014978 | 35.0 | 35.0 | 20.00 | 90.0 | SS |
| 13 | 200044486 | 24.5 | 17.5 | 30.00 | 72.0 | MS |
| 14 | 202006321 | 19.2 | 17.5 | 25.00 | 61.7 | MM |
| 15 | 202006401 | 35.0 | 31.5 | 12.00 | 78.5 | MS |
| 16 | 202021785 | 15.8 | 26.2 | 30.00 | 72.0 | MS |
| 17 | 202037426 | 22.8 | 12.2 | 30.00 | 65.0 | MM |
| 18 | 211010468 | 22.8 | 14.0 | 14.00 | 50.8 | MM |
| 19 | 211010477 | 29.8 | 31.5 | 20.00 | 81.3 | MS |
| 20 | 211055254 | 28.0 | 33.2 | 20.00 | 81.2 | MS |
| 21 | 211055325 | 28.0 | 31.5 | 20.00 | 79.5 | MS |
| 22 | 211055334 | 31.5 | 31.5 | 20.00 | 83.0 | MS |
| 23 | 211055380 | 31.5 | 8.8 | 30.00 | 70.3 | MS |
| 24 | 221003995 | 15.8 | 21.0 | 15.00 | 51.8 | MM |
| 25 | 221018906 | 26.2 | 15.8 | 30.00 | 72.0 | MS |
5. Bibliografia
bibliographystyle:plain
bibliography:~/workspace/org/zotLib.bib