Cronograma de aulas
DONE Aula 01 - Introdução e motivação
Resumo da aula:
Apresentamos o protocolo covid adotado pela UnB, e o plano de ensino do curso.
- Link para a gravação da aula: Teams - aula 01
DONE Aula 02 - Análise de algoritmos
Resumo da aula:
Iniciamos com a análise da correção do algoritmo de busca sequencial dando ênfase para a construção e prova da invariante de laço. Em seguida, analisamos a complexidade de tempo da busca sequencial (melhor e pior casos) considerando o custo de cada linha do pseudocódigo. O mesmo foi feito para o algoritmo de ordenação por inserção, e no final vimos a ideia inicial de como fazer uma análise mais geral, e não baseada no custo de cada linha (análise assintótica). Exercícios sugeridos: 89 e 90.
- Link para a gravação da aula: Teams - aula 02
- Anotações da aula: pdf
DONE Aula 03 - A correção de algoritmos
Material da aula:
- Notas de aula (capítulo 5, a partir da página 70)
- Capítulo 3, Cormen et.al. 4ed (2022)
Resumo da aula:
Iniciamos com comentários sobre o exercício que estabelece a correção do algoritmo BubbleSort, que ficou como um dos exercícios da semana valendo pontos (atividade postada no Teams). Em seguida, refizemos a análise assintótica, no melhor e pior casos, do algoritmo de ordenação por inserção (insertion sort). Por fim, prosseguimos comentando as notas de aulas até o exercício 93. A gravação da aula está dividida em duas partes por consequência de queda da conexão.
- Link para a gravação da aula:
- Anotações da aula: pdf
Feriado
DONE Aula 04 - A notação assintótica
Resumo da aula:
Finalizamos a apresentação sobre notação assintótica, e fizemos alguns exemplos.
- Link para a gravação da aula: Teams - aula 04
- Anotações da aula: pdf
CANCELLED Aula 05
DONE Aula 06 - Recursão - parte 1
Material da aula:
- Leitura: Seção 5.1 das notas de aula.
- Fundamentos de Git e GiyHub: link
- Projeto: link para a criação dos grupos
Resumo da aula:
Iniciamos com uma breve discussão sobre o exercício da semana passada, e iniciamos o desenvolvimento da prova de correção da busca sequencial recursiva em Coq.
- Link para a gravação da aula:Teams - aula 06
DONE Aula 07 - Recursão - parte 2
Resumo da aula:
Fizemos uma descrição geral do projeto, e formalizamos a complexidade do pior caso da busca sequencial recursiva no Coq.
- Link para a gravação da aula: Teams - aula 07
DONE Aula 08 - Equações de recorrência
Resumo da aula:
Equações de recorrência e apresentação da primeira versão do Teorema Mestre.
- Link para a gravação da aula: Teams - aula 08
- Link para a prova da regra de suavização: Teams - suavização
- Link para a prova de um resultado auxiliar para a regra da suavização: Teams - suavização (auxiliar)
- Link para a prova da regra de suavização: Teams - suavização
- Anotações da aula: pdf
DONE Aula 09 - Equações de recorrência
Resumo da aula:
Apresentamos a ideia geral da prova do Teorema Mestre, e resolvemos algumas relações de recorrência. Por fim, iniciamos uma formalização do algoritmo mergesort.
- Link para a gravação da aula: Teams - Aula 09
- Anotações da aula: pdf
- Link do repositório com o arquivo inicial da formalização em Coq: GitHub
DONE Aula 10 - Divisão e Conquista
Resumo da aula:
Fizemos uma breve recapitulação do Teorema Mestre com a resolução de um exercício. Em seguida, prosseguimos com a formalização do algoritmo mergesort em Coq.
- Link para a gravação da aula: Teams - aula 10
- Anotações da aula: pdf
DONE Aula 11 - Divisão e Conquista
Resumo da aula:
Apresentamos o algoritmo quicksort e fizemos a análise assintótica do pior caso.
- Link para a gravação da aula: Teams - aula 11
- Anotações da aula: pdf
DONE Aula 12 - Heapsort
Resumo da aula:
Apresentamos o algoritmo heapsort e fizemos a análise assintótica do pior caso.
- Link para a gravação da aula: Teams - aula 12
- Anotações da aula: pdf
DONE Aula 13 - Aula de exercícios
Resumo da aula:
Comentamos sobre os exercícios disponibilizados acima.
- Link para a gravação da aula: Teams - aula 13
- Anotações da aula: pdf
- Soluções dos exercícios pré-prova: pdf
Reunião anual da SBPC
Reunião anual da SBPC
DONE Aula 15 - Comentários sobre a prova e o projeto
Material da aula:
- Arquivo Coq: files/paa_2022_1_mergesort.v
- Arquivo TeX (relatório): files/paa-2022-1-relatorio.tex
- Biblioteca CoqDoc: files/coqdoc.sty
Resumo da aula:
Fizemos comentários gerais sobre o resultado da prova, e avançamos no desenvolvimento da formalização do algoritmo mergesort que visa servir de modelo para o desenvolvimento do projeto.
- Link para a gravação da aula: Teams - aula 15
DONE Aula 16 - Comentários sobre o projeto
Resumo da aula:
Fizemos uma estruturação da pontuação do projeto. O arquivo disponibilizado mostra as possibilidades de pontuação.
- Link para a gravação da aula: Teams - aula 16
DONE Aula 17 - Comentários sobre o projeto
DONE Aula 18 - Ordenação em tempo linear
Resumo da aula:
Estudamos os chamados algoritmos de classificação (counting-sort e radix-sort), e avançamos na formalização do algoritmo mergesort.
- Link para a gravação da aula: Teams - aula 18
- Anotações da aula: pdf
DONE Aula 19 - Algoritmos em grafos e projeto
DONE Aula 21 - O algoritmo DFS
Semana Universitária
Semana Universitária
DONE Aula 22 - NP-completude
DONE Aula 23 - NP-completude
DONE Aula 24 - NP-completude
DONE Aula 25 - NP-completude
Resumo da aula:
Discutimos detalhadamente a redução polinomial de 3-SAT para VERTEX-COVER. Infelizmente, no finalzinho da conversa houve uma queda de energia. Amanhã publicarei material para compensar a interrupção ocorrida no final da aula.
- Link para a gravação da aula: Teams - aula 25
- Anotações da aula: pdf