Análise de Algoritmos - A1 (noturno)

Prof. Ronaldo Cristiano Prati

Bloco A, sala 513-2


Avisos


Horário das aulas


Atendimento


Ementa da disciplina


Recomendação

Disciplinas: Matemática Discreta; Algoritmos e Estruturas de Dados I.

Para facilitar o acompanhamento do curso, é recomendado que você possua:

Materiais de apoio para esses tópicos:


Bibliografia e materiais de apoio


Cronograma

Aula Data Tópicos
1 05/6 [pdf] [html] Introdução ao curso. Multiplicação. Referências: [LM],
2 07/6 [pdf] [html] Insertion Sort (com análise). Notação assintótica. Referências: Cap. 1, 11 [LM], notas de aula, Cap. 2.1, 2.2, 3.1 [CLRS2], Cap. 0.3 [DPV], 1.8, 2.1, 2.2, 2.3, 2.4 e 2.5 [R].
3 12/6 [pdf] [html] Notação assintótica. Referências: Cap. 1, 11 [LM], notas de aula, Cap. 2.1, 2.2, 3.1 [CLRS2], Cap. 0.3 [DPV], 1.8, 2.1, 2.2, 2.3, 2.4 e 2.5 [R].
14/6 cancelada
4 19/6 [pdf] [html] Divisão e Conquista. Mergesort. Recorrências. Referências: Cap. 3, 12, 16 [LM], notas de aula, Cap. 2.3, 4 (intro) [CLRS2], Cap. 2.3 [DPV], 1.5, 1.6, 1.7 e 4.1 [R].
21/6 ---- Feriado ----
5 26/6 [pdf] [html] Solução de recorrências: substituição e iteração. Referências: Cap. 3 [LM], Cap. 4 [CLRS2].
6 28/6 [pdf] [html] Solução de recorrências: árvore de recursão e Teorema Mestre. Referências: Cap. 3 [LM], Cap. 4 [CLRS2], 4.1, 4.2, 4.3, 4.4, 4.5, 4.6 [R].
7 03/7 [pdf] [html] Quicksort. Referências Cap. 14 [LM], Cap. 7 [CLRS2], 5.1, 5.2, 5.3, 5.4 [R].
8 05/7 [pdf] [html] Selection Sort. Heap. Heapsort. Referências: Parte II, Cap. 8 e 13.2 [LM], Cap. 6 [CLRS2], 12.1, 12.2, 12.3 [R].
9 10/7 [pdf] [html] Grafos. Estrutura de dados Busca em grafos. Cap. 19 e 20 [LM], Cap. 22 [CLRS2], 9.2, 10.1 [R].
10 12/7 [pdf] [html] Busca em grafos. Aplicações.Referências: Cap. 20 [LM], Cap. 22 [CLRS2], 10.2, 10.3, 10.4, 10.5 [R].
11 17/7 Solução de exercícios.
12 19/7 gabarito Prova 1
13 24/7 [pdf] [html] Introdução a algoritmos gulosos. Escalonamento de tarefas compatíveis. Mochila fracionária. Escalonamento de tarefas compatíveis. Mochila fracionária. Referências: Cap. 17 [LM], Cap. 16 [CLRS2], 3, 5, 6, 7, 8 [R].Extra: site prof. Feofiloff, texto prof. Flávio Miyazawa.
14 26/7 [pdf] [html] Árvore geradora mínima. Algoritmo de Kruskal. Union-Find. Referências: Cap. 21 [LM], Cap. 23 [CLRS2], 10, 17, 18, 19, 20, 21 [R]. Extra: animação Union Find, outra animação Union Find, animação Kruskal, outra animação Kruskal.
15 31/7 [pdf] [html] Compressão de dados. Algoritmo de Huffman. Referências: Cap. 17 [LM], Cap. 16 [CLRS2], 33, 34, 35, 36, 37, 38 [R]. Extra: animação Huffman.
16 02/8 [pdf] [html] Introdução a Programação Dinâmica. Corte da barra de ferro. Mochila inteira. Referências: Cap. 18 [LM], Cap. 15 [CLRS3], 39, 43, 44, 45, 46 [R]. Extra: animação Fibonacci, animação Mochila
17 07/8 [pdf] [html] Alinhamento de sequências. Algoritmo de Needleman-Wunsch. Referências: Cap. 18 [LM], Cap. 15 [CLRS3], 47, 48 [R]. Extra: animação Needleman-Wunsch.
18 09/8 [pdf] [html] Caminhos mínimos. Algoritmo de Floyd-Warshall. Referências: Cap. 23 [LM], Cap. 25 [CLRS2], 62, 63, 64 [R].Extra: animação Floyd-Warshall.
29 14/8 [pdf] [html] Redução. Classes P, NP, NP-difícil e NP-completo. Referências: Cap. 24 [LM], Cap. 34 [CLRS2], 68, 69, 70, 71, 72 [R]. Extra: Uma pergunta de um milhão de dólares, P vs. NP and the Computational Complexity Zoo, Map of Computer Science (não exatamente relacionado com a aula).
20 16/8 [pdf] [html] Abordagens para problemas NP-difíceis.
21 21/8 Solução de exercícios.
22 23/8 Prova 2
23 28/8 Prova de recuperação (reposição do feriado, portanto aula às 19h)

Listas de exercícios


Avaliação


Recupeção


Avaliação substitutiva