Para cada aula aparecem Transparências (usadas na
aula) e Papel (mesmo material, em formato melhor para
impressão).
As transparências se baseiam nas feitas pelos Profs. Paulo Feofiloff, José Coelho de Pina e Cristina Gomes Fernandes.
Referências
- CLRS é Cormen, Leiserson, Rivest e Stein, Introduction to Algorithms, 3a edição.
- KT é Kleinberg e Tardos, Algorithm Design.
- 8/08 - Aula 1 (Transparências/Papel)
- Como contar instruções
- Por que ignorar as constantes
- Notação O
Leitura recomendada: CLRS, secs 1.1 Algorithms, 1.2 Algorithms as a technology, 2.1 Insertion sort e 2.2 Analyzing algorithms.
- 10/08 - Aula 2 (Transparências/Papel)
- Notação assintótica: O, Ω e Θ
- Crescimento de funções
- Análise de pior caso, melhor caso e caso médio do InsertionSort
Leitura recomendada: CLRS, sec 3.1 Asymptotic notation e 3.2 Standard notation and common functions. Se tiver dificuldades com a parte matemática, revise o material coberto nos apêndices A Summations e parte do C Counting and probability do CLRS.
- 15/08 - Aula 3 (Transparências/Papel)
Leitura recomendada:sec 2.3 Designing algorithms e começo do cap 4 Recurrences, incluindo a sec 4.1 The substitution method.
- 17/08 - Aula 4 (Transparências/Papel)
- Quicksort
- Análises de pior e melhor caso
Leitura recomendada:sec 4.2 The recursion-tree method e parte do cap 7 Quicksort do CLRS até sec 7.2.
- 22/08 - Aula 5 (Transparências/Papel)
- Análise probabilística
- Cálculo do máximo
- Análise do caso médio do Quicksort
Leitura recomendada: CLRS cap 7 Quicksort todo e CLRS secs 5.1 The hiring problem e 5.2 Indicator random variables, apêndices C.1 a C.3.
- 24/08 - Aula 6 (Transparências/Papel)
- Quicksort aleatorizado
- Select aleatorizado
Leitura recomendada: CLRS secs 7.3 e 7.4 do capítulo Quicksort e secs 9.1 e 9.2 do capítulo Medians and Order Statistics. KT, sec 13.5.
- 29/08 - Aula 7
Leitura recomendada: CLRS sec 6, CLRS secs 4.3-4.6, KT 5.2
- 31/08 - Aula 8 (Transparências/Papel)
- Cota inferior para ordenação
- Ordenação em tempo linear
Leitura recomendada: CLRS cap 8
- 12/9 - Aula 9 (Transparências/Papel)
- Elementos de programação dinâmica
- Ex: Números de Fibonacci
- Ex: corte de hastes
Leitura recomendada: CLRS cap 15
- 14/9 - Aula 10 (Transparências/Papel)
- Multiplicação de cadeias de matrizes
- Elementos de programação dinâmica
- Árvore binária de busca ótima
Leitura recomendada: CLRS cap 15
- 19/9 - Aula 11 (Transparências/Papel)
- Árvore binária de busca ótima com falhas
- Subsequência comum máxima com falhas
- Seam carving
Leitura recomendada: CLRS cap 15
- 21/9 - Não houve aula
- Aula 12
- Dúvidas sobre material visto em aula, véspera de prova
- Solução
do problema UVA 10086. Solução análoga a Transparências/Papel, que
poderia ter sido uma aula, mas não foi.
- 28/9 - Prova - Obaaaa!
- 3/10 - Aula 13 (Transparências/Papel)
- Grafos e suas representações
- Busca em largura
Leitura recomendada: CLRS cap 22, secs 1,2
- 5/10 - Aula 14 (Transparências/Papel)
- Busca em largura, prova de corretude
- Aplicações: componentes conexas, reconhecimento de grafos bipartidos
Leitura recomendada: CLRS cap 22, secs 1,2
- 10/10 - Break
- 17/10 - Aula 15 (Transparências/Papel)
- Busca em profundidade, estrutura parentizada.
- Aplicação: ordenação topológica.
Leitura recomendada: CLRS cap 22, secs 3, 4.
- 19/10 - Aula 16 (Transparências/Papel)
- Relações de equivalência e componentes fortemente conexas
- Algoritmo de Kosaraju-Sharir
- Condensação de um digrafo
Leitura recomendada: CLRS cap 22, secs 3, 4.
- 24/10 - Aula 17 (Transparências/Papel)
- Caminhos de comprimento mínimo
- Algoritmo de Dijkstra
- Algoritmo de Floyd-Warshall
Leitura recomendada: CLRS secs 24.3 e 25.2
- 26/10 - Aula 18 (Transparências/Papel)
- Árvore geradora mínima
- Algoritmo de Prim
- Algoritmo de Kruskal
- Necessidade do Union-Find
Leitura recomendada: CLRS cap 23
- 31/10 - Aula 19 (Transparências/Papel)
Leitura recomendada: CLRS cap 21
- 7/11 - Aula 20 (Transparências/Papel)
- Complexidade algorítmica de problemas
- A classe P
- Certificados curtos e a classe NP
- O problema P=NP
Leitura recomendada: CLRS cap 34
- 9/11 - Aula 21 (Transparências/Papel)
- Redução polinomial de problemas
- Algumas reduções
- Teorema de Cook-Levin
Leitura recomendada: CLRS cap 34
- 21/11 - Aula 22 (Transparências/Papel)
- Redução polinomial de problemas
- Provas de NP-completude via redições
- Problemas NP-difíceis
Leitura recomendada: CLRS cap 34