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 | 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 | ||||
| 18 | |||||
| 19 | |||||
| 20 | |||||
| 21 | |||||
| 22 | |||||
| 23 | |||||
| 24 | |||||
| 25 | |||||
| 26 | |||||
| 27 | |||||
| 28 | |||||
| 29 | Revisão para a prova 2 | ||||
| 30 | Prova 2 | ||||
| Revisão de menção final |
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 (35) | Prova 2 (35) | Projeto (30) | Total (100) | Menção | |
|---|---|---|---|---|---|---|
| 1 | 170104630 | |||||
| 2 | 170141667 | |||||
| 3 | 170144631 | |||||
| 4 | 180102141 | |||||
| 5 | 180126890 | |||||
| 6 | 190014351 | |||||
| 7 | 190021276 | |||||
| 8 | 190029269 | |||||
| 9 | 190098406 | |||||
| 10 | 190100346 | |||||
| 11 | 190106298 | |||||
| 12 | 190113987 | |||||
| 13 | 190126183 | |||||
| 14 | 190131497 | |||||
| 15 | 190134330 | |||||
| 16 | 200014382 | |||||
| 17 | 200014978 | |||||
| 18 | 200040979 | |||||
| 19 | 200044486 | |||||
| 20 | 202006321 | |||||
| 21 | 202006401 | |||||
| 22 | 202017020 | |||||
| 23 | 202021785 | |||||
| 24 | 202037426 | |||||
| 25 | 202042829 | |||||
| 26 | 211010468 | |||||
| 27 | 211010477 | |||||
| 28 | 211055254 | |||||
| 29 | 211055325 | |||||
| 30 | 211055334 | |||||
| 31 | 211055380 | |||||
| 32 | 212006871 | |||||
| 33 | 221003995 | |||||
| 34 | 221004043 | |||||
| 35 | 221006404 | |||||
| 36 | 221006440 | |||||
| 37 | 221018906 | |||||
| 38 | 241034059 |
5. Bibliografia
bibliographystyle:plain
bibliography:~/workspace/org/zotLib.bib