MC558 - Projeto e Análise de Algoritmos II

Primeiro semestre de 2019

Prof. Orlando Lee




Conteúdo desta página



Avisos importantes

Para ver as notas finais clique aqui.

Horário das aulas e atendimento



Objetivos

O que será visto no curso:
  1. Algoritmos eficientes para vários problemas envolvendo grafos
  2. Redução de problemas
  3. Programação Linear


Programa da disciplina

Abaixo seguem os tópicos que serão cobertos e sugestões para leitura. [CLRS] é a refrência [1] e [Manber] é a referência [4]. Em verde encontram-se os tópicos já cobertos em aula):


Aulas de exercícios

Todas essas datas estão sujeitas a alteração.

Listas de Exercícios

Abaixo estão várias listas de exercícios. Além de servir para maior fixação do material apresentado em classe, o conteúdo dos exercícios é considerado parte integrante do material visto e tratado como parte coberta da matéria. A entrega deles não será cobrada. Entretanto, para o bom aprendizado da disciplina é necessário que cada aluno tente fazer individualmente os exercícios e só depois discutir em grupo. Dúvidas ou dificuldades devem ser discutidas com o docente ou o PED.

  1. Lista 1 [Representação]([CLRS] Capítulo 22): Exercícios 22.1-1 a 22.1-6.
  2. Lista 2 [BFS]([CLRS] Capítulo 22): Exercícios 22.2-1 a 22.2-9.
  3. Lista 3 [DFS]([CLRS] Capítulo 22): Exercícios 22.3-1 a 22.3-12.
  4. Lista 4 [Ordenação Topológica]([CLRS] Capítulo 22): Exercícios 22.4-1 a 22.4-5.
  5. Lista 5 [Componentes Fortemente Conexos]([CLRS] Capítulo 22): Exercícios 22.5-1 a 22.5-7; Problema 22-1.
  6. Lista 6 [AGM - Básico]([CLRS] Capítulo 23): Exercícios 23.1-1 a 23.1-11.
  7. Lista 7 [AGM - 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.
  8. Lista 8 [CM - Grafos Orientados Acíclicos]([CLRS] Capítulo 24:) Exercícios 24.2-1 a 24.2-4; Problema 24-2.
  9. Lista 9 [CM - Dijkstra]([CLRS] Capítulo 24:) Exercícios 24.3-1 a 24.3-8.
  10. Lista 10 [CM - Bellman-Ford]([CLRS] Capítulo 24:) Exercícios 24.1-1 a 24.1-4, 24.1-6.
  11. Lista 11 [CM - Sistemas de Diferenças]([CLRS] Capítulo 24:) Exercícios 24.4-1 a 24.4-8, 24.4-10 a 24.4-11.
  12. Lista 12 [CM - Floyd-Warshall]([CLRS] Capítulo 25:) Exercícios 25.2-1 a 25.2-9.
  13. Lista 13 [Fluxo Máximo] pdf ; ([CLRS] Capítulo 26:) Exercícios 26.2-1 a 26.2-6, 26.2-10 a 26.2-13.
  14. Lista 14 [Redução] pdf
  15. Lista 15 [Modelagem por PL] pdf


Material didático

O material didático (slides) que será usado neste curso foi preparado pelo professor Cid Carvalho de Souza e por Cândida Nunes da Silva. O que disponibilizarei aqui será basicamente o mesmo com algumas adaptações, modificações e erros introduzidos por mim.

Deixo claro que o material serve principalmente como guia e de nenhum modo deve ser usado como única fonte de estudos. Para isso, deve-se consultar a bibliografia.

Os slides estão em arquivos no formato PDF (idênticos aos usados em aula) e serão disponibilizados ao longo do semestre.

Algoritmos em Grafos

Redução de problemas

Programação Linear