Para voltar à página raíz clique aqui.

Projeto e Análise de Algoritmos

Turmas A e B - 2s2020

Informações do Professor

Nome: Mário César San Felice
Sala: G.08 do Departamento de Computação
Email: [ meu último último nome ] (at) ufscar.br

Informações do Curso

Trabalhos Práticos

Tópicos das Aulas

Aula 01 - Motivação, Multiplicação, Recorrências
Vídeos da aula 01: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 2.1 do Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 1 2, 1 3.

Aula 02 - Princípios da Análise de Algoritmos, Indução Matemática
Vídeos da aula 02: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 0.2 do Algorithms, Capítulo 5 do Elementos de Matemática Discreta para Computação.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 1 8.

Aula 03 - Divisão e Conquista, MergeSort, Árvore de Recorrência
Vídeos da aula 03: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 2.3 do Algorithms, Seções 2.3 e 4.4 (4.2 da 2ed) do Introduction to Algorithms, Capítulo 9 do Projeto de Algoritmos (em C).
Material complementar: Vídeo aulas do prof. Tim Roughgarden 1 5, 1 6, 1 7.

Aula 04 - Análise Assintótica
Vídeos da aula 04: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 0.3 do Algorithms, Capítulo 3 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 2 1, 2 2, 2 3, 2 4, 2 5.

Aula 05 - Encontrar o Par Mais Próximo
Notas de aula: PDF.
Bibliografia: Exercício 2.32 do Algorithms, Seção 33.4 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 3 4, 3 5.

Aula 06 - Teorema Mestre
Vídeos da aula 06: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 2.2 do Algorithms, Seções 4.5 e 4.6 (4.3 e 4.4 da 2ed) do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 4 1, 4 2, 4 3, 4 4, 4 5, 4 6.

Aula 06.2 - (Bônus) Multiplicação de Matrizes de Strassen
Notas de aula: PDF.
Bibliografia: Seção 2.5 do Algorithms, Seções 4.2 e 4.3 (4.1 da 2ed) do Introduction to Algorithms.
Material complementar: Vídeo aula do prof. Tim Roughgarden 3 3.

Aula 07 - QuickSort e Problema da Separação
Notas de aula: PDF.
Bibliografia: Capítulo 7 do Introduction to Algorithms, Capítulo 11 do Projeto de Algoritmos (em C).
Material complementar: Vídeo aulas do prof. Tim Roughgarden 5 1, 5 2, 5 3, 5 4, 6 1, 6 2, 6 3.

Aula 08 - Bases de Probabilidade, Problema da Seleção
Notas de aula: PDF.
Bibliografia: Seção 2.4 do Algorithms, Seção 9.2 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 7 1, 7 2, 8 1, 8 2.

Aula 09 - Grafos, Busca em Grafos e Busca em Largura
Notas de aula: PDF.
Bibliografia: Seções 3.1 e 4.2 do Algorithms, Seções 22.1 e 22.2 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 9 2, 10 1, 10 2, 10 3, 10 4.

Aula 10 - Busca em Profundidade e Ordenação Topológica
Notas de aula: PDF.
Bibliografia: Seções 3.2 e 3.3 do Algorithms, Seções 22.3 e 22.4 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 10 5, 10 6.

Aula 11 - Algoritmos Gulosos e Problema do Escalonamento
Vídeos da aula 11: Playlist.
Notas de aula: PDF.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 1, 2, 3, 4, 5, 6.

Aula 12 - Seleção de Atividades e Mochila Fracionária
Vídeos da aula 12: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 16.1 do Introduction to Algorithms.
Material complementar: Nota de aula sobre mochila fracionária do profe. Paulo Feofiloff.

Aula 13 - Caminhos Mínimos, Algoritmo de Dijkstra, Heap com Atualização
Notas de aula: PDF.
Bibliografia: Seções 4.3 e 4.4 do Algorithms, Seções 24.3 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden sobre Dijkstra 11 1, 11 2, 11 3, 11 4 e sobre Heaps 12 1, 12 2, 12 3.

Aula 14 - Árvores Geradoras Mínimas (MST), Propriedade do Corte, Algoritmo de Prim
Vídeos da aula 14: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 5.1 do Algorithms, Capítulo 23 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden sobre Prim 1, 2, 3, 4, 5, 6, 7.

Aula 15 - Árvores Geradoras Mínimas (MST), Algoritmo de Kruskal
Notas de aula: PDF.
Bibliografia: Seção 5.1 do Algorithms, Capítulo 23 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden sobre Kruskal 1, 2, 3, 4, 5.

Aula 16 - Union Find, k-Clusterização com Espalhamento Máximo
Notas de aula: PDF.
Bibliografia: Seção 5.1 do Algorithms, Capítulo 21 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden sobre Union-Find 1, 2, 3, 4, 5, 6, 7, 8, 9 e sobre k-Clusterização 1, 2.

Aula 17 - Programação Dinâmica, Conjunto Independente de Peso Máximo em Caminhos
Vídeos da aula 17: Playlist.
Notas de aula: PDF.
Bibliografia: Seção 6.7 do Algorithms, Seção 15.3 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 1, 2, 3, 4, 5.

Aula 18 - Problemas da Mochila e do Alinhamento de Sequências
Vídeos da aula 18: Playlist.
Notas de aula: PDF.
Bibliografia: Seções 6.4 e 6.3 do Algorithms.
Material complementar: Nota de aula sobre mochila do profe. Paulo Feofiloff e vídeo aulas do prof. Tim Roughgarden sobre mochila 1, 2, 3 e sobre alinhamento de sequências 1, 2, 3.

Aula 19 - Problema da Árvore Binária de Busca Ótima
Notas de aula: PDF.
Bibliografia: Seção 15.5 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden 1, 2, 3, 4, 5.

Aula 20 - Caminhos Mínimos, Algoritmo de Bellman-Ford
Notas de aula: PDF.
Bibliografia: Seção 4.6 do Algorithms e Seção 24.1 do Introduction to Algorithms.
Material complementar: Vídeo aulas do prof. Tim Roughgarden sobre Bellman-Ford 1, 2, 3, 4, 5, 6 e sobre roteamento na internet 1, 2, 3.

Aula 21 - Caminhos Mínimos de Todos para Todos, Algoritmos de Floyd-Warshall e de Johnson
Material complementar: Vídeo aulas do prof. Tim Roughgarden sobre Floyd-Warshall 1, 2, 3 e sobre Johnson 1, 2, 3.

Aulas 22 e 23 - Problemas NP-Completos, Reduções entre Problemas (Partes 1 e 2)
Material complementar: Vídeo aulas do prof. Tim Roughgarden 1, 2, 3, 4, 5, 6.

Aula 24 - Algoritmos Exatos para Cobertura por Vértices e Problema do Caixeiro Viajante
Material complementar: Vídeo aulas do prof. Tim Roughgarden sobre Cobertura por Vértices 1, 2, 3 e sobre Problema do Caixeiro Viajante 1, 2.

Aulas 25 e 26 - Algoritmos de Aproximação para Problemas do Caixeiro Viajante e da Mochila (Partes 1 e 2)
Material complementar: Vídeo aulas do prof. Tim Roughgarden 1, 2, 3, 4, 5, 6.

Aula 27 - Algoritmo de Busca Local para Problema do Corte Máximo
Material complementar: Vídeo aulas do prof. Tim Roughgarden 1, 2, 3, 4.

Listas de Exercícios

Abaixo estão indicados vários exercícios da 2a edição do Introduction to Algorithms (CLRS) e do Algorithms (DPV).

Sugere-se que cada estudante tente resolver individualmente os exercícios e só depois discuta-os em grupo. Dúvidas e dificuldades podem ser apresentadas ao docente.

  1. [Básico]([CLRS] Capítulo 1): Exercícios 1.2-2, 1.2-3; Problema 1-1.
  2. [Básico]([CLRS] Capítulo 2): Exercícios 2.1-3, 2.1-4, 2.2-2, 2.2-3, 2.3-3, 2.3-5, 2.3-6, 2.3-7; Problema 2-1.
  3. [Heapsort] ([CLRS] Capítulo 6): Exercícios 6.1-4, 6.1-5, 6.2-1, 6.2-2, 6.2-3, 6.2-4, 6.2-6, 6.4-3, 6.4-4, 6.4-5, 6.5-8.
  4. [Análise assintótica] ([CLRS] Capítulo 3): Exercícios 3.1-1, 3.1-2, 3.1-3, 3.1-4, 3.1-6, 3.1-7, 3.1-8, 3.2-3; Problemas 3-1, 3-2, 3-3, 3-4.
  5. [Análise assintótica] ([DPV] Capítulo 0): Exercícios 0.1, 0.2, 0.3, 0.4.
  6. [Recorrências] ([CLRS] Capítulo 4): Exercícios 4.1-2, 4.1-5, 4.2-2, 4.2-4, 4.2-5, 4.3-1, 4.3-2, 4.3-4, 4.3-5, 4.4-2; Problemas 4-1, 4-3 b, 4-4 a, c, d, e, f, h, i.
  7. [Divisão-e-conquista e Recorrências] ([DPV] Capítulo 2): Exercícios 2.3, 2.4, 2.5, 2.11, 2.12, 2.13, 2.14, 2.15, 2.16, 2.17, 2.18, 2.19, 2.20, 2.21, 2.22, 2.23, 2.24, 2.25.
  8. [Quicksort] ([CLRS] Capítulo 7): Exercícios 7.2-2, 7.2-3; Problemas 7-3, 7-4.
  9. [Problema da Seleção] ([CLRS] Capítulo 9): Exercícios 9.1-1, 9.2-4; Problemas 9-1 a, b, c.
  10. [Representação de Grafos]([CLRS] Capítulo 22): Exercícios 22.1-1 a 22.1-6.
  11. [Busca em Largura (BFS)]([CLRS] Capítulo 22): Exercícios 22.2-1 a 22.2-9.
  12. [Busca em Profundidade (DFS)]([CLRS] Capítulo 22): Exercícios 22.3-1 a 22.3-12.
  13. [Ordenação Topológica]([CLRS] Capítulo 22): Exercícios 22.4-1 a 22.4-5.
  14. [Componentes Fortemente Conexos]([CLRS] Capítulo 22): Exercícios 22.5-1 a 22.5-7; Problema 22-1.
  15. [Caminhos Mínimos - Dijkstra]([CLRS] Capítulo 24:) Exercícios 24.3-1 a 24.3-8.
  16. [Árvores Geradoras Mínimas - Básico]([CLRS] Capítulo 23): Exercícios 23.1-1 a 23.1-11.
  17. [Árvores Geradoras Mínimas - Prim e Kruskal]([CLRS] Capítulo 21 e 23): Exercícios 21.2-1 a 21.2-2, 21.2-4 a 21.2-6; 23.2-1 a 23.2-5, 23.2-8; Problemas 23-1 e 23-4.
  18. [Algoritmos gulosos] ([CLRS] Capítulo 16): Exercícios 16.1-1, 16.1-2, 16.1-3, 16.1-5 , 16.1-4, 16.2-3,16.2-4, 16.2-5, 16.3-1, 16.3-4, 16.3-7, 16.3-8; Problemas: 16-1.
  19. [Programação dinâmica] ([CLRS] Capítulo 15): Exercícios 15.2-1, 15.2-2, 15.2-3, 15.3-2, 15.3-3, 15.3-5, 15.4-1, 15.4-2, 15.4-3, 15.4-4, 15.4-5, 15.4-6, 15.5-1, 15.5-2, 15.5-3; Problemas: 15-4, 15-6, 15-7.
  20. [Caminhos Mínimos - Bellman-Ford]([CLRS] Capítulo 24:) Exercícios 24.1-1 a 24.1-4, 24.1-6.
  21. [Caminhos Mínimos - Floyd-Warshall]([CLRS] Capítulo 25:) Exercícios 25.2-1 a 25.2-9.

Bibliografia e materiais recomendados

Last Update: 07/07/2021 17:40