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

Projeto e Análise de Algoritmos

Turmas A, B e C - 2s2023

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

Tópicos das Aulas

  1. 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.
  2. 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.
  3. Corretude de Algoritmos e Contagem de Operações
    Vídeos da aula 03: Playlist.
    Notas de aula: PDF.
    Material complementar: Vídeo aulas da profa. Carla N. Lintzmayer.
  4. 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.
  5. Divisão e Conquista, MergeSort, Árvore de Recorrência
    Vídeos da aula 05: 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.
  6. Encontrar o Par Mais Próximo
    Vídeos da aula 06: Playlist.
    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.
  7. Teorema Mestre
    Vídeos da aula 07: Playlist.
    Vídeos da aula bônus sobre o Algoritmo de Multiplicação de Matrizes de Strassen: Playlist.
    Notas de aula: PDF, PDF_Bônus.
    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, 3 3.
  8. Bases de Probabilidade, Problema da Seleção
    Vídeos da aula 08: Playlist.
    Notas de aula: PDF, PDF_Bônus.
    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.
  9. Grafos e o Problema do Corte Máximo
    Vídeos da aula 09: Playlist.
    Notas de aula: PDF.
    Bibliografia: Seção 3.1 e Página 143 do Algorithms, Seção 22.1 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 9 1, 9 2, 9 3.
  10. Algoritmo Aleatorizado baseado em Contrações para o Corte Máximo
    Vídeos da aula 10: Playlist.
    Notas de aula: PDF.
    Bibliografia: Seção 3.1 e Página 143 do Algorithms, Seção 22.1 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 9 4, 9 5.
  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.
  12. Revisão, Exercícios e Dúvidas
    Exercícios recomendados: Análise Assintótica, Recorrências e Teorema Mestre, Divisão e Conquista.
    Exercícios com resolução ou comentários: Análise Assintótica, Recorrências e Teorema Mestre, Divisão e Conquista.
  13. Prova 1
  14. Seleção de Atividades e Mochila Fracionária
    Vídeos da aula 14: 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.
  15. Árvores Geradoras Mínimas (MST), Propriedade do Corte, Algoritmo de Prim
    Vídeos da aula 15: Playlist.
    Notas de aula: PDF, PDF_Bônus.
    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.
  16. Árvores Geradoras Mínimas (MST), Algoritmo de Kruskal
    Vídeos da aula 16: 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 Kruskal 1, 2, 3, 4, 5.
  17. Union Find
    Vídeos da aula 17: Playlist.
    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.
  18. Programação Dinâmica, Conjunto Independente de Peso Máximo em Caminhos
    Vídeos da aula 18: 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.
  19. Problemas da Mochila e do Alinhamento de Sequências
    Vídeos da aula 19: Playlist.
    Notas de aula: PDF, PDF_Bônus.
    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.
  20. Revisão, Exercícios e Dúvidas
    Exercícios recomendados: Algoritmos Gulosos.
    Exercícios com resolução ou comentários: Algoritmos Gulosos.
  21. Caminhos Mínimos, Algoritmo de Bellman-Ford
    Vídeos da aula 21: Playlist.
    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.
  22. Caminhos Mínimos de Todos para Todos, Algoritmo de Floyd-Warshall
    Vídeos da aula 22: Playlist.
    Notas de aula: PDF.
    Bibliografia: Seção 6.6 do Algorithms e Seção 25.2 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden sobre Floyd-Warshall 1, 2, 3.
  23. Caminhos Mínimos de Todos para Todos, Algoritmo de Johnson
    Vídeos da aula 23: Playlist.
    Notas de aula: PDF.
    Bibliografia: Seção 6.6 do Algorithms e Seção 25.3 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden sobre Johnson 1, 2, 3.
  24. Revisão, Exercícios e Dúvidas
    Exercícios recomendados: Programação Dinâmica, Caminhos Mínimos.
    Exercícios com resolução ou comentários: Programação Dinâmica, Caminhos Mínimos.
  25. Problemas NP-Completos, Reduções entre Problemas (Parte 1)
    Vídeos da aula 25: Playlist.
    Bibliografia: Capítulos 8 e 9 do Algorithms e Capítulo 34 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 1, 2, 3, 4, 5, 6.
  26. Problemas NP-Completos, Reduções entre Problemas (Parte 2)
    Vídeos da aula 26: Playlist.
    Bibliografia: Capítulos 8 e 9 do Algorithms e Capítulo 34 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 1, 2, 3, 4, 5, 6.
  27. Prova 2
  28. Revisão, Exercícios e Dúvidas
  29. Prova Sub

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: 09/07/2024 15:01