Paulo Mann

Paulo Mann

AI Researcher & Professor in Computer Science

Algoritmos e Grafos

Semestre: 25-1
Código: ICP368
Professor: Paulo Mann
Nesta disciplina, iremos ver problemas clássicos em Teoria dos Grafos, que servirão de pano de fundo para a compreensão de técnicas de desenvolvimento e análise de algoritmos, ao mesmo tempo em que familiarizam o aluno com a representação e manipulação de grafos no computador.

Informação Básica

A plataforma de comunicação principal será o grupo no classroom.

As aulas serão presenciais.

  • Atendimento: sob demanda.
  • Horário: Terça e Quinta, 10:00-12:00
  • Local: F3-004 (CCMN)
  • Monitor(a): não possui

Ementa

Representação de Grafos; Ordenação Topológica; Buscas em grafos e Digrafos (largura e profundidade); Técnicas de Desenvolvimento de Algoritmos; Decomposição; Recursão; Algoritmo Guloso; Programação Dinâmica; Aplicação das Técnicas Usadas; Fluxo Máximo.

Cronograma Planejado

DataLeiturasConteúdoMaterial
Ter 18/03Introdução ao curso
Qui 20/03Capítulo 20.1 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Introdução, conceitos básicos de grafos direcionados e não direcionados
Ter 25/03Capítulo 20.1 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Representação de grafos no computador; algoritmos básicos de inserção, remoção e consulta em grafos direcionados e não direcionados
Qui 27/03Capítulo 20.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Busca em Largura
Ter 01/04Não haverá aula: semana acadêmica
Qui 03/04Não haverá aula: semana acadêmica
Ter 08/04Capítulos 20.2 e 20.3 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Subgrafo Predecessor e Busca em Profundidade
Qui 10/04Capítulo 20.3 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Busca em Profundidade
Ter 15/04Capítulos 20.3 e 20.4 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Aplicações de DFS: Ordenação Topológica—
Qui 17/04Capítulo 20.5 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Aplicações de DFS: Componentes Fortemente Conexos
Ter 22/04Não haverá aula: recesso
Qui 24/04Capítulo 15.1 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Problemas de otimização, método guloso, o problema da árvore geradora mínima
Ter 29/04Capítulos 21.0 e 21.1 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Árvore geradora mínima: algoritmo genérico e prova para identificar arestas seguras
Qui 01/05Não haverá aula: dia do trabalhador
Ter 06/05Capítulo 21.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Árvore geradora mínima: algoritmos de Kruskal e Prim
Qui 08/05Capítulo 21.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Complexidade do algoritmo de Prim, comparação de Kruskal e Prim; Lista 1
Ter 13/05Revisão e Lista 1
Qui 15/05P1
Ter 20/05Vista de Prova
Qui 22/05Capítulo 22.0 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.O problema de caminhos mínimos de origem única; intuição de Dijkstra
Ter 27/05Capítulo 22.3 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.O algoritmo de Dijkstra
Qui 29/05Capítulo 14 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Programação Dinâmica
Ter 03/06Capítulos 22.1 e 22.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Bellman-Ford e distância mínima em DAGs
Qui 05/06Capítulos 23.0 e 23.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.O problema de caminhos mínimos entre todos os pares de vértices; Floyd-Warshall
Ter 10/06Capítulos 23.0 e 23.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Floyd-Warshall e exercícios
Qui 12/06Capítulos 24.0, 24.1, e 24.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Fluxo máximo, corte mínimo, redes residuais e caminhos aumentantes
Ter 17/06Capítulos 24.0, 24.1, e 24.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Ford-Fulkerson, Edmonds-Karp; revisão de Floyd-Warshall
Qui 19/06Não haverá aula: Corpus Christi
Ter 24/06P2
Qui 26/06Prova Substitutiva
Ter 01/07PF e Vista da P2
Qui 03/07Vista da PF e P2

Bibliografia

Bibliografia Primária

  • Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.

Bibliografia Secundária

  • Teoria Computacional de Grafos; os algoritmos. Jayme Luiz Swarcfiter, Fabiano S. Oliveira e Paulo E. D. Pinto. Elsevier, 2018.

Avaliação

  • ✅ 2 Provas (P1/P2)
  • ✅ 1 Prova Substitutiva (PS) e 1 Prova Final (PF)
MP = (P1 + P2) / 2
Se MP < 3 → Reprovado
Se MP ≥ 7 → Aprovado
Se 3 ≤ MP < 7 → Então o aluno faz a Prova Final (PF)
Se (MP + PF) / 2 ≥ 5 → Aprovado
Se (MP + PF) / 2 < 5 → Reprovado
← Voltar às Disciplinas