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

Projeto e Análise de Algoritmos

Turmas A e C - 2s2018

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

Avisos

[06/08] Página da disciplina no ar.

Informações do Curso

Trabalhos Práticos

Tópicos das Aulas

  1. Motivação, Multiplicação e Indução
    Notas de aula: Motivação, Multiplicação, Indução.
    Bibliografia: Seção 2.1 do Algorithms, Capítulo 5 do Elementos de Matemática Discreta para Computação.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 1 1, 1 2, 1 3.

  2. Ordenação e Algoritmos Elementares
    Notas de aula: Ordenação, InsertionSort, SelectionSort, BubbleSort.
    Bibliografia: Seção 2.1 do Introduction to Algorithms, Capítulo 8 do Projeto de Algoritmos (em C).

  3. Heapsort, Heap e Heapify
    Notas de aula: Ordenação, HeapSort, Heap.
    Bibliografia: Seção 4.5 do Algorithms, Capítulo 6 do Introduction to Algorithms, Capítulo 10 do Projeto de Algoritmos (em C).
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 12 1, 12 2, 12 3.

  4. Divisão e Conquista, MergeSort, Princípios de Análise de Algoritmos
    Notas de aula: Divisão e Conquista, MergeSort, Árvore de Recursão, Análise por Substituição, Princípios de Análise.
    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, 1 8.

  5. Análise Assintótica
    Notas de aula: Motivação, Notacao O, Notação Omega, Notação Theta, Notações ozinho e omegazinho.
    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.

  6. Algoritmo para Contar Inversões e Algoritmo de Multiplicação de Matrizes de Strassen
    Notas de aula: Divisão e Conquista, Contar Inversões, Multiplicação Matrizes, Análise por Substituição.
    Bibliografia: Seção 2.5 do Algorithms, Seções 4.2 e 4.3 (28.2 e 4.1 da 2ed) do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 3 1, 3 2, 3 3.

  7. Teorema Mestre
    Notas de aula: Teorema Mestre, Intuição e Interpretação.
    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.

  8. Encontrar o Par Mais Próximo
    Notas de aula: Par Mais Proximo, Corretude Algoritmo Par Mais Proximo Dividido.
    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.

  9. QuickSort
    Notas de aula: QuickSort.
    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.

  10. Limitante Inferior para Ordenação e Problema da Seleção
    Notas de aula: Limitante Inferior Ordenação, Limitante Inferior Ordenação, Problema da Seleção, Problema da Seleção.
    Bibliografia: Seções 2.3 e 2.4 do Algorithms, Seções 8.1 e 9.2 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 8 6, 8 1, 8 2.

  11. Grafos, Busca em Grafos e Busca em Largura
    Notas de aula: Introdução a Grafos, Busca Genérica em Grafos, Busca Genérica em Grafos, Busca em Largura, Busca em Largura.
    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.

  12. Busca em Profundidade e Ordenação Topológica
    Notas de aula: Busca em Profundidade, Busca em Profundidade, Ordenação Topológica, Ordenação Topológica, Provas sobre Ordenação Topológica.
    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.

  13. Componentes Fortemente Conexos
    Notas de aula: Componentes Fortemente Conexos, Exemplo 1 para Componentes Fortemente Conexos, Exemplo 2 para Componentes Fortemente Conexos.
    Bibliografia: Seções 3.4 do Algorithms, Seções 22.5 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 10 7, 10 8, 10 9.

  14. Caminhos Mínimos e Algoritmo de Dijkstra
    Notas de aula: Caminhos Mínimos, Exemplos de Caminhos Mínimos, Algoritmo de Dijkstra, Exemplos de Dijkstra, Corretude de Dijkstra.
    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 11 1, 11 2, 11 3, 11 4.

  15. Algoritmos Gulosos e Problema do Escalonamento
    Notas de aula: Algoritmos Gulosos, Problema do Escalonamento, Algoritmo Guloso para Escalonamento, Prova de Corretude do Algoritmo.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 1, 2, 3, 4, 5, 6.

  16. Árvores Geradoras Mínimas, Propriedade do Corte e Algoritmo de Prim
    Notas de aula: Árvore Geradora Mínima, Exemplo Árvore Geradora Mínima, Propriedade do Corte, Exemplo Cortes, Exemplo Propriedade do Corte, Algoritmo de Prim, Exemplo Algoritmo de Prim, Corretude do Algoritmo de Prim, Exemplo Lema Travessia Par, Explicação Algoritmo de Prim com Heap, Explicação Operação Atualização Heap.
    Bibliografia: Seção 5.1 do Algorithms, Capítulo 23 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 1, 2, 3, 4, 5, 6, 7.

  17. Algoritmo de Kruskal para encontrar Árvores Geradoras Mínimas e Estrutura de Dados Union-Find
    Notas de aula: Algoritmo de Kruskal, Exemplo Algoritmo de Kruskal, Kruskal produz Árvore Geradora, Arestas de Kruskal satisfazem Propriedade do Corte.
    Bibliografia: Seção 5.1 do Algorithms, Capítulos 23 e 21 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden sobre Kruskal 1, 2, 3, 4, 5, e sobre Union-Find 1, 2, 3, 4, 5, 6, 7, 8, 9.

  18. Algoritmos Gulosos para os problemas da Seleção de Atividades, da Mochila Fracionária e da k-Clusterização com Espalhamento Máximo
    Notas de aula: Roteiro para Projetar Algoritmos Gulosos, Seleção de Atividades, Mochila Fracionaria, k-Clusterização com Espalhamento Máximo, Prova de Corretude da k-Clusterização.
    Bibliografia: Seção 16.1 do Introduction to Algorithms.
    Material complementar: Nota de aula sobre mochila fracionária do profe. Paulo Feofiloff e vídeo aulas do prof. Tim Roughgarden sobre k-Clusterização 1, 2.

  19. Programação Dinâmica e o problema do Conjunto Independente de Peso Máximo em Grafos Caminhos
    Notas de aula: Conjunto Independente de Peso Máximo em Grafos Caminhos, Exemplo de Diferentes Abordagens para o Problema, Subestrutura Ótima, Subestrutura Ótima, Algoritmo de Programação Dinâmica, Algoritmo para Reconstruir a Solução, Principios da Programação Dinâmica.
    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.

  20. Algoritmos de Programação Dinâmica para os problemas da Mochila e do Alinhamento de Sequências
    Notas de aula: Principios da Programação Dinâmica, Problema da Mochila, Exemplo do Algoritmo para o Problema da Mochila, Problema do Alinhamento de Sequências (ou da Distância de Edição).
    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.

  21. Programação Dinâmica e o problema da Árvore Binária de Busca Ótima
    Notas de aula: Roteiro para Projetar um Algoritmo de Programação Dinâmica, Problema da Árvore Binária de Busca Ótima, Exemplo para Árvore Binária de Busca Ótima, Subestrutura Ótima, Exemplo para Subestrutura Ótima, Recorrência, Algoritmo de Programação Dinâmica, Representação Matricial do Algoritmo.
    Bibliografia: Seção 15.5 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 1, 2, 3, 4, 5.

  22. Programação Dinâmica e o problema dos Caminhos Mínimos
    Notas de aula: Roteiro para Projetar um Algoritmo de Programação Dinâmica, Problema dos Caminhos Mínimos com Custos Negativos, Exemplo de Circuito Negativo, Subestrutura Ótima, Exemplo para Subestrutura Ótima, Recorrência, Algoritmo de Bellman-Ford, Exemplo do Algoritmo de Bellman-Ford, Detectando Circuito Negativo, Melhorias para o Algoritmo de Bellman-Ford.
    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.

  23. Caminhos Mínimos de Todos para Todos
    Notas de aula: Caminhos Mínimos de Todos para Todos, Subestrutura Ótima de Floyd-Warshall, Exemplo de Subestrutura Ótima, Algoritmo de Floyd-Warshall, Algoritmo de Johnson, Exemplo para Algoritmo de Johnson.
    Bibliografia: Seção 6.6 do Algorithms e Seções 26.2 e 26.3 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden sobre Floyd-Warshall 1, 2, 3 e sobre Johnson 1, 2, 3.

  24. Problemas NP-Completos
    Notas de aula: Problemas NP-Completos, Exemplo redução 3-CNF-SAT para Clique, Exemplo redução Clique para Cobertura por Vértices, Exemplo redução Circuito Hamiltoniano para Problema do Caixeiro Viajante.
    Bibliografia: Capítulo 8 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.

  25. Algoritmos Exatos para Cobertura por Vértices e Problema do Caixeiro Viajante
    Notas de aula: Estratégias para Atacar Problemas NP-Completos, Cobertura por Vértices, Exemplo para Cobertura por Vértices, Análise de Eficiência do Algoritmo Recursivo para Cobertura por Vértices, Problema do Caixeiro Viajante, Exemplo para Problema do Caixeiro Viajante.
    Bibliografia: Seção 9.1 do Algorithms.
    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.

  26. Algoritmos de Aproximação para Problema do Caixeiro Viajante e Mochila
    Notas de aula: Problema do Caixeiro Viajante, Exemplo Algoritmo Guloso para Problema do Caixeiro Viajante, Problema da Mochila, Exemplo Problema da Mochila.
    Bibliografia: Seção 9.2 do Algorithms e Capítulo 35 do Introduction to Algorithms.
    Material complementar: Vídeo aulas do prof. Tim Roughgarden 1, 2, 3.

  27. Busca Local para Problema do Corte Máximo
    Notas de aula: Busca Local, Exemplo de Vizinhança para Problema do Caixeiro Viajante, Problema do Corte Máximo, Exemplo Problema do Corte Máximo, Definições para Busca Local do Corte Máximo, Cenário de Pior Caso da Busca Local do Corte Máximo, Resumo de Algoritmos 1/2-Aproximados para Corte Máximo.
    Bibliografia: Seção 9.3 do Algorithms.
    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: 05/05/2021 16:45