Paulo Mann

Paulo Mann

AI Researcher & Professor in Computer Science

Algoritmos e Grafos

Semestre: 25-2
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, pessoalmente ou via email.
  • Horário: Terça e Quinta, 10:00-12:00
  • Local: F3-007 (CCMN)
  • Monitores: Lucas Tsai e Yasmim Lima

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 05/08Introdução ao curso
Qui 07/08Capí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
Ter 12/08Capí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 14/08Capítulo 20.2 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Busca em Largura
Ter 19/08Capí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 21/08Capítulo 20.3 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Busca em Profundidade
Ter 26/08Capítulos 20.3 e 20.4 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Aplicações de DFS: Classificação de arestas e Ordenação Topológica—
Qui 28/08Capítulo 20.5 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Aplicações de DFS: Componentes Fortemente Conexos
Ter 02/09Capítulo 20.5 do Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.Aplicações de DFS: Componentes Fortemente Conexos
Qui 04/09Capí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 09/09Capí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 11/09—— —
Ter 16/09—— —
Qui 18/09—— —
Ter 23/09Sem aula: semana da integração acadêmica (SIAC)
Qui 25/09Sem aula: semana da integração acadêmica (SIAC)
Ter 30/09P1
Qui 02/10—— —
Ter 07/10—— —
Qui 09/10—— —
Ter 14/10—— —
Qui 16/10—— —
Ter 21/10—— —
Qui 23/10—— —
Ter 28/10Sem aula: dia do funcionário público
Qui 30/10—— —
Ter 04/11—— —
Qui 06/11—— —
Ter 11/11—— —
Qui 13/11—— —
Ter 18/11—— —
Qui 20/11Sem aula: dia da consciência negra
Ter 25/11—— —
Qui 27/11—— —
Ter 02/12—— —
Qui 04/12—— —
Ter 09/12—— —
Qui 11/12—— —
Ter 16/12—— —
Qui 18/12—— —

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 Final (PF)
  • ✅ 1 Prova de Reposição (PR) - apenas com comprovante de acordo com o regulamento da universidade
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